Detailed Solution (Java,Javascript)


  • 0
    S

    Approach #
    Complexity :- O(n)

    This problem can be solved by the simple mathematical approach.
    As in the problem statement, we have to add one at the highest index of the array if there is carry forwarded after addition, that will be moved to the next lower index for addition.

    Corner case: In case the carry is forwarded all the way to the most significant digit then the length of the array will increase by one. for example [9,9] the result will be [1,0,0]

    in this approach, we need extra space for a new array for the corner case. in worst scenario the space complexity will be O(n)
    Solution 1:

          var plusOne = function(digits) {
                var c=1;     // To add one in digits 
                var arr=[]; 
               for(let i=digits.length-1;i>=0;i--){ 
                           let d=digits[i]+c; 
                             digits[i]=(d<10) ? d : (d-10); 
                            c= d<10 ? 0 : 1 ; \\ for carry calculation
         } 
          if(c!=0){  
              arr[0]=c; 
            for(let i=0;i<digits.length;i++){ 
                arr[i+1]=digits[i]; 
            } 
         } 
         else{ 
             arr=digits; 
         } 
          return arr;  
      };
    

    Solution 2 :
    In approach, we can reduce the number of comparisons.
    if digit at any index is less than 9 then we can add one in that number and return the array. because there will be no carry so we don't need to modify the other numbers of the array.
    for the corner case, we can create an array with length one more than the input array and all the elements of that array will be zero except the number at index 0 which will be 1 because of carry forwarded.
    in the worst case scenario, the Time and Space complexity will be O(n)

    plusOne( digits) {
       var arr=[];
         for(let  i = digits.length - 1;i >= 0;i--){
             if(digits[i] < 9){
                 digits[i]++;
                 return digits;
             }
             digits[i] = 0;
         }
          arr[0]=c; 
         for(let i=0;i<digits.length;i++){ 
             arr[i+1]=0; 
         } 
    return arr;
     }
    

Log in to reply
 

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