In this problem, We have given a non-empty array which represents a non-negative integer. Write a code to add one to the number.
Each element in the array contain a single digit. You may assume the integer does not contain any leading zero, except the number 0 itself.
Example 1 –
Input: [1, 3, 4]
Output: [1, 3, 5]
In this example, the array represents the number 134. When we add 1 to it, the new number is 135.
Example 2 –
Input : [1, 2, 9]
Output: [1, 3, 0]
The number is 129. When we add 1 to 129. The new number is 130.
Example 3 –
Input : [9, 9, 9]
Output: [1, 0, 0, 0]
For the number 999, when you add 1, the new number would be 1000. If you think in terms of array, the new array size would be the previous array size plus one.
We have discussed the problem statement with multiple examples. Let’s think how you can solve this problem efficiently.
At the end of this tutorial, I have mentioned the video tutorial link.
Add One to Number Represented as Array – Java Code
To solve this problem, we have to traverse an array from end.
If the digit is not equal to 9 then we can simply add 1 to a digit present at that index and simply return the array. Else if it is 9 in that case we have to put 0 at that index and repeat this process until digit is not equal to 9.
There is one more case which we need to handle when all the elements of an array is 9, in that case we have to increase an array size by 1. The first element of the new array is 1 and rest all are zeroes.
The time complexity of this approach is O(n) and it’s space complexity is also O(n).
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 |
// Add One to Number Represented as Array - Java Code public class PlusOne { public static int[] plusOne(int[] digits) { int i = digits.length-1; while(i >= 0) { if(digits[i] != 9) { digits[i] = digits[i] + 1; return digits; } digits[i] = 0; i--; } int[] res = new int[digits.length + 1]; res[0] = 1; return res; } public static void main(String[] args) { int[] digits = {1, 2, 9}; //Method call to add 1 plusOne(digits); System.out.println(Arrays.toString(digits)); } } |
Programming questions on Binary Search
Programming questions on Linked List
Programming questions on Sliding window
Plus One LeetCode Solution
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
//Plus one leetcode solution public int[] plusOne(int[] digits) { int i = digits.length-1; while(i >= 0) { if(digits[i] != 9) { digits[i] = digits[i] + 1; return digits; } digits[i] = 0; i--; } int[] res = new int[digits.length + 1]; res[0] = 1; return res; } |
