Sum of all the digits till it becomes single digit in java with o(1) complexity?

Question

I found the answer for this from Henry

int sum = n % 9;
if (sum == 0) sum = 9;

here

java program that sums up the digits of a number until it is a single number Eg: 2748303 = 2+7+4+8+3+0+3 = 27 = 2+7 = 9

Can any one please explain how adding digits and remainder are related?

My logic also would have been as below which is also mentioned in above link

int sum = 0;
    while (n > 9 ) {
                 sum=0;
        while (n > 0) {
            int rem;
            rem = n % 10;
            sum = sum + rem;
            n = n / 10;
        }
        n = sum;
    }

But 2 line answer is awesome.

Answer 1

In Java integers have a limited range, therefore taking a reminder has O(1) asymptotic complexity.

Now to your main question:

Can any one please explain how adding digits and remainder are related?

First note that any number n has the same reminder when divided by 9 as the sum of its digits. In case this does not seem immediately obvious here is a sketch of a proof.

Proof

Let nk,...,n2,n1,n0 be the k+1 digits of the number n.

Let 10^p denote the p-th power of 10.

Then

n = 10^k * nk + ... + 100 * n2 + 10 * n1 + n0 =
  = (10^k - 1) * nk + ... + (100-1) * n2 + (10-1) * n1 +
    + nk + ... + n2 + n1 + n0

Now note that the last line is the sum of digits of the number n

  S0 = nk + ... + n2 + n1 + n0

Let

 S1 = (10^k - 1) * nk + ... + (100-1) * n2 + (10-1) * n1

is divisible by 9 since 10^p - 1 = 9...9 is divisible by 9 for all p > 0.

Since n = S1 + S0 and S1 is divisible by 9, it follows that S0 % 9 = n % 9.

That is what we wanted to prove

Now let S(n) denote the function that returns the sum of digits of the number n, then as we have just observed

  n % 9 = S(n) % 9 = S(S(n)) % 9 = ...

We can continue process until we reach a single digit number.

This is how the reminder and the sum of digits are related.