Home > Reflections | ⏮️ ⏭️

2024-06-28

🏋️ Coding Practice

66. Plus One

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.

🪞 Reflections

1. Manually doing math can be a bit more confusing than it seems. It took me a few minutes to figure out the precise logic for carrying under any circumstance.
2. Still, this went well.
   1. I didn’t catch any bugs while manually testing.
   2. But a cursory code review after my initial implementation did catch that I was incrementing instead of decrementing my counter, which I quickly fixed before my first manual test case.
3. I’m happy with the time (<16m)

⌨️ My Solution

/* increment a large integer, digit-by-digit  
Approaches  
1. do math with carries, digity by digit  
2. join the digits, convert to a number, add one, convert to string, split. We'd need to use bigint for this, as it's up to 100 digits  
  
Let's just do math manually  
Runtime complexity:  
O(N) in the number of digits  
also: O(log(N)) in the number represented by those digits  
extra space complexity: O(1)  
[3:25] Done planning  
[11:09] Done with initial implementation  
[15:28] Done with tests  
[15:46] Successful on first submission  
*/  
function plusOne(digits: number[]): number[] { // [4]; [9,9]  
  const length: number = digits.length // 1; 2  
  const smallestDigit: number = length - 1 // 0; 1  
  let carry: number = 1  
  for (let i = smallestDigit; i >= 0; i--) {  
    const newValue: number = digits[i] + carry // 5; 9 + 1 = 10; 9 + 1 = 10  
    if (newValue === 10) {  
      digits[i] = 0 // [0, 0]; [9, 0]  
      carry = 1 // 1; 1  
    } else {  
      digits[i] = newValue // 5  
      carry = 0 // 0  
    }  
  }  
  if (carry) {  
    digits.unshift(1) // [1, 0, 0]  
  }  
  return digits // [5]; [1,0,0]  
};