Given a non-negative number represented as an array of digits, add 1 to the number ( increment the number represented by the digits ). The digits are stored such that the most significant digit is the first element of the array.
Examples :
Input : [1, 2, 4] Output : [1, 2, 5]
Input : [9, 9, 9] Output : [1, 0, 0, 0]
Approach: To add one to the number represented by digits, follow the below steps :
- Parse the given array from the end as we do in school addition.
- If the last elements are 9, make it 0 and carry = 1.
- For the next iteration check carry and if it adds to 10, do the same as step 2.
- After adding carry, make carry = 0 for the next iteration.
- If the vectors add and increase the vector size, append 1 in the beginning.
Below is the implementation to add 1 to the number represented by digits.
Output
1 7 9 0
Time Complexity: O(n), where n is the size of the array.
Auxiliary Space: O(1)
Another Approach:
Start from the end of the vector and if the last element is 9 set it to 0, else exit the loop.
- If the loop set all digits to 0 (if all digits were 9) insert 1 at the beginning.
- Else increment the element at the position where the loop stopped.
- No carry/division/modulo is needed.
Below is the implementation:
C++
#include <iostream> #include <vector> using namespace std; void AddOne(vector<int>& digits) { // initialize an index (digit of units) int index = digits.size() - 1; // while the index is valid and the value at [index] == // 9 set it as 0 while (index >= 0 && digits[index] == 9) digits[index--] = 0; // if index < 0 (if all digits were 9) if (index < 0) // insert an one at the beginning of the vector digits.insert(digits.begin(), 1, 1); // else increment the value at [index] else digits[index]++; } // Driver code int main() { vector<int> digits{ 1, 7, 8, 9 }; AddOne(digits); for (int digit : digits) cout << digit << ' '; return 0; } // This code is contributed // by Gatea David |
Java
// Java implementation for Adding one // to number represented by digits import java.io.*; import java.util.*; class GFG { static void AddOne(Vector<Integer> digits) { // initialize an index (digit of units) int index= digits.size() - 1; // while the index is valid and the value at [index] == // 9 set it as 0 while (index >= 0 && digits.get(index) == 9){ digits.set(index, 0); index -= 1; } // if index < 0 (if all digits were 9) if (index < 0){ // insert an one at the beginning of the vector digits.set(0, 1); //Add one extra zero at the end of the vector digits.add(digits.size(),0); } // else increment the value at [index] else digits.set(index, digits.get(index) + 1); } // Driver code public static void main(String[] args) { Vector<Integer> digits = new Vector<Integer>(Arrays.asList(1,7,8,9)); AddOne(digits); for (int digit : digits) System.out.print(digit + " "); } } // This code is contributed by Shubham Singh |
Python3
#Python Program def AddOne(digits): # initialize an index (digit of units) index = len(digits) - 1 # while the index is valid and the value at [index] == # 9 set it as 0 while (index >= 0 and digits[index] == 9): digits[index] = 0 index -= 1 # if index < 0 (if all digits were 9) if (index < 0): # insert an one at the beginning of the vector digits.insert(0, 1) # else increment the value at [index] else: digits[index]+=1 digits = [1, 7, 8, 9] AddOne(digits) for digit in digits: print(digit, end =' ') # This code is contributed # by Shubham Singh |
C#
// C# implementation for adding one // to number represented by digits using System; using System.Xml; class GFG{ // Driver code static void Main(string[] args) { int[] digits = new int[] { 1, 7, 8, 9 }; // Initialize an index (digit of units) int index = digits.Length - 1; // While the index is valid and the value at // [index] == 9 set it as 0 while (index >= 0 && digits[index] == 9) digits[index--] = 0; // If index < 0 (if all digits were 9) if (index < 0) { // Insert an one at the beginning of the vector Array.Resize(ref digits, index + 1); digits[0] = 1; } // Else increment the value at [index] else digits[index]++; foreach(int digit in digits) Console.Write(digit + " "); } } // This code is contributed by Shubham Singh |
Javascript
<script> // JavaScript implementation for Adding one // to number represented by digits // function for adding one to number const AddOne = (digits) => { // initialize an index (digit of units) let index = digits.length -1; // while the index is valid and the value at [index] == // 9 set it as 0 while (index >= 0 && digits[index] == 9) digits[index--] = 0; // if index < 0 (if all digits were 9) if (index < 0) // insert an one at the beginning of the vector digits.insert(digits.begin(), 1, 1); // else increment the value at [index] else digits[index]++; } // driver code let digits = [ 1, 7, 8, 9 ]; AddOne(digits); for (let i = 0; i < digits.length; i++) document.write(`${digits[i]} `); // This code is contributed by Shubham Singh </script> |
Go
// Golang implementation for Adding one // to number represented by digits package main import "fmt" // function to add one digit based on diff scenarios func plusOne(digits []int) []int { // initialize an index (i) (digit of units) i := len(digits) - 1 // while the index is valid and the value at [i] == // 9 set it as 0 and move index to previous value for i >= 0 && digits[i] == 9 { digits[i] = 0 i-- } if i < 0 { //leveraging golang's simplicity with append internal method for array return append([]int{1}, digits...) } else { digits[i]++ } return digits } //Driver code func main() { //slice with non-negative numbers given as input s := []int{9, 9, 9, 9, 9} //calling plusOne function and printing the result fmt.Println(plusOne(s)) } // This code is contributed by Mayur |
Output
1 7 9 0
Time Complexity: O(n), where n is the number of digits.
Auxiliary Space: O(1)
Another Approach:
In this approach we first reverse the original array then we take a carry variable to store the carry value.
Now we start iterating over the array from the start and we simply add 1 and carry to the value of that array at that index. After this we are going to check if the value of that index is it greater than 9 then we can take carry as the ten’s value and the value at that index in the array will the value present at the one place else we simply move on.
if digits[i]>9 then carry = digits[i]/10 and digits[i]%=10 if digits[i]<=9 then carry = 0.
We keep on doing this until we reach the last of the array. Now after coming out also if carry is not zero then we need to simply add that 1 to the array also and then again reverse the array so that we get our original array.
Implementation :
C++
// This Code represents one more approach to // Add 1 to the number represents in the array. // This code is contributed by Omkar Subhash Ghongade. #include<bits/stdc++.h> using namespace std; void plus_one(vector<int> &digits,int n) { // We are reversing the original arr // So that we need to iterate from Back. reverse(digits.begin(),digits.end()); // Taking a carry variable in case if there is any carry int carry=0; for(int i=0;i<n;i++) { // initially carry is 0 so this is base case if(i==0) digits[i]+=(1+carry); // If carry is not equal to zero it should be added to // array element at that position. else if(carry!=0) digits[i]+=carry; // Now to get carry, i.e. // If digits[i]>9 we get the value at tens place in carry // or else if digits[i]<9 carry will be 0 carry=digits[i]/10; // Now if carry is not equal to 0 // so at that index we should keep the value present // at the ones place so we get digits[i]%10 if(carry!=0) digits[i]=digits[i]%10; } // After doing all that if carry is still there which means // one more element is needed to be added to the array if(carry!=0) digits.push_back(carry); // Now we reverse the array so that we get the final array reverse(digits.begin(),digits.end()); } int main() { vector<int> digits={9,8,9,9}; int n=digits.size(); plus_one(digits,n); for(int i=0;i<digits.size();i++) { cout<<digits[i]<<" "; } } |
Java
// This Code represents one more approach to // Add 1 to the number represents in the array. // This code is contributed by Omkar Subhash Ghongade. import java.io.*; import java.util.*; class GFG { public static void plus_one(Vector<Integer> digits,int n) { // We are reversing the original arr // So that we need to iterate from Back. Collections.reverse(digits); // Taking a carry variable in case if there is any carry int carry = 0; for(int i = 0; i < n; i++) { // initially carry is 0 so this is base case if(i == 0) digits.set(i, digits.get(i) + 1 + carry); // If carry is not equal to zero it should be added to // array element at that position. else if(carry != 0) digits.set(i, digits.get(i) + carry); // Now to get carry, i.e. // If digits[i]>9 we get the value at tens place in carry // or else if digits[i]<9 carry will be 0 carry = digits.get(i) / 10; // Now if carry is not equal to 0 // so at that index we should keep the value present // at the ones place so we get digits[i]%10 if(carry != 0) digits.set(i, digits.get(i) % 10); } // After doing all that if carry is still there which means // one more element is needed to be added to the array if(carry != 0) digits.set(digits.size() - 1, carry); // Now we reverse the array so that we get the final array Collections.reverse(digits); } public static void main (String[] args) { Vector<Integer> digits = new Vector<Integer>(Arrays.asList(9,8,9,9)); int n = digits.size(); plus_one(digits, n); for(int i = 0; i < n; i++) { System.out.print(digits.get(i) + " "); } } } // This code is contributed by Shubham Singh |
Python3
# This Code represents one more approach to # Add 1 to the number represents in the array. def plus_one(digits, n): # We are reversing the original arr # So that we need to iterate from Back. digits.reverse() # Taking a carry variable in case if there is any carry carry = 0 for i in range(n): # initially carry is 0 so this is base case if(i == 0): digits[i] += (1 + carry) # If carry is not equal to zero it should be added to # array element at that position. elif(carry != 0): digits[i] += carry # Now to get carry, i.e. # If digits[i]>9 we get the value at tens place in carry # or else if digits[i]<9 carry will be 0 carry = digits[i]//10 # Now if carry is not equal to 0 # so at that index we should keep the value present # at the ones place so we get digits[i]%10 if(carry != 0): digits[i] = digits[i] % 10 # After doing all that if carry is still there which means # one more element is needed to be added to the array if(carry != 0): digits.append(carry) # Now we reverse the array so that we get the final array digits.reverse() # Driver code digits = [9, 8, 9, 9] n = len(digits) plus_one(digits, n) for i in digits: print(i, end =" ") # This code is contributed # by Shubham Singh |
C#
// This Code represents one more approach to // Add 1 to the number represents in the array. using System; public class GFG{ public static void Main () { int[] digits = new int[] {9,8,9,9}; int n = digits.Length; // We are reversing the original arr // So that we need to iterate from Back. Array.Reverse(digits); // Taking a carry variable in case if there is any carry int carry = 0; for(int i = 0; i < n; i++) { // initially carry is 0 so this is base case if(i == 0) digits[i] = digits[i] + 1 + carry; // If carry is not equal to zero it should be added to // array element at that position. else if(carry != 0) digits[i] = digits[i] + carry; // Now to get carry, i.e. // If digits[i]>9 we get the value at tens place in carry // or else if digits[i]<9 carry will be 0 carry = digits[i] / 10; // Now if carry is not equal to 0 // so at that index we should keep the value present // at the ones place so we get digits[i]%10 if(carry != 0) digits[i] = digits[i]%10; } // After doing all that if carry is still there which means // one more element is needed to be added to the array if(carry != 0) digits[digits.Length -1] = carry; // Now we reverse the array so that we get the final array Array.Reverse(digits); for(int i = 0; i < n; i++) { Console.Write(digits[i] + " "); } } } // This code is contributed by Shubham Singh |
Javascript
<script> // This Code represents one more approach to // Add 1 to the number represents in the array. var digits = [9,8,9,9]; var n = digits.length; // We are reversing the original arr // So that we need to iterate from Back. digits.reverse(); // Taking a carry variable in case if there is any carry var carry = 0; for(var i = 0; i < n; i++) { // initially carry is 0 so this is base case if(i == 0) digits[i] = digits[i] + 1 + carry; // If carry is not equal to zero it should be added to // array element at that position. else if(carry != 0) digits[i] = digits[i] + carry; // Now to get carry, i.e. // If digits[i]>9 we get the value at tens place in carry // or else if digits[i]<9 carry will be 0 carry = parseInt(digits[i] / 10); // Now if carry is not equal to 0 // so at that index we should keep the value present // at the ones place so we get digits[i]%10 if(carry != 0) digits[i] = digits[i]%10; } // After doing all that if carry is still there which means // one more element is needed to be added to the array if(carry != 0) digits[digits.length -1] = carry; // Now we reverse the array so that we get the final array digits.reverse(); for(var i = 0; i < n; i++) { document.write(digits[i] + " "); } // This code is contributed by Shubham Singh </script> |
Output
9 9 0 0
Time Complexity: O(n log n), where n is the size of the array.
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
