C solution in 4ms


  • -1
    A

    Present a C solution in 4ms, longer but faster than the simplest one which adopts "10≡1(mod 9)". The idea in this method is "10≡1(mod 9), 8≡-1(mod 9), 64≡1(mod 9)."

    int addDigits(int num) 
    {
        int temp;
        if (num>=10){
            temp=num;
            num=((num)&0x0007);
            while(temp){
                temp>>=3;num-=(temp&7);
                temp>>=3;num+=(temp&7);
            }
            num--;
            while (num<0) num+=9;
            num++;
        }
        //here num is no more than 7*11
        if (num>=10){
            temp=num>>3;
            num=((num)&0x0007)-(temp&7)+((temp>>3)&7);
            if (num<0) num+=9;
        }
        //here num is no more than 7*2
        if (num>=10){
            num=(num&0x0007)-((num>>3)&7);
            if (num<0) num+=9;
        }
        return num;
    }

Log in to reply
 

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