Recursion solution + O(1) Solution


  • 0
    B

    Recursion is a straightforward solution :

    public class Solution {
        public int addDigits(int num) {
            int sum = 0;
            if(num < 10)
                return num;
            while(num!=0){
                sum+=num%10;
                num/=10;
            }
            return addDigits(sum);
        }
    }
    

    For O(1) solution if you think about it what happen when you adding 2 numbers, There is 2 conditions x+y >= 10 or < 10 , then if it greater than 10 then the sum of its digits will be less than 10 why ? because the biggest result you can achieve is 18 -> 9+9 -> 1+8 -> 9 , So easily we can define when the number (x) exceeds 10 is by 10-x , for example for 8 -> 8 + any number greater than 2 >= 10, so the idea of xy number we need to get the 10 start of x and the distance between y and this start.
    example :
    (let x be the biggest).
    38 -> x = 8,y = 3
    z => 10 - 8 = 2 (start of 8)
    y-z = 1 -> 1 + 1 = 2

    for 75 -> x = 7,y = 5
    z => 10-7 = 3
    y-z = 2 + 1 = 3

    public class Solution {
        public int addDigits(int num) {
            int sum = 0;
            if(num < 10)
                return num;
            int x = num%10,y = (num/10)%10,z;
            z = x;
            x = Math.max(x,y);
            y = Math.min(z,y);
            num/=100;
            while(num!=0){
                if(10-x <= y){
                    z = ((y-(10-x)) + 1);
                }else{
                    z = x+y;
                }
                sum+=z;
                x = z;
                y = num%10;
                x = Math.max(x,y);
                y = Math.min(z,y);
                num/=10;
            }
            return (10-x <= y) ? ((y-(10-x)) + 1) : x+y;
        }
    }
    

Log in to reply
 

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