《leetCode》:Add Digits

タイトル

Given a non-negative integer num, repeatedly add all its digits until the result has only one digit.

For example:

Given num = 38, the process is like: 3 + 8 = 11, 1 + 1 = 2. Since 2 has only one digit, return it.

Follow up:
Could you do it without any loop/recursion in O(1) runtime?

考え方1
よく使われる方法は、1~9の数になるまで、対数の皆さんを積み重ねて和を求めることです.
実装コードは次のとおりです.

//     ：          
int everyDigitSum(int n){
    if(n<=0){
        return 0;
    } 
    int sum=0;
    while(n){
        int remainder=n%10;
        sum+=(remainder);
        n/=10;
    }
    return sum;
}

int addDigits(int num) {
    if(num<=0){
        return 0;
    }
    while(!(0<num&&num<=9)){
        num=everyDigitSum(num);
    }
    return num;
}

考え方2
構想:任意の整数モード9は、この数字の各ビット上の数字の和に等しい.具体的な証明過程は次の博文を参照してください.

int addDigits(int num){
    if(num<=0){
        return 0;
    }
    int res=num%9;
    return res==0?9:res;
}

コードは簡単ですが、実行時間は構想の1実行時間の2倍以上です.