Community

Start a Thread


Notifications
Subscribe You’re not receiving notifications from this thread.

Sum until one digit

Challenges • Asked about 4 years ago by orlandu8@gmail.com

orlandu8@gmail.com Commented on Jul 15, 2021:

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?

Team AlgoDaily Commented on Jun 11, 2025:

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

Pat Kumar Commented on Jun 11, 2025:

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;
}

Jun Commented on Jul 20, 2025:

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.

  • If you prefer explicitness: 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