Adding one to number represented as array of digits

Add 1 to a non-negative number that is represented by an array of digits to increase the number that the digits represent. The digits are stored so that the array’s first entry is the most significant digit.

Examples : 

Input : [1, 2, 4]
Output : [1, 2, 5]

Input : [9, 9, 9]
Output : [1, 0, 0, 0]

Method: Take the actions listed below to add one to the number that is represented by the digits:

• As in addition class, parse the provided array from the end.
• Make it zero and carry = one if the final elements are nine.
• Repeat step 2 for the subsequent iteration and check carry to see whether it amounts to 10.
• Make carry = 0 for the following iteration after adding carry.
• Append 1 at the start if the vectors sum and enlarge the vector size.
• The implementation of adding 1 to the number represented by the digits is shown below.

Output

1 7 9 0 

Time Complexity: O(n), where n is the size of the array.

Auxiliary Space: O(1)

An alternative method is to begin at the end of the vector and set the last element to 0 if it is 9, otherwise break the loop.

• Insert 1 at the start if the loop sets all the digits to 0 (if all the digits were 9).
• If not, increment the element at the loop’s termination point.
• There is no requirement for a carry, division, or module.
• The implementation is shown below:

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

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