PROBLEM LINK:
Author: aniket_111
Tester: sahoomirnalin
Editorialist: aniket_111
DIFFICULTY:
Simple
PREREQUISITES:
Basic observations, array.
PROBLEM:
Chef has a large integer and for storing it he has used an integer array named 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. Chef wants to increment the large integer by one and return the resulting array of digits.
EXPLANATION
Traverse digits from the last element (least significant)
Since we begin with the last digit, increasing that digit by one it results in overflow. Therefore, all elements PRIOR to digits[0] need to be considered since there may be additional nines between → digits[0], … , digits[n].
if (digits[i] == 9) {
digits[i] = 0;
}
else {
//As current digit is not 9 so we can safely increment by one
digits[i] += 1;
return digits;
}
If carry exists, To get a correct solution, we need to add one more element with a value of zero AND set digits[0] to 1 (in the most significant position) to account for the carry digit.
TIME COMPLEXITY
Time complexity is O(n) per test case
Space Complexity O(1) space.
SOLUTIONS:
#include <bits/stdc++.h>
#include<vector>
using namespace std;
vector<int> plusOne(vector<int>& digits) {
int n=digits.size();
for(int i=n-1;i>=0;i--){
if(digits[i]<9){
digits[i]++;
return digits;
}
else
digits[i]=0;
}
digits.insert(digits.begin(),1);
return digits;
}
int main() {
int t,n,a;
vector<int> ans;
cin>>t;
while(t--){
cin>>n;
vector<int> arr;
for(int i=0;i<n;i++){
cin>>a;
arr.push_back(a);
}
ans=plusOne(arr);
for(auto i:ans){
cout<<i<<" ";
}
cout<<endl;
ans={};
}
return 0;
}