Scale Engineer

Plus One

Easy
#0066Time: O(N)Space: O(N)14 companies
Patterns
Math
Data structures
Array
Companies
AccentureAdobeAgodaAmazon

Prompt

You are given a large integer represented as an integer array digits, where each digits[i] is the ith digit of the integer. The digits are ordered from most significant to least significant in left-to-right order. The large integer does not contain any leading 0's.

Increment the large integer by one and return the resulting array of digits.

 

Example 1:

Input: digits = [1,2,3]
Output: [1,2,4]
Explanation: The array represents the integer 123.
Incrementing by one gives 123 + 1 = 124.
Thus, the result should be [1,2,4].

Example 2:

Input: digits = [4,3,2,1]
Output: [4,3,2,2]
Explanation: The array represents the integer 4321.
Incrementing by one gives 4321 + 1 = 4322.
Thus, the result should be [4,3,2,2].

Example 3:

Input: digits = [9]
Output: [1,0]
Explanation: The array represents the integer 9.
Incrementing by one gives 9 + 1 = 10.
Thus, the result should be [1,0].

 

Constraints:

  • 1 <= digits.length <= 100
  • 0 <= digits[i] <= 9
  • digits does not contain any leading 0's.

Approaches

2 approaches with complexity analysis and trade-offs.

This approach converts the array of digits into a data type that can handle arbitrarily large integers, such as Java's BigInteger. The process involves first building a string from the digit array, parsing it into a BigInteger, performing the addition, and then converting the result back into an array of digits. While straightforward, it's not the most performant solution.

Algorithm

  • Create a StringBuilder to hold the string representation of the integer.
  • Iterate through the digits array and append each digit to the StringBuilder.
  • Convert the StringBuilder to a String and then construct a java.math.BigInteger object.
  • Use the add() method of BigInteger to add one to the number.
  • Convert the resulting BigInteger back to a String.
  • Create a new integer array with a size equal to the length of the result string.
  • Iterate through the result string, convert each character back to an integer, and populate the new array.
  • Return the new array.

Walkthrough

The core idea is to leverage a high-level library designed for arbitrary-precision arithmetic. Instead of manually handling the carry logic, we delegate the entire addition operation to the BigInteger class.

import java.math.BigInteger; class Solution {    public int[] plusOne(int[] digits) {        // 1. Convert array to a string representation.        StringBuilder sb = new StringBuilder();        for (int digit : digits) {            sb.append(digit);        }                // 2. Create a BigInteger from the string.        BigInteger number = new BigInteger(sb.toString());                // 3. Add one.        number = number.add(BigInteger.ONE);                // 4. Convert the result back to a string.        String resultStr = number.toString();                // 5. Convert the string back to an integer array.        int[] result = new int[resultStr.length()];        for (int i = 0; i < resultStr.length(); i++) {            result[i] = resultStr.charAt(i) - '0'; // Convert char to int        }                return result;    }}

Complexity

Time

O(N)

Space

O(N)

Trade-offs

Pros

  • The logic is simple to understand and write, as it offloads the complex arithmetic to a built-in library.

  • It correctly handles all edge cases, including very large numbers and the case where the number of digits increases (e.g., 999 + 1).

Cons

  • Significantly less efficient due to the overhead of creating multiple objects (StringBuilder, BigInteger, String) and performing conversions between data types.

  • This approach abstracts away the core arithmetic logic, which might not be what an interviewer is looking for when asking this type of question.

Solutions

class Solution {public  int[] plusOne(int[] digits) {    int n = digits.length;    for (int i = n - 1; i >= 0; --i) {      ++digits[i];      digits[i] %= 10;      if (digits[i] != 0) {        return digits;      }    }    digits = new int[n + 1];    digits[0] = 1;    return digits;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem