Google Interview Question
Software Engineer / DevelopersCountry: United States
It could be better. don't need the "carry", and don't need "%" in the loop. I write it by java.
public int[] Add1(int[] a){
for(int i=a.length-1; i>=0; i++){
if(a[i]==9){
a[i]=0;
if(i==0){
int[] new_array=new int[a.length+1];
new_array[0]=1;
for(int j=1;j<a.length+1;j++){
new_array[j]=a[j-1];
return new_array;
}
}
}
else{
a[i]+=1;
break;
}
}
return a;
}
Some changes on @nihaldps' code.
1. Remove the use of the modulus operator %.
2. Remove the use of the result array.
#include <stdio.h>
void increment_by_one(int a[], int n)
{
int i;
int carry;
carry = 1;
for (i = n - 1; i >= 0; i--) {
a[i] += carry;
if (a[i] >= 10) {
carry = 1;
a[i] = 0;
} else {
carry = 0;
}
}
if (carry == 1)
printf("%d", carry);
for (i = 0; i < n; i++)
printf("%d", a[i]);
printf("\n");
}
int main()
{
int a[4] = {9,9,9,9};
increment_by_one(a, 4);
int b[] = {2, 7, 8, 9};
increment_by_one(b, 4);
int c[] = {2, 8, 1};
increment_by_one(c, 3);
return 0;
}
int aaaa[5]={0,0,0,0,0};
void arrayplusplus()
{
bool carry=1;
int i=4;
do{
if(carry==1)
{
aaaa[i]++;
}
if(aaaa[i]>9)
{
carry=1;
aaaa[i]=aaaa[i]%10;
}
else
{
carry=0;
}
}while(--i>=0);
printf("%d%d%d%d%d\n",aaaa[0],aaaa[1],aaaa[2],aaaa[3],aaaa[4]);
}
public class NewClass {
public static void main(String[] args) {
int[] nums={9,9,3,9};
int[] fin=new int[nums.length+1];
int carry=0;
nums[nums.length-1]++;
for(int i=nums.length-2;i>=0;i--){
carry=nums[i+1]/10;
nums[i]=nums[i]+carry;
fin[i+1]=nums[i]%10;
}
fin[0]+=nums[0]/10;
for(int i=0;i<fin.length;i++)
System.out.print(fin[i]+" ");
}
}
I am assuming if this is a google interview question there has to be another way of doing things.
I propose not using multiplications and divisions at all which are the slowest arithmetic operations.
We maintain a map such that 0 to 9 charactres are stored. There is a method next(i) which simply returns the next digit from the map. Remember it is a character. The start from unit place (RHS) and simply call next(i). if next(9) is called it returns a 0. Which means we continue to move towards left doing the same.
After calling next(9) if we get a 0 then we call next(i+1) for the next element towards the left since the only possible carry is 1.
void plusPlusArray (std::vector<int>& array)
{
int carry=1;
int sum=0;
for(int i=array.size()-1; i>=0; i--)
{
sum = array[i] + carry;
array[i] = (int) sum%10;
carry = sum/10;
if(carry == 0)
{
break;
}
}
if(carry)
{
// additional digit to be added
array.insert ( array.begin(), carry );
}
}
1) Basic sanity checks need to be done & dealt with accordingly: e.g. Any zeroes at the beginning of input array
2) Problem says it is integer array => Assuming no negative numbers
Please correct me if I am doing anything wrong or missing anything.
void incrementArr(int arr[], int length)
{
if(arr[length-1] == 9)
{
arr[length-1] = 0;
length--;
incrementArr(arr, length);
}
else{ arr[length-1]++; }
}
int main()
{
int arr[] = {2,7,8,9};
int arrLength = sizeof(arr)/sizeof(int);
incrementArr(arr, arrLength);
for(int i = 0; i < arrLength; i++)
{
cout << arr[i];
}
}
can handle negative by checking first index and reversing operation
string nextNumber (string str){
if(str==NULL)
return str;
int pos = str.length();
int carry = 0;
while(pos>=0){
if(!isnum(str[pos]))
return NULL;
if(str[pos] == '9') {
str[pos] = 0;
if(pos==0){
str.resize(str.length+1);
str.insert(0,0); //insert 0 at the first position which will be incremented in the next iteration
}
else pos--; //decrement only if pos != 0
}
else{
str[pos]++;
break;
}
}
return str;
}
Trying to avoid checking conditions and multiplications and divisions!
But one more extra space is wasted!! Tried hard to find some another soln. without wasting the space! But failed any helped will be appreciated.
#include <stdio.h>
#include <stdlib.h>
int next[] = {1,2,3,4,5,6,7,8,9,0};
int* getPlusPlus (int arr[], int len, int* res_len) {
int i, carry = 1, nextnum ;
int *result = (int *) malloc (sizeof(int) * (*res_len=(len+1))) ;
for ( i = len-1, nextnum = i+1 ; i >= 0 ; i -- ) {
if ( arr[i] != 9 ) {
carry = 0 ;
break ;
}
result[nextnum] = next[arr[i]] ;
nextnum = i ;
}
if ( carry )
result[0] = 1 ;
else {
result[nextnum] = next[arr[i]] ;
for ( nextnum = i , i-- ; i >= 0 ; nextnum = i, i -- )
result[nextnum] = arr[i] ;
(*res_len) -- ;
return ++result ;
}
return result ;
}
int main () {
int arr[] = {9, 9, 8, 7};
int i, *result, len ;
result = getPlusPlus (arr, 4, &len) ;
for ( i = 0 ; i < len ; i ++ )
printf ( "%d ", result[i] ) ;
printf ( "\n" ) ;
return 0 ;
}
void plusPlusArray (std::vector<int>& array)
{
int carry=1;
int sum=0;
for(int i=array.size()-1; i>=0; i++)
{
sum = array[i] + carry;
array[i] = (int) sum%10;
carry = sum/10;
if(carry == 0)
{
break;
}
}
if(carry)
{
// additional digit to be added
array.insert ( array.begin(), carry );
}
}
1) Basic sanity checks need to be done & dealt with accordingly: e.g. Any zeroes at the beginning of input array
2) Problem says it is integer array => Assuming no negative numbers
Please correct me if I am doing anything wrong or missing anything.
#include<iostream>
using namespace std;
class array
{
public:
int *a;
int s;
array()
{
cout<<"Enter the size of array : ";
cin>>s;
a = new int[s];
cout<<"Enter the array : ";
for(int i = 0; i<s; i++)
{
while(true)
{
cin>>a[i];
if(a[i]>=0 && a[i]<10)
break;
cout<<"Renter this digit please :";
}
}
}
void operator++();
void show()
{
for(int i=0; i<s; i++)
cout<<a[i]<<",";
}
};
void array::operator++()
{
int carry = 1;
int i=s;
for(; i>=0; i--)
{
if(a[i] + carry <=9)
{
a[i] += carry;
carry = 0;
i = -99;
}
else
a[i] = 0;
}
if(carry == 1 && i ==-1)
{
s++;
for(int i=s-1; i>0; i--)
a[i] = a[i-1];
a[0] = 1;
}
}
int main()
{
array arr;
++arr;
cout<<"The ++array is :";
arr.show();
return 0;
}
public static void main(String[] args) {
Integer[] input = {9,8,9,9};
Integer[] output = plus(input);
for (int i=0; i<output.length; i++){
System.out.print(output[i] + " ");
}
}
private static Integer[] plus(Integer[] input) {
int carryFlag = 1;
for (int i=input.length - 1; i >= 0; i--){
if (input[i]==9 && carryFlag==1){
if (i==0){
return makeNewArray(input.length);
}
else{
input[i]=0;
}
} else if (carryFlag == 1){
carryFlag = 0;
input[i]++;
}
}
return input;
}
private static Integer[] makeNewArray(int length) {
Integer[] output = new Integer[length+1];
output[0] = 1;
for (int i=1; i<output.length; i++){
output[i] = 0;
}
return output;
}
void incrementArr(int arr[], int length)
{
if(arr[length-1] == 9)
{
arr[length-1] = 0;
length--;
incrementArr(arr, length);
}
else{ arr[length-1]++; }
}
int main()
{
int arr[] = {2,7,8,9};
int arrLength = sizeof(arr)/sizeof(int);
incrementArr(arr, arrLength);
for(int i = 0; i < arrLength; i++)
{
cout << arr[i];
}
}
can handle negative by checking first index and reversing operation
void incrementArr(int arr[], int length)
{
if(arr[length-1] == 9)
{
arr[length-1] = 0;
length--;
incrementArr(arr, length);
}
else{ arr[length-1]++; }
}
int main()
{
int arr[] = {2,7,8,9};
int arrLength = sizeof(arr)/sizeof(int);
incrementArr(arr, arrLength);
for(int i = 0; i < arrLength; i++)
{
cout << arr[i];
}
}
can handle negative by checking first index and reversing operation
there are 3 important cases:
Inc(new int[] { 1, 2, 3, 4 }); //1235
Console.WriteLine();
Inc(new int[] {2, 7, 8, 9 }); //2790
Console.WriteLine();
Inc(new int[] { 9, 9, 9, 9 }); //10000
Code in C#:
private static void Inc(int[] a)
{
int len = a.Length;
if (a[len - 1] + 1 <= 9)
{
a[len - 1] = a[len - 1] + 1;
Display(a, len);
}
else
{
int i = len - 1;
a[i] = 0;
int carry = 1;
i--;
while (i >= 0)
{
int sum = a[i] + carry;
a[i] = sum % 10;
carry = sum / 10;
i--;
}
if (carry == 1)
{
//insert 1 carry at the beginning of the array
int j = len;
int[] b = new int[len + 1];
while (j >= 1)
{
b[j] = a[j - 1];
j--;
}
b[0] = carry;
len++;
Display(b, len);
}
else
{
Display(a, len);
}
}
}
there are 3 important cases:
Inc(new int[] { 1, 2, 3, 4 }); //1235
Console.WriteLine();
Inc(new int[] {2, 7, 8, 9 }); //2790
Console.WriteLine();
Inc(new int[] { 9, 9, 9, 9 }); //10000
Code in C#:
private static void Inc(int[] a)
{
int len = a.Length;
if (a[len - 1] + 1 <= 9)
{
a[len - 1] = a[len - 1] + 1;
Display(a, len);
}
else
{
int i = len - 1;
a[i] = 0;
int carry = 1;
i--;
while (i >= 0)
{
int sum = a[i] + carry;
a[i] = sum % 10;
carry = sum / 10;
i--;
}
if (carry == 1)
{
//insert 1 carry at the beginning of the array
int j = len;
int[] b = new int[len + 1];
while (j >= 1)
{
b[j] = a[j - 1];
j--;
}
b[0] = carry;
len++;
Display(b, len);
}
else
{
Display(a, len);
}
}
}
public int[] arrayIncrement(int[] number, int increment)
{
int length = number.length;
int carry = increment;
int i = length - 1;
while(i >= 0)
{
number[i] = number[i] + carry;
if(number[i] >= 10)
{
carry = 1;
number[i] = number[i] % 10;
}
else
carry = 0;
i--;
}
if(carry == 0)
return number;
else
{
int[] result = new int[length + 1];
result[0] = 1;
int index = 1;
for(int num : number)
result[index++] = num;
return result;
}
}
string nextNumber (string str){
if(str==NULL)
return str;
int pos = str.length();
int carry = 0;
while(pos>=0){
if(!isnum(str[pos]))
return NULL;
if(str[pos] == '9') {
str[pos] = 0;
if(pos==0){
str.resize(str.length+1);
str.insert(0,0); //insert 0 at the first position which will be incremented in the next iteration
}
else pos--; //decrement only if pos != 0
}
else{
str[pos]++;
break;
}
}
return str;
}
string nextNumber (string str){
if(str==NULL)
return str;
int pos = str.length();
int carry = 0;
while(pos>=0){
if(!isnum(str[pos]))
return NULL;
if(str[pos] == '9') {
str[pos] = 0;
if(pos==0){
str.resize(str.length+1);
str.insert(0,0); //insert 0 at the first position which will be incremented in the next iteration
}
else pos--; //decrement only if pos != 0
}
else{
str[pos]++;
break;
}
}
return str;
}
string nextNumber (string str){
if(str==NULL)
return str;
int pos = str.length();
int carry = 0;
while(pos>=0){
if(!isnum(str[pos]) && pos > 0) //first char can be '-'
return NULL;
if(str[pos] == '9') {
if(str[0] == '-') {
str[pos]--;
pos--;
}
else{
str[pos] = 0;
if(pos==0){
str.resize(str.length+1);
str.insert(0,0); //insert 0 at the first position which will be incremented in the next iteration
}
else pos--; //decrement only if pos != 0
}
} // shut the first else after checking for negative number
else{
if(str[0] == '-' && str[pos] == '0') {
if(pos == 1){
string str1 = "-";
str1.append(str.begin()+2, str.end);
str = str1; break;
}
str[pos] = 9;
pos--
}
else{
str[pos]++;
break;
}
}
}
return str;
}
string nextNumber (string str){
if(str==NULL)
return str;
int pos = str.length();
int carry = 0;
while(pos>=0){
if(!isnum(str[pos]) && pos > 0) //first char can be '-'
return NULL;
if(str[pos] == '9') {
if(str[0] == '-') {
str[pos]--;
pos--;
}
else{
str[pos] = 0;
if(pos==0){
str.resize(str.length+1);
str.insert(0,0); //insert 0 at the first position which will be incremented in the next iteration
}
else pos--; //decrement only if pos != 0
}
} // shut the first else after checking for negative number
else{
if(str[0] == '-' && str[pos] == '0') {
if(pos == 1){
string str1 = "-";
str1.append(str.begin()+2, str.end);
str = str1; break;
}
str[pos] = 9;
pos--
}
else{
str[pos]++;
break;
}
}
}
return str;
}
string nextNumber (string str){
if(str==NULL)
return str;
int pos = str.length();
int carry = 0;
while(pos>=0){
if(!isnum(str[pos]) && pos > 0) //first char can be '-'
return NULL;
if(str[pos] == '9') {
if(str[0] == '-') {
str[pos]--;
pos--;
}
else{
str[pos] = 0;
if(pos==0){
str.resize(str.length+1);
str.insert(0,0); //insert 0 at the first position which will be incremented in the next iteration
}
else pos--; //decrement only if pos != 0
}
} // shut the first else after checking for negative number
else{
if(str[0] == '-' && str[pos] == '0') {
if(pos == 1){
string str1 = "-";
str1.append(str.begin()+2, str.end);
str = str1; break;
}
str[pos] = 9;
pos--;
}
else{
str[pos]++;
break;
}
}
}
return str;
}
string nextNumber (string str){
if(str==NULL)
return str;
int pos = str.length();
int carry = 0;
while(pos>=0){
if(!isnum(str[pos]) && pos > 0) //first char can be '-'
return NULL;
if(str[pos] == '9') {
if(str[0] == '-') {
str[pos]--;
pos--;
}
else{
str[pos] = 0;
if(pos==0){
str.resize(str.length+1);
str.insert(0,0); //insert 0 at the first position which will be incremented in the next iteration
}
else pos--; //decrement only if pos != 0
}
} // shut the first else after checking for negative number
else{
if(str[0] == '-' && str[pos] == '0') {
if(pos == 1){
string str1 = "-";
str1.append(str.begin()+2, str.end);
str = str1; break;
}
str[pos] = 9;
pos--;
}
else{
str[pos]++;
break;
}
}
}
return str;
}
string nextNumber (string str){
if(str==NULL)
return str;
int pos = str.length();
int carry = 0;
while(pos>=0){
if(!isnum(str[pos]) && pos > 0) //first char can be '-'
return NULL;
if(str[pos] == '9') {
if(str[0] == '-') {
str[pos]--;
pos--;
}
else{
str[pos] = 0;
if(pos==0){
str.resize(str.length+1);
str.insert(0,0); //insert 0 at the first position which will be incremented in the next iteration
}
else pos--; //decrement only if pos != 0
}
} // shut the first else after checking for negative number
else{
if(str[0] == '-' && str[pos] == '0') {
if(pos == 1){
string str1 = "-";
str1.append(str.begin()+2, str.end);
str = str1; break;
}
str[pos] = 9;
pos--;
}
else{
str[pos]++;
break;
}
}
}
return str;
}
Sorry for typo mistakes in my previous post.
Whats the input : string or integer array?
If it is an integer array, then why cant we use a simple logic :
1 -> reverse the array
2- > start from index 0 and increment each index. if current digit is 9, add 1 for next iteration
3-> reverse the array again to get the required number
public int[] getNewArray(int[] arr) {
int size = arr.length -1;
for (int i = 0; i<=size; ++i) {
if((arr[size - i]+1) > 9) {
arr[size - i] = 0;
if (i == size) {
arr[0] = 1;
int newArr[] = new int[size+2];
newArr[0] = 1;
return newArr;
}
}
else {
arr[size - i] = arr[size - i] + 1;
break;
}
}
return arr;
}
public static void main(String[] args)
{
int[] arr = {8,9,9,9};
int[] res = getNewArray(arr);
for(int i = 0; i < res.length; ++i)
System.out.print(res[i]);
}
public void incrementNumber(int num[]) {
int[] result = new int[num.length];
int carry = 1;
for (int i = num.length - 1; i >= 0; i--) {
result[i] = num[i] + carry;
if (result[i] > 9) {
if (i == 0) {
result[i] = result[i] % 10;
result = incrementArray(result);
result[i] = 1;
} else {
result[i] = result[i] % 10;
carry = 1;
}
} else {
carry = 0;
}
}
for (int i = 0; i < result.length; i++) {
System.out.println(result[i] + " ");
}
}
public int[] incrementArray(int result[]) {
int[] newArray = new int[result.length + 1];
for (int i = result.length - 1; i >= 0; i--) {
newArray[i + 1] = result[i];
}
return newArray;
}
<?php
$input = array(9,9,9);
var_dump(arrayInc($input));
function arrayInc(&$input) {
$len = count($input);
$rem = 1;
$p1 = $len - 1;
while ($p1 >=0) {
$sum = $input[$p1] + $rem;
if ($sum >= 10) {
$input[$p1] = $sum - 10;
$rem = 1;
} else {
$input[$p1] = $sum;
$rem = 0;
}
$p1--;
}
if ($rem == 1) {
$input[0] += 10;
}
return $input;
}
?>
int[] incrementArray(int arr[], int size){
if(arr == null || size < 1)
return;
int i = size-1;
arr[i]++;
while( arr[i] > 9)
{
arr[i] = arr[i] - 9;
i--;
if ( i >= 0)
arr[i]++;
else{
int[] newArr = new int[size + 1];
newArr[0] = 1;
for (int j=1; j<size+1; j++)
newArr[j]=arr[j];
return newArr;
}
}
return arr;
}
I did not compile this but I think this is theoretically possible.
int temp, num[2,7,8,9];
char strbuf[100];
sprintf(strbuf,"%d%d%d%d",&num[0],&num[1],&num[2],&num[3]);
// now the number is stored in strbuf as an ascii string
temp = atoi(strbuf);
temp++;
// store incremented number as a string
sprintf(strbuf,"%d", temp);
sprintf(num,"%d%d%d%d",&strbuf[0],&strbuf[1],&strbuf[2],&strbuf[3]);
public static int[] incremented(int[] num)
{
if (num == null)
throw new NullReferenceException("null arguement");
else
{
int len = num.Length;
int inclen;
if (num[0] == 9)
{
if (num[1] == 9)
inclen = len + 1;
else
inclen = len;
}
else
inclen = len;
int[] increment = new int[inclen];
int index = inclen - 1;
int carry = 1;
int indexnum = len -1;
while (index >= 0)
{
if (indexnum < 0)
{
increment[index] = carry;
break;
}
increment[index] = (num[indexnum] + carry ) % 10;
carry = (num[indexnum] + carry) / 10;
index--;
indexnum--;
}
return increment;
}
}
int* arrayIncrement(int *arr, int &size)
{
int i, carry;
for(i=size-1, carry=1;carry==1&&i>=0;--i){
carry=(arr[i]+1)/10;
arr[i]=(arr[i]+1)%10;
}
if(i==-1&&carry==1){
int *n=new int[++size];
n[0]=1;
for(int j=1;j<size+1;++j)
n[j]=0;
return n;
}
return arr;
}
int main()
{
int arr[5]={9,9,9,9,9};
int size=5;
int *p=arrayIncrement(arr, size);
for(int i=0;i<size;++i)
cout<<p[i];
cout<<endl;
return 0;
}
#include<stdio.h>
#include<conio.h>
#define SIZE 100
void incre(int *,int,int);
int main()
{
int n,a[SIZE],carr,i;
clrscr();
printf("How many number you wanted to enter\n");
scanf("%d",&n);
printf("Enter the array \n");
for(i=0;i<n;i++)
scanf("%d",&a[i]);
printf("Enter carry \n");
scanf("%d",&carr);
incre(a,n,carr);
getch();
return 0;
}
void incre(int *a,int pos,int carry)
{
int i,temp;
for(i=pos-1;i>=0;i--)
{
temp=a[i]+carry;
if(temp>=10)
{
a[i]=temp%10;
carry=temp/10;
}
else
{
a[i]=temp;
carry=0;
}
}
if(carry>0)
{
for(i=pos-1;i>=0;i--)
{
a[i+1]=a[i];
}
a[++i]=carry;
printf("Your Array is\n");
for(i=0;i<=pos;i++)
printf("%d ",a[i]);
}
else
{
printf("Your Array is\n");
for(i=0;i<pos;i++)
printf("%d ",a[i]);
}
}
#include<stdio.h>
void inc(int a[],int size)
{
int i=0,k=0;
i=size-1;
while(i>0)
{
if(a[i] == 9)
{
a[i] = 0;
}
else
{
a[i] = a[i] + 1;
break;
}
i=i-1;
}
if(i == 0)
{
a[0]= a[0] + 1;
}
}
int main()
{
int k=0,size=0;
int a1[]={9,8,9,9};
size=sizeof(a1)/sizeof(*a1);
printf("Input array:\n");
while(k<size)
{
printf("%d ", a1[k]);
k++;
}
printf("\n");
inc(a1,size);
k=0;
printf("Output array after incrementing by 1:\n");
while(k<size)
{
printf("%d ", a1[k]);
k++;
}
printf("\n");
return 0;
}
For performance perspective, use minus instead of mod.
//Given a number, e.g., 2789, as an array [2,7,8,9].
//Write a method that returns the array incremented by one: i.e. [2,7,9,0].
public int[] IncreaseNumber(int[] input)
{
if (input == null || input.Length == 0)
{
throw new ArgumentException();
}
int temp = 0;
for (int i = input.Length -1; i >=0; i--)
{
temp = input[i] + 1;
input[i] = temp >= 10 ? temp - 10 : temp;
if (temp < 10)
{
return input;
}
if (temp >= 10 && i == 0)
{
int[] result = new int[input.Length + 1];
for (int j = 1; j < result.Length; j++)
{
result[j] = input[j - 1];
}
result[0] = 1;
return result;
}
}
return input;
}
public class CarryCount
{
//Total Time is O(n)
public static void main(String[] args)
{
int[] inputs = new int[]{2,3,8,9};
print(add(inputs));
//2 3 9 0
inputs = new int[]{9,9,9,9};
print(add(inputs));
//1 0 0 0 0
}
public static void print(int[] inputs)
{
for(int i : inputs)
{
System.out.print(i + " ");
}
System.out.println();
}
public static int[] add(int[] inputs)
{
boolean carry = true;
for(int i = inputs.length-1; i>=0; i--)
{
if(carry)
{
inputs[i] ++;
if(inputs[i] == 10)
{
carry = true;
inputs[i] %= 10;
}
else
{
carry = false;
break;
}
}
}
if(carry)
{
int[] inputs2 = new int[inputs.length + 1];
inputs2[0] = 1;
for(int i=0; i< inputs.length; i++)
{
inputs2[i+1] = inputs[i];
}
inputs = inputs2;
}
return inputs;
}
}
///
public class application {
public static void main(String args[]){
int[] arr={9,9,9,9};
increment(arr,arr.length);
}
public static void display(int result[]){
for(int i=0;i<=result.length-1;i++){
System.out.print(result[i]);
}
}
public static void increment(int [] arr,int length){
int[] result = {1,0,0,0,0};
if(arr[length-1]==9){
arr[length-1]=0;
length--;
if(length!=0)
increment(arr,length);
if(length==0 && arr[length]==0){
display(result);
}
}else{
arr[length-1]++;
display(arr);
}
}
}
\\\
public class Array {
public static void main(String[] args){
int a[] = {6,7,8,9}; // u can try for 1235,9999 or any other number also
int len = a.length;
int carry =1;
for(int i= len-1; i>=0;i--){
if(a[i]==9 && carry == 1){
a[i] = 0;
carry = 1;
}else if(a[i]!=9 && carry ==1) {
a[i] = a[i] + 1;
carry = 0;
}else{
a[i] = a[i];
carry = 0;
}
}
for(int i=0; i<len ;i++){
System.out.print(a[i]);
}
}
}
Used recursive approach,
int incrementOne(int* arr, int len,int curr)
{
if(arr[len-1]<9)
{
arr[len-1]++;
return 0;
}
if(curr==len-1)
{
arr[curr]=0;
return 1;
}
arr[curr]+=incrementOne(arr,len,curr+1);
if(arr[curr]<=9)
return 0;
arr[curr]-=10;
return 1;
}
void incrementOne(int* arr, int len)
{
int c=incrementOne(arr, len,0);
if(c==1)
{
for(int i=len;i>0;--i)
arr[i]=arr[i-1];
arr[0]=1;
len++;
}
for(int i=0;i<=len-1;++i)
cout<<arr[i];
cout<<endl;
}
#ifdef TEST_INCREONE
void main()
{
int arr[10]={2,7,8,9};
incrementOne(arr,4);
int arr1[10]={9,9,9,9};
incrementOne(arr1,4);
int arr2[10]={2,7,8,8};
incrementOne(arr2,4);
system("pause");
}
#endif
There can be a no. of ways to get that output........Difficult to decide with just one example.
BTW, I have come up with the below algorithm
int[] plusplus(int[] inArr)
{
Find length of input Array;
Define outputArraylength={length of input Array}; + 1;
declare outputArray
Declare carry variable
decrement OutputArraylength
Loop (outArraylen>=0)
{
if (inlen == (inArr.Length - 1))
carry = inArr[inlen--] + 1;
else if (inlen>=0)
carry += inArr[inlen--];
outArr[outlen--] = carry % 10;
carry /= 10;
}
return outputArray;
}
1. Combine the digits of the array (eg:9999)
2. Add one to it(10000);
3. Convert it to interger array;
#include<stdio.h>
#include<conio.h>
int main()
{
int n,storevalue,value=0,*arr,i=0;
printf("enter the values of n \n");
scanf("%d",&n);
arr=(int *)malloc(sizeof(int)*n);
printf("enter the value in an array ");
for(i=0;i<n;i++)
{
scanf("%d",&arr[i]);
}
printf(" \n values in an array \n ");
for(i=0;i<n;i++)
{
printf("%d , ",arr[i] );
value=value*10+arr[i];
}
printf(" \n value is == %d ",value);
// for plus plus ++
i=0;
value=value+1;
printf(" \n after addition is == %d ",value);
while(value!=0&&i!=n)
{
storevalue=value%10;
value=value/10;
printf(" \n plz %d, st %d",value,storevalue);
arr[i++]=storevalue;
if(i==n)
{//realloc size of array....
n=n+1;
arr = (int *) realloc (arr,n* sizeof(int));
}
}
printf(" \n after addition the answer is ");
for(i=0;i<5;i++)
{
printf("%d , ",arr[i] );
}
getch();
}
hey anybody can tell me ,how can i store an integer value in digit form to an array ?? plzzzzz...help me .... :)
Resizing the array is required iff. each digit in the input is a 9. We perform one linear pass to determine if this is the case, and if so we allocate an array of size n+1 and fill in values {1, 0, 0, ...}. Otherwise, we start from the rightmost digit and set all A[i] to 0 until we reach a digit that's not 9, which we increment.
Use addition and multiplication by power of 10 to combine the elements to make the number, then add 1, and then use division and mod operation to separate out the last digit on each step to create a new array. In the above case
Step 1: 9*1000 + 9*100 + 9*10 + 9 = 9999
Step 2: 9999 + 1 = 10000
Step 3: 10000%10=0 then 1000%10=0 then 100%10=0 then 10%10=0 and 1%10=1 and then add them to a new array in reverse order
Do roundup(10000/10) to get the number for the next stage inside the loop.
I guess question is to implement the ++ operator so that if we write array++ or ++array then we will get answer as 1 incremented from the value of the array(taken each entry as digit of a number).
private static int[] plusOneArray(int[] x){
String value = "";
int plusOne = 0, i;
for(i = 0; i < x.length; i++)
value += Integer.toString(x[i]);
plusOne = Integer.parseInt(value);
value = Integer.toString(++plusOne);
if(value.length() > x.length)
x = new int[value.length()];
for(i = 0; i < value.length(); i++)
x[i] = Integer.parseInt(Character.toString(value.charAt(i)));
return x;
}
{{
import java.util.ArrayList;
import java.util.List;
public class PlusPlusTest {
public static void main(String[] args) {
int[] number = { 9, 8, 9, 9 };
List<Integer> list = new ArrayList<Integer>();
for(int i=0; i<number.length;i++) {
list.add(number[i]);
}
int remainder = 0;
for (int i = list.size() - 1; i >= 0; i--) {
if (list.get(i) == 9) {
list.set(i, 0);
remainder = 1;
} else {
remainder=0;
list.set(i, list.get(i)+1);
break;
}
}
// Special case: if we have a remainder of 1, we need to add 1 as the first element
if(remainder == 1) {
list.add(0,1);
}
System.out.println("Nb element in list: " + list.size());
for(int i : list) {
System.out.print(i + " ");
}
}
}
}}
public class Hello{
public boolean incrNext;
public static void main(String as[]){
Hello a= new Hello();
a.plusPlus();
}
public void plusPlus(){
int[] dd1=new int[100];
int[] dd= {9,9,9,9,9,9,9,9,9,9,8,9,9,9,9};
System.out.println(dd);
for(int i=dd.length-1;i>=0;i--){
if(!incrNext&&!(i==dd.length-1)){
dd1[i]=( (dd[i]));
System.out.println(dd1[i]);
}else{
if(i==0){
dd1[i]=add(dd[i],true);}
else{
dd1[i]=add(dd[i],false);
}
System.out.println(dd1[i]);
}
}
}
public int add (int i,boolean last){
i=i+1;
if(i==10&&!last){
incrNext=true;
return 0;
}
incrNext=false;
return i;
}
}
public int[] plusPlus(int[] numbers) {
int step = 1;
for (int i = numbers.length - 1; i >= 0; i--) {
numbers[i] = numbers[i] + step;
if (numbers[i] > 9) {
numbers[i] = 0;
step = 1;
} else {
step = 0;
numbers[i] = numbers[i] + step;
}
}
if (step == 1) {
int[] result = new int[numbers.length + 1];
for (int i = 1; i < result.length - 1; i++) {
result[i] = numbers[i - 1];
}
result[0] = 1;
return result;
} else {
return numbers;
}
}
public class plusplus {
private static int[] output = null;
public static void main(String[] args){
int[] input = {9,4,3,6};
plus(input);
for(int i : output){
System.out.println(i);
}
}
public static void plus(int[] input){
int i = Integer.parseInt(getString(input).toString());
i++;
getArray(i);
}
public static StringBuilder getString(int[] input){
StringBuilder b = new StringBuilder();
for(int i: input){
b.append(i);
}
return b;
}
public static void getArray(int i){
int arrayLength = String.valueOf(i).length();
output = new int[arrayLength];
List <Integer>digits = new ArrayList<Integer>(arrayLength);
while(i>0){
output[arrayLength-1] = i%10;
arrayLength--;
i/=10;
}
}
}
(1)limitation:input array can only contain single digit integer ,meaning {1,2,3} is a valid input versus {11,2,3} is not
(2)special case:resizing the array is required ,if each digit in the input is a 9.For example:{9,9,9}===>{1,0,0,0}
_____________________________________
Python Code:
def plusplus(value_list):
carry = 0;
i=len(value_list)
for digit in reversed(value_list):
i=i-1
try:
if int(digit) > 9:
raise Exception()
next_digit = (int(digit) + 1)%10
except:
print 'input array is not valid,which can only hold single digit integers'
value_list[i] = str(next_digit)
#if there is a carry,do the plus operation for the next left digit of the value_list
if next_digit == 0:
carry = 1
continue
else:
break
#special case:resizing the array is required ,if each digit in the input is a 9.For example:{9,9,9}===>{1,0,0,0}
else:
if carry == 1:
value_list.insert(0, 1)
return value_list
'''
Main Entry
'''
console_input = raw_input("Enter something(ex:9,9,9,9): ")
input_list = console_input.split(',')
result_list = plusplus(input_list)
print result_list
Most general program I could come up with. Just use '1' in place of toAdd, and you will get the solution.
P.S. - Its working :)
#include<stdio.h>
void plusArray(int in[], int N, int toAdd)
{
int i;
int cin, c;
int out[1000];
int copyN=N;
cin=(in[N-1]+toAdd)/10;
in[N-1]=(in[N-1]+toAdd)%10;
N--;
while(!(cin==0 || N==0))
{
c=(in[N-1]+cin)/10;
in[N-1]=(in[N-1]+cin)%10;
cin=c;
N--;
}
int rightShift=0, copyCin=cin;
if(N==0 && cin!=0)
{
while(copyCin) { copyCin/=10; rightShift++; }
for(i=0;i<copyN;i++)
{
out[i+rightShift]=in[i];
}
for(i=0;i<rightShift;i++)
out[i]=(cin%((int)pow(10,rightShift-i)))/((int)pow(10, rightShift-i-1));
}
else
{
for(i=0;i<copyN;i++)
out[i]=in[i];
}
for(i=0;i<copyN+rightShift;i++)
printf("%d ", out[i]);
}
void main()
{
int in[] = {1,2,3};
plusArray(in, 3, 1024);
}
//usiing a vector to enable easy expansion of the result matrix
int digit,carryover=1, ct=0;
vector<int> arr;
while (true)
{
cout<<"enter each single digit (0-9), enter a -negative number to end"<<endl;
cin>>digit;
if (digit>=0)
{
arr.push_back(digit);
ct++;
}
else
break;
}
int temp;
for (int i=(ct-1); i>=0; i--)
{
temp = arr[i];
temp = temp+carryover;
if (temp >9)
{
arr[i]=0;
carryover=1;
}
else
{
arr[i] = arr[i]+1;
break;
carryover=0;
}
if ((i==0) && carryover != 0)
{//array needs to be expanded 9999
arr.insert(arr.begin(),1);
ct++;
}
}
cout<<"new digit after doing a ++"<<endl;
for (int g=0;g<ct;g++)
{
cout<<arr[g];
}
package google;
public class Plusplus_Operator_Array {
public static int[] plusplusOperator(int[] test){
boolean whether_add=true;
for(int i=0;i!=test.length;i++){
if((test[i]<0)||(test[i]>9)){
System.out.println("int[] err!");
return null;
}
else if(test[i]!=9){
whether_add=false;
break;
}
}
if(whether_add){
int[] result=new int[test.length+1];
result[0]=1;
for(int i=1;i!=result.length;i++){
result[i]=0;
}
return result;
}
else{
int[] result=new int[test.length];
int add_value=1;
for(int i=test.length-1;i>=0;i--){
if(test[i]+add_value==10){
add_value=1;
result[i]=0;
}
else{
result[i]=test[i]+add_value;
add_value=0;
}
}
return result;
}
}
public static void main(String[] args) {
int[] test=new int[]{9,9,9,9};
int[] plus_plus_result=plusplusOperator(test);
for(int i=0;i!=plus_plus_result.length;i++){
System.out.print(plus_plus_result[i]+" ");
}
}
}
package google;
import java.util.Arrays;
import java.util.HashMap;
public class PlusPlusOperator {
public static void main(String[] args) {
usingHashMap();
usingOperators();
}//main ends
static void usingHashMap(){
int[] arr={1,0,1};
int carry=0,len=arr.length;
HashMap <Integer,Integer> hMap=new HashMap<Integer,Integer>(10);
for(int i=0;i<9;i++){
hMap.put(i, i+1);
}
hMap.put(9,0);
int i=len-1;
while(carry==1&&i>0){
arr[i]=hMap.get(arr[i]);
if(arr[i]==0){
carry=1;
}else
carry=0;
i--;
}
if(carry>0){
arr=Arrays.copyOf(arr, len+1);
arr[0]=carry;
}
for(int j=0;j<arr.length;j++){
System.out.print(arr[j]);
}
}//method 2 ends
static void usingOperators(){
//Declare variables
int[] arr={9,2,9};
int sum=0,carry=0,len=arr.length;
//Add 1 to the last element
arr[len-1]+=1;
//loop through the entire array incrementing every number by carry
for(int i=len-1;i>=0;i--){
sum=arr[i]+carry;
if(sum>9){
carry=sum/10;
arr[i]=sum%10;
}
else{
carry=0;
arr[i]=sum;
}
}
if(carry>0){
arr=Arrays.copyOf(arr, len+1);
arr[0]=carry;
}
for(int j=0;j<len;j++){
System.out.print(arr[j]);
}
}//method1 ends
}//class ends
package google;
/**
*
* Problem :- Implement the plus plus operator when we are getting the input as integer array = { 9,9,9,9 }.output will be {1,0,0,0,0}
*
*/
public class ImplementPlusPlusFunctionalityForAnIntegerArray {
public static void main(String[] args) {
int[] input = {9,9,9,9};
int carry = 0;
if(input[input.length - 1] == 9){
int i = input.length - 1;
carry = 1;
while(i >=1 && carry == 1){
if(input[i] == 9){
input[i--] = 0;
carry = 1;
}else{
input[i--] += 1;
carry = 0;
break;
}
}
}else{
input[input.length - 1] += 1;
}
if(input[0] == 9 && (input.length == 0 || carry == 1)){
//Create new array of bigger size
input = new int[input.length + 1];
input[0] = 1;
for(int i = 1 ; i < input.length; i++){
input[i] = 0;
}
}
for(int i : input){
//Print the elements
System.out.println(i);
}
}
}
import java.util.ArrayList;
class IncrementNew{
public static void incrementArray(int[] inputArray){
StringBuffer str = new StringBuffer();
for(int i=0;i<inputArray.length;i++){
str.append(inputArray[i]);
}
int x = Integer.parseInt(str.toString());
x=x+1;
String str2 = Integer.toString(x);
System.out.println(x);
char[] iArray = new char[str2.length()];
iArray=str2.toCharArray();
int[] oArray = new int[iArray.length];
for(int i=0;i<iArray.length;i++){
oArray[i] = (int)iArray[i] & 0xF;
System.out.println(oArray[i]);
}
/*iArray[i]=; */
}
public static void main(String args[]){
int[] inputArray = {9,9,1,9};
incrementArray(inputArray);
}
}//class
#include <iostream>
void incby1(int* value, int* value1, int len){
int carry = 1;
int temp;
for(int i=len; i>0; i--){
if((value[i-1] + carry)==10){
value1[i] = 0;
carry = 1;
} else {
value1[i] = value[i-1] + carry;
carry = 0;
}
}
value1[0] = carry;
}
int main()
{
const int size = 4;
int value[size] = {8,4,9,9};
int value1[size+1]={0,0,0,0,0};
int carry = 1;
int temp;
incby1(value, value1, size);
cout<<value1<<endl;
}
Working Java code which was tested:
package arrays;
/**
*
* lets say a[] = {2,7,8,9}. we should make a contain {2,7,9,0}
*
*/
public class IncrementNumberInArray {
public static void main(String [] args){
int a [] = {9,9,9,9,9};
int b [] = new int[a.length+1];
int i = a.length-1;
int carry = 9;
for(;i>=0;i--) {
int sum=0;
sum += a[i]+carry;
int digit;
if(sum >=10){
digit = sum % 10;
carry = sum /10;
} else {
digit = sum;
carry = 0;
}
b[i+1]= digit;
}
b[0]= carry;
for (int j : b) {
System.out.print(j);
}
}
}
// plusplus.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include <vector>
#include <iostream>
using namespace std;
void plusplus(std::vector<int>& numArray)
{
std::vector<int>::reverse_iterator it;
int val = 0;
for (it = numArray.rbegin(); it != numArray.rend(); ++it)
{
val = *it;
// assert(val < 10)
val++;
if (val == 10)
*it = 0;
else
{
*it = val;
break;
}
}
if (val == 10)
numArray.insert(numArray.begin(), 1);
}
int _tmain(int argc, _TCHAR* argv[])
{
std::vector<int> arr;
arr.push_back(9);
arr.push_back(9);
arr.push_back(9);
arr.push_back(9);
plusplus(arr);
for(int i = 0; i < arr.size(); ++i)
cout << arr[i];
return 0;
}
void increase_by(int nums[], int size, int inc) {
if (size == 0) { return; }
int sum = nums[size-1] + inc;
int val = sum % 10;
int carry = (sum - val) / 10;
if (size > 1) {
increase_by(nums, size - 1, carry);
} else {
cout << carry;
}
cout << ' ' << val; // Suppose we are just printing to the console
}
void increase_by_one(int nums[], int size) {
increase_by(nums, size, 1);
}
C++ solution
vector<int> array_plusplus(const vector<int> &a) {
// up to which position propagates carray
int p = (int)a.size()-1;
while (p >= 0 && a[p] == 9)
--p;
// create result and copy for i<p and add +1 for i>=p
int offset = (p < 0 ? 1 : 0);
vector<int> res(a.size() + offset, 1);
for (int i = 0; i < (int)a.size(); ++i)
res[i+offset] = (a[i] + (i>=p))%10;
return res;
}
#include <iostream>
#include <vector>
using namespace std;
int main(){
int a[] = {9,9,9,9};
int value = 25;
int i;
vector<int> b;
int len = sizeof(a)/sizeof(a[0]);
for(i=len-1;i>=0;i--){
a[i]= a[i]+value; //14
if(a[i]>=10){
b.push_back(a[i]%10);
value = a[i]/10;
}
else{
b.push_back(a[i]);
value = 0;
}
}
if(value>0)
b.push_back(value);
for(i=b.size()-1;i>=0;i--)
cout << b[i];
return 0;
}
package plusplus;
public class Solution {
public static void main(String[] args) {
plusplus();
}
public static void printArray(int[] arr){
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
}
public static int[] plusplus(){
int[] arr = {9,9,9,9};
// int[] arr = {3,9,9,9};
// int[] arr = {1,0,1};
// int[] arr = {9,8,9};
// int[] arr = {9,9};
// int[] arr = {0};
// int[] arr = {9};
//Special cases for arr in length 1:::
if ((arr.length == 1) && (arr[0] == 9)){
arr= new int[arr.length+1];
arr[0]=1;
printArray(arr);
return arr;
}
if (arr[arr.length-1] != 9) {
arr[arr.length - 1] = arr[arr.length - 1] + 1;
} else {
for (int i = arr.length-2; i >=0 ; i--) {
if (arr[i]!=9) {
arr[i] = arr[i] + 1;
for (int j = i + 1; j < arr.length; j++) {
arr[j] = 0;
}
printArray(arr);
return arr;
}
}
arr= new int[arr.length+1];
arr[0]=1;
}
printArray(arr);
return arr;
}
}
When carry is 0, stop the loop(Add a checkpoint in for loop for this). And for the 4th line form last .. change it to if(i == 0 && flag*carry==1) form if(flag*carry==1).
working c code -
- nihaldps February 23, 2012