Adding one to the number represented an array of digits
You have given one array, which consists of values which represent the different digits of a number. You have to add 1 to this number and store the result in the same array. It is confirmed that in the array the digits are stored such that the most significant digit is the first element of the array.
Let’s take an example -
Input- { 2, 3, 4 }
Output- { 2, 3, 5 }
Explanation- If we take number 2,3,4 in an array and add 1 to this number, we will get the result 2,3,5.
Algorithm:-
Step 1: Start
Step 2: An array is created of size n. Then values of the array are taken from the user.
Step 3: The values of array elements are taken from the user.
Step 4: A function is called to calculate the answer.
Step 5: In this function, we take the array.
Step 6: This function processes all the array elements by checking carry and sum and returns the calculated sum.
Step 7: The value of the answer is returned.
Step 8: The returned value will be printed.
Step 9: Stop.
Explanation of Algorithm: - Here, we will think about two things. The first one is the sum of two digits and the second one is carry. Let's understand the solution by an example. We are going to add one with the value 99. So, first, we will check from the last element of the array. We will add 1 with the number. If the sum is 10, the carry will be 1, and if less than 10, then the carry will be 0. We will traverse all the array elements and will add 1 if the carry is 1.
Code: -
Program in CPP
// program in CPP to add one to the number in array.
#include <bits/stdc++.h>
using namespace std;
void incrementVector(vector<int>& a)
{
int n = a.size();
a[n - 1] += 1;
int carry = a[n - 1] / 10;
a[n - 1] = a[n - 1] % 10;
for (int i = n - 2; i >= 0; i--) {
if (carry == 1) {
a[i] += 1;
carry = a[i] / 10;
a[i] = a[i] % 10;
}
}
if (carry == 1)
a.insert(a.begin(), 1);
}
int main()
{
vector<int> vect{ 1, 7, 8, 9 };
incrementVector(vect);
for (int i = 0; i < vect.size(); i++)
cout << vect[i] << " ";
return 0;
}
Program in Java
// program in java to add one to the number in the array.
import java.io.*;
import java.util.*;
class jtp {
static void incrementVector(Vector<Integer> a)
{
int n = a.size();
a.set(n - 1, a.get(n - 1) + 1);
int carry = a.get(n - 1) / 10;
a.set(n - 1, a.get(n - 1) % 10);
for (int i = n - 2; i >= 0; i--) {
if (carry == 1) {
a.set(i, a.get(i) + 1);
carry = a.get(i) / 10;
a.set(i, a.get(i) % 10);
}
}
if (carry == 1)
a.add(0, 1);
}
public static void main(String[] args)
{
Vector<Integer> vect = new Vector<Integer>();
vect.add(1);
vect.add(7);
vect.add(8);
vect.add(9);
incrementVector(vect);
for (int i = 0; i < vect.size(); i++)
System.out.print(vect.get(i) + " ");
}
}
Program in Python
# Program in python to add one to the number in the array.
import math
def incrementVector(a):
n = len(a)
a[n-1] += 1
carry = a[n-1]/10
a[n-1] = a[n-1] % 10
for i in range(n-2, -1, -1):
if (carry == 1):
a[i] += 1
carry = a[i]/10
a[i] = a[i] % 10
if (carry == 1):
a.insert(0, 1)
vect = [1, 7, 8, 9]
incrementVector(vect)
for i in range(0, len(vect)):
print(vect[i], end=" ")
Program in JavaScript
// program in javascript to add one to the number in array.
<script>
const incrementVector = (a) =>
{
let n = a.length;
a[n - 1] += 1;
let carry = parseInt(a[n - 1] / 10);
a[n - 1] = a[n - 1] % 10;
for (let i = n - 2; i >= 0; i--) {
if (carry == 1) {
a[i] += 1;
carry = parseInt(a[i] / 10);
a[i] = a[i] % 10;
}
}
if (carry == 1)
a.unshift(1);
}
let vect = [ 1, 7, 8, 9 ];
incrementVector(vect);
for (let i = 0; i < vect.length; i++)
document.write(`${vect[i]} `);
</script>
Output:
[ 1, 7, 9, 0 ]
Complexity Analysis: -
Time complexity- Here, we need looping. For traversing the array, n time will be taken. So, we can find the solution within n time. Time complexity will be O(n).
Space complexity- Here, we need only constant memory. So, space complexity will be O(1).