Challenges • Asked about 4 years ago by orlandu8@gmail.com
Here's what I got for the solution
function sumDigits(num) {
let n = num % 9;
if(n === 0) {
return 9;
} else {
return n;
}
}
The challenge says expected time complexity to be O(log n), but unless I'm missing something here. This is O(1) isn't it?
You discovered the digital root trick. That implementation is constant time in typical interview settings.
Two notes:
- Handle 0 separately. Your code returns 9 for 0, which is incorrect for most versions of the problem.
- If negatives can appear, use Math.abs first (or define behavior).
Clean version:
js
function sumDigits(num) {
num = Math.abs(num);
return num === 0 ? 0 : 1 + (num - 1) % 9;
}
Why the mismatch with “expected O(log n)”? The straightforward approach repeatedly sums digits, which is proportional to the number of digits (~log10 n). Using the digital root congruence reduces it to O(1), which is better and perfectly acceptable unless the prompt forbids math shortcuts.
Quick checks:
- sumDigits(38) -> 2
- sumDigits(9) -> 9
- sumDigits(0) -> 0
Yeah, your version is O(1) for normal integer inputs. The “expected O(log n)” is for the naive repeated-summing approach where work scales with the number of digits.
Two practical notes to add to what Team AlgoDaily said:
- Theory vs. practice: modulo on fixed-width ints is constant time. If you’re working with arbitrary-precision numbers (BigInt, big libs), mod is O(d) where d is digits, so strictly speaking it’s not O(1).
- Base matters: the trick generalizes to base b as 1 + (n - 1) % (b - 1). In base 10, that’s 9.
JS-ready and safe for 0/negatives:
js
function sumDigits(num) {
num = Math.abs(num);
return num === 0 ? 0 : 1 + (num - 1) % 9;
}
If inputs might exceed Number.MAXSAFEINTEGER, treat them as strings and compute n % 9 as you stream the digits:
js
function sumDigitsStr(s) {
if (s === "0") return 0;
if (s[0] === "-") s = s.slice(1);
let mod = 0;
for (const ch of s) mod = (mod + (ch.charCodeAt(0) - 48)) % 9;
return mod === 0 ? 9 : mod;
}
You’re right: with fixed-width integers, the digital-root formula makes it O(1). The “expected O(log n)” typically refers to the naive loop that sums digits repeatedly, proportional to the number of digits.
Why the formula works (proof sketch): 10 ≡ 1 (mod 9), so 10k ≡ 1 (mod 9) and n ≡ sum of its digits (mod 9). Map multiples of 9 to 9 (except 0 → 0), giving the digital root.
JS options:
- Branchless and handles 0/negatives:
js
const sumDigits = n => (Math.abs(n) - 1) % 9 + 1;
Note: In JS, -1 % 9 === -1, so this returns 0 for input 0 as desired.
js
function sumDigits(n) {
n = Math.abs(n);
return n === 0 ? 0 : 1 + (n - 1) % 9;
}
Complexity nuance:
- Unit-cost model (typical interviews, 32/64-bit numbers): O(1).
- Bit model/arbitrary precision: modulo is O(d) where d is digit count, so overall O(log n). For true big inputs, either use BigInt:
```js
function sumDigitsBig(n) {
n = n