100 Days to crack FAANG interview Day 3 — Plus One
Welcome to Day 3 of my FAANG/MAANG interview preparation journey! Today, I’ve chosen an easy problem again, but this time I’m moving from String topic to Arrays.
Problem Statement
Plus One — https://leetcode.com/problems/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.
Approach
This question brought back memories of how I used to do additions when I was a kid. It’s a fairly straightforward problem, we can perform an in-place addition by adding 1 to the last index. If the result is more than 10, we maintain a carry and add it to the previous cell. This process is continued till the carry is 0.
One edge case to consider is when the input consists of all nines. In this scenario, the array size will increase by one, so in-place modification won’t work. We’ll need to initialise a new array to accommodate the new digit. Either, check for this case in the beginning or at the end.
Code Implementation
class Solution {
public int[] plusOne(int[] digits) {
int carry = 1;
for(int i = digits.length-1; i>=0; i--){
carry = digits[i] + carry;
digits[i] = carry % 10;
carry = carry / 10;
if(carry == 0) return digits;
}
//carry will be 1 here, so initialise a new array
int[] nums = new int[digits.length+1];
nums[0] = 1;
return nums;
}
}
Approach 2
Since, this problem was easy and I was able to solve it quickly, I’m going to make it challenging by implementing a plusK algorithm. In this approach, instead of simply adding 1, k will be added to the input digits. This methos will be used to solve the original plusOne problem. To implement this, I’ll be using ArrayList instead of performing an in-place update.
Code Implementation
public static int[] plusK(int[] digits, int k) {
List<Integer> result = new ArrayList<>();
int carry = k;
for(int i=digits.length-1;i>=0;i--){
carry = digits[i] + carry;
result.add(0, carry%10);
carry = carry/10;
}
while(carry>0){
result.add(0, carry%10);
carry = carry/10;
}
return result.stream().mapToInt(Integer::intValue).toArray();
}
public int[] plusOne(int[] digits) {
return plusK(digits, 1);
}
My FAANG interview journey — https://www.100daysofcode.io/faang-interview-guide
If you have any feedback or suggestions, please feel free to share. Your input is valuable as I continue on this journey.