Javaのo（1）複雑さで1桁になるまでのすべての桁の合計？

Question

私はヘンリー

ここ

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

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

から、このための答えを見つけたいずれかの追加の数字と残りがどのように関係するかを説明していただけますか？

また、上記のリンクに記載されている以下のように私のロジックも

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

しかし、2行の答えは素晴らしいですされていると思います。

Answer 1

Javaの整数では、制限された範囲を持っているので、リマインダーはO（1）漸近の複雑さを持っています。今

はあなたの主な質問に：

いずれかが追加の数字と残りは をどのように関連しているか説明していただけますか？

最初に、数値nには数字の合計として9で割ったときに同じリマインダがあることに注意してください。これがすぐにわからない場合は、ここで証明のスケッチがあります。

がnk,...,n2,n1,n0は数nのk+1桁とする

証明。

その後

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

今すぐ最後の行が数n

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

レッツの数字の和であることに注意してください10^pは10

のp乗を表すと

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

は、10^p - 1 = 9...9がすべてp > 0で9で割り切れるので、9で割り切れる。

n = S1 + S0以来

とS1が9で割り切れる、それは次のようS0％で9 = N％我々は返す関数を表すS(n)を聞かせて今

を証明したかったものです9.

数nの数字の合計値、そして私達はちょうど私たちが一桁の数に到達するまで、私たちは、プロセスを継続することができ

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

を観察しているよう。

リマインダと数字の合計がどのように関連しているかを示します。