258. Add Digits


  • 0
    C

    Solution


    Approach #1 Traditional Way Using Loops or Recursion

    Using loops or recursion to calculate the sum of digits until it less than 10

    public class Solution { // using recursion
        public int addDigits(int num) {
            if(num < 10) return num;
            int re = 0;
            while(num > 0){
                re += num % 10;
                num /= 10;
            }
            return addDigits(re);
        }
    }
    

    Complexity Analysis

    Approach #2 Find The Pattern

    Since there are only 10 possible results ( 0 ~ 9 ) and only addDigits(0) = 0 , we can analysis the pattern as below

    for input n : 
       addDigits(0) = 0;
       if addDigits(n) + 1 < 10
             addDigits(n+1) = addDigits(n) + 1
       else
             addDigits(n+1) = addDigits( addDigits(n) + 1 )
       if addDigits(n) == 9
             addDigits(n + 1) = addDigits( 10 ) = 1
    
    

    From the above we can see the answer repeated from 1 ~ 9 since the input > 0, we can get than

         addDigits(n) = addDigits(n-9) ;  // n - 9 > 0
    

    Only we need is try to reduce the input to 1 ~ 9 and that's the answer.

    public class Solution { // using recursion
        public int addDigits(int num) {
           return 1 + (num - 1) % 9;
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.