Fastest and simplest C++ solution


  • 14
    L
    class Solution {
    public:
        vector<int> plusOne(vector<int> &digits) {
            int i,j,carry=1;
            // traditional long addition..
            for(i=digits.size()-1;i>=0&&carry;i--){
                int sum=carry+digits[i];
                carry=sum/10;
                digits[i]=sum%10;
            }
            if(carry){ // if carry is 1, then digits must be all 99..999
                digits[0]=1;
                digits.push_back(0);
            }
            return digits;
        }
    };

  • 0
    J

    cool, good catch of idea with all 9, and that additional digit is only required if all digits are 9.


  • 0
    P

    I guess there is no need to use / and % as we are only increasing by 1,that's costly .

    if(digits[i] + c > 9){
                        c = 1;
                        digits[i] = 0;
                        carrylast = true;
                    }else{
                        c = 0;
                        digits[i]+=1;
                        carrylast = false;
                    }
    

    Any suggestions?


  • 1
    L

    branching may be more costly. you may try using bit hacks and twiddling to avoid % and /. For example, you can exploit this fact :

    digits[i] == sum iff carry == 0, digits[i] == 0 if carry == 1. 
    

    to get

    digits[i] = sum & ~(-carry)
    

    I personally wouldn't recommend this kind of microoptimisation unless it is absolutely necessary.


Log in to reply
 

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