Implement Plus One
Company: Coinbase
Role: Data Scientist
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
Given a non-empty array of digits representing a non-negative integer, where the most significant digit comes first and each element is in [0, 9], add one to the integer and return the resulting array of digits.
You may not convert the entire array directly into a built-in big integer.
Examples:
- [1, 2, 3] -> [1, 2, 4]
- [4, 3, 2, 1] -> [4, 3, 2, 2]
- [9, 9, 9] -> [1, 0, 0, 0]
Discuss the time and space complexity of your approach.
Quick Answer: This question evaluates array manipulation and numeric carry propagation skills, along with the ability to reason about time and space complexity when performing arithmetic on digit lists.
Add one to a non-negative integer represented as a digit array.
Constraints
- Inputs are Python literals matching the function signature.
- Return a deterministic exact-match value.
Examples
Input: ([1,2,3],)
Expected Output: [1, 2, 4]
Explanation: Simple increment.
Input: ([4,3,2,1],)
Expected Output: [4, 3, 2, 2]
Explanation: Increment last digit.
Input: ([9,9,9],)
Expected Output: [1, 0, 0, 0]
Explanation: Carry grows the array.
Hints
- Clarify edge cases before coding.
- Keep the return value deterministic.