Saltar al contenido principal

Plus One

Given an array digits that represents a non-negative integer, add one to the number and return the result as an array.

The digits are ordered from most significant to least significant in left-to-right order. The large integer does not contain any leading zeros.

Example(s)​

Example 1:

Input: digits = [1, 2]
Output: [1, 3]
Explanation: The array represents the integer 12. Adding one gives 12 + 1 = 13.

Example 2:

Input: digits = [9, 9]
Output: [1, 0, 0]
Explanation: The array represents the integer 99. Adding one gives 99 + 1 = 100.

Example 3:

Input: digits = [4, 3, 2, 1]
Output: [4, 3, 2, 2]
Explanation: The array represents the integer 4321. Adding one gives 4321 + 1 = 4322.

Example 4:

Input: digits = [9]
Output: [1, 0]
Explanation: The array represents the integer 9. Adding one gives 9 + 1 = 10.

Solution​

The solution processes digits from right to left:

  1. Start from the rightmost digit
  2. Add 1 to the current digit
  3. If the result is less than 10, we're done - return the array
  4. If the result is 10, set the digit to 0 and carry 1 to the next position
  5. If we need to carry beyond the first digit, add a new digit 1 at the beginning

JavaScript Solution

/**
* Add one to a number represented as an array of digits
* @param {number[]} digits - Array of digits representing a number
* @return {number[]} - Result after adding one
*/
function plusOne(digits) {
// Start from the rightmost digit
for (let i = digits.length - 1; i >= 0; i--) {
  // Add one to the current digit
  digits[i]++;
  
  // If the digit is less than 10, no carry needed
  if (digits[i] < 10) {
    return digits;
  }
  
  // Otherwise, set to 0 and continue (carry will be handled in next iteration)
  digits[i] = 0;
}

// If we've processed all digits and still have a carry,
// we need to add a new digit 1 at the beginning
return [1, ...digits];
}

// Test cases
console.log(plusOne([1, 2])); // [1, 3]
console.log(plusOne([9, 9])); // [1, 0, 0]
console.log(plusOne([4, 3, 2, 1])); // [4, 3, 2, 2]
console.log(plusOne([9])); // [1, 0]
console.log(plusOne([1, 9, 9])); // [2, 0, 0]
console.log(plusOne([0])); // [1]
Output:
Click "Run Code" to execute the code and see the results.

Alternative Solution (More Explicit)​

Here's an alternative approach that explicitly tracks the carry:

/**
 * Add one to a number represented as an array of digits (explicit carry)
 * @param {number[]} digits - Array of digits representing a number
 * @return {number[]} - Result after adding one
 */
function plusOneExplicit(digits) {
  let carry = 1; // Start with carry of 1 (the "+1" we're adding)
  
  // Process from right to left
  for (let i = digits.length - 1; i >= 0; i--) {
    const sum = digits[i] + carry;
    digits[i] = sum % 10;
    carry = Math.floor(sum / 10);
    
    // Early exit if no carry remains
    if (carry === 0) {
      break;
    }
  }
  
  // If carry remains after processing all digits
  if (carry > 0) {
    return [carry, ...digits];
  }
  
  return digits;
}

Complexity​

  • Time Complexity: O(n) - Where n is the length of the digits array. In the worst case, we iterate through all digits once.
  • Space Complexity: O(1) - We modify the input array in place. The only extra space is for the new array when we need to add a leading 1, which is O(n) in that specific case, but typically O(1).

Approach​

The solution uses a right-to-left processing approach:

  1. Start from the end: Process digits from rightmost to leftmost (least significant to most significant)
  2. Add one: Increment the current digit
  3. Handle carry: If the digit becomes 10, set it to 0 and continue to the next digit
  4. Edge case: If all digits were 9, we need to add a new leading digit 1

Key Insights​

  • Right-to-left processing: Since we're adding 1, the carry propagates from right to left
  • Early termination: Once we find a digit that doesn't produce a carry, we can stop
  • In-place modification: We can modify the input array directly, which is more space-efficient
  • Edge case handling: When all digits are 9, we need to create a new array with a leading 1
  • Simple logic: Since we're only adding 1, the carry is always either 0 or 1

Edge Cases​

  • All 9s: [9, 9, 9] → [1, 0, 0, 0] (requires new leading digit)
  • Single digit: [9] → [1, 0]
  • No carry needed: [1, 2, 3] → [1, 2, 4] (simple increment)
  • Partial carry: [1, 9, 9] → [2, 0, 0] (carry propagates but doesn't reach the beginning)
  • Zero: [0] → [1]

Takeaways​

  • Right-to-left iteration is natural for arithmetic operations on digit arrays
  • Early exit optimization improves average-case performance
  • In-place modification is more efficient than creating a new array when possible
  • Edge case handling is crucial - always consider what happens when all digits are 9
  • Simple problems can have elegant solutions when you think about the problem structure