Sum of Digits of a Number
Mahabharata — The Census Tally — Adding One Digit at a Time
अंकों का योग — एक-एक निकालो। n%10 अंतिम अंक — n/10 शेष संख्या॥
*Sum of digits — extract one by one. n%10 is the last digit — n/10 is what remains.*
The Story
Find the sum of digits of a number using recursion.
For n=1234: 1+2+3+4=10.
**Recursive approach:** - Base: n < 10 → return n (single digit) - Recursive: n%10 (last digit) + sumOfDigits(n/10) (sum of remaining digits)
```java int sumOfDigits(int n) { if (n < 10) return n; // Base: single digit return n % 10 + sumOfDigits(n/10); // Last digit + rest } ```
Trace n=1234: - sum(1234): 4 + sum(123) - sum(123): 3 + sum(12) - sum(12): 2 + sum(1) - sum(1): 1 (base) - Returns: 2+1=3 → 3+3=6 → 6+4=10 ✓
**Key pattern:** `n%10` extracts the last digit, `n/10` removes it. This is how we 'peel' a number digit by digit.
**Iterative equivalent:** ```java int sumIterative(int n) { int sum=0; while (n>0) { sum += n%10; n/=10; } return sum; } ```
The number of recursive calls = number of digits = O(log₁₀ n).
The String Conversion Approach
Convert to string, iterate chars, sum digit values. O(log n).
int sumOfDigitsString(int n) {
int sum=0;
for (char c : String.valueOf(n).toCharArray())
sum += c - '0';
return sum;
}The Last-Digit-Plus-Rest Wisdom
int sumOfDigits(int n) {
if (n < 10) return n;
return n % 10 + sumOfDigits(n / 10);
}Step-by-Step Walkthrough
n=7: return 7 ✅ n=10: 0 + sum(1) = 0+1 = 1 ✅ n=99: 9 + sum(9) = 9+9 = 18 ✅
Deep Insight
**Digit extraction pattern:** `n%10` and `n/10` are the fundamental operations for processing numbers digit by digit. This pattern appears in: - Sum of digits (this problem) - Count digits in a number - Reverse a number: `result = result*10 + n%10; n/=10;` - Check if number is palindrome (by comparing original and reversed)
**Call depth = O(log n):** A d-digit number has d recursive calls. d = floor(log₁₀ n) + 1.
Complexity Analysis
| Approach | Time | Space | Note |
|---|---|---|---|
| Brute Force | O(log n) | O(1) | Iterative digit extraction |
| Optimal | O(log n) | O(log n) | Recursive call stack depth = number of digits |
Pattern Recognition
✅ Process number digit by digit: n%10 + recurse(n/10) ✅ Base: n<10 (single digit) ✅ Number of calls = O(log₁₀ n) ✅ Pattern: last digit + rest **LeetCode Trigger Phrases:** → "sum of digits" recursively → Process number digit by digit → n%10 and n/10 extraction pattern
Bhagavad Gita 9.18
गतिर्भर्ता प्रभुः साक्षी निवासः शरणं सुहृत्। प्रभवः प्रलयः स्थानं निधानं बीजमव्ययम्॥
I am the goal, the sustainer, the master, the witness, the abode, the refuge, the friend, the origin, the dissolution, the foundation, the treasure house, and the imperishable seed.
Connection: The digits of a number are like its component aspects — each contributes to the whole. By extracting the last digit (n%10) and recursing on the remainder (n/10), we peel away each aspect until nothing remains. The sum reveals the number's complete essence. Like the Gita's enumeration of divine aspects — each a different facet of the same truth — the digit sum collects each individual contribution into the whole.