Google Interview Question for Android Engineers


Country: United States




Comment hidden because of low score. Click to expand.
1
of 3 vote

public int [] add (int [] num){
		if (num == null || num.length == 0) {
			return num ;
		}
		int carrier = 1 ;
		for (int i = num.length - 1 ; i >= 0 ; --i) {
			int sum = num[i] + carrier ;
			num[i] = sum % 10 ;
			carrier = sum / 10 ;
		}
		if (carrier > 0) {
			int [] rst = new int [num.length + 1] ;
			rst[0] = carrier ;
			System.arraycopy(num, 0, rst, 1, num.length);
			return rst ;
		}
		return num ;

}

- Scott September 01, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I came up with the same solution, but a slightly cheaper overflow solution. You're guaranteed that if the carrier > 0 after looping through the elements, that all values in the array are zero, so the arraycopy statement is unnecessary (you're copying zeros onto zeros).

- johnasmith September 23, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

We could simultaneously calculate the given number as the question states it must be interpreted. At the same time we can add one to the least significant digit to return the same result array.
This will be a clean O(d) time & O(1) space solution, the only catch is when the number has all 9s, this is when the result array must have an extra element.

public static int[] getIncrementedArray(int[] a)
	{
		if(a==null || a.length==0)
			return null;
		
		int resultNumber = 0;
		int givenNumber = 0;
		int factor = 1;
		int carry=1;
		
		for(int i=a.length-1;i>=0;i--)
		{
			givenNumber += a[i]*factor;
			resultNumber = a[i] + carry;
			
			if(resultNumber==10)
			{
				a[i]=0;
				carry=1;
			}
			
			else
			{
				a[i]=resultNumber;
				carry=0;
			}
			factor*=10;
		}
		
		int[] res = null;
		
		if(carry == 1)
		{
			res = new int[a.length+1];
			res[0]=1;
		}
		System.out.println("Given Number is: " + givenNumber);
		
		if(carry==0)
		   return a;
		else
			return res;
	}

The solution has time complexity O(n) & space complexity of O(1) when all digits are not 9.
The solution has O(n) time complexity & O(n) space complexity when all digits are 9.

- teli.vaibhav September 01, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

def incarray(seq):
    num = 0
    for digit in seq:
        num = num * 10 + digit
    num += 1
    result = []
    while num:
        result.append(num % 10)
        num //= 10
    result.reverse()
    return result

or using O(1) auxiliary space, iterating only once

def incarray2(seq):
    i = len(seq) - 1
    c = 1
    while i >= 0 and c:
        d = seq[i] + 1
        seq[i] = d % 10
        c = d // 10
        i -= 1
    if c:
        seq.insert(0, 1)
    return seq

- Dave September 01, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

char* getNumber(int length) {
	return(new char[length+1]);
}

char* removeLeadingZeros(char* arr) {
	const int len = strlen(arr);
	int i = 0;
	for(i=0; i<len; i++) {
		if(arr[i]!='0')
			break;     // break will not increment i, in case it is hit
	}
	
	int j=0;
	for(j=0; j<len-i; j++) {
		arr[j] = arr[j+i];
	}

	arr[j] = 0;
	
	return arr;
	
}


char* increment(char* arr) {
	removeLeadingZeros(arr);
	
	const int len = strlen(arr);
	if(arr[len-1]!='9') {
		arr[len-1] = arr[len-1] + 1;
	}else {
		int i = len-1;
		while(arr[i]=='9')
			i--;
		if(i>=0) {
			arr[i] = arr[i] + 1;
			i++;
			while(i<len)
				arr[i++] = '0';
			arr[i] = 0; 
		} else {
			arr[0] = '1';
			i=1;
			while(i<=len)
				arr[i++] = '0';
			arr[i] = '\0';		
		}
			
	}
	return arr;
}

void printNumber(char* arr) {
	for(int i=0; i<strlen(arr); i++) 
		cout << arr[i];
}

- Hem Dutt Dabral September 01, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class ArrayAdditionSvc
{
	public static int[] incrementByOne(int[] arr) throws NullPointerException
	{
		if(arr==null)
		{
			throw new NullPointerException();
		}
		int i=arr.length-1;
		int carry=1;
		while(i>=0)
		{
			int sum=carry+arr[i];
			carry=sum/10;
			arr[i--]=sum%10;
		}
		if(carry>0)
		{
			int newArr=new int[arr.length+1];
			newArr[0]=carry;
			System.arrayCopy(arr,newArry,0,1,arr.length);
			arr=newArr;
		}
		return arr;
		
	}
	public static int[] getTestInput(int n)
	{
		if(n<=0)
		{
			return null;
		}
		int[] a=new int[n];
		Random rnd=new Random();
		for(int i=0;i<a.length;i++)
		{
			a[i]=rnd.nextInt(101);
		}
		return a;
	}
	public static void main(String[] args)
	{
		Random rnd=new Random();
		int[] arr=ArrayAdditionSvc.getTestInput(rnd.nextInt(1001));
		System.out.println("start: "+Arrays.toString(arr));
		arr=ArrayAdditionSvc.incrementByOne(arr);
		System.out.println("result: " +Arrays.toString(arr));
	}
	
	//Worst case analysis: O(N) time and O(N) space
}

- divm01986 September 01, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public int[] addOne(int[] array) {
if (array == null || array.length == 0)
return null;
int carry = 0;
int last = 0;
for (int i = array.length - 1; i >= 0; i--) {
last = array[i];
last = last + 1;
carry = last / 10;
last = last % 10;
array[i] = last;

if (carry == 0)
return array;
}
// need copy
int[] result = new int[array.length + 1];
result[0] = 1;
for (int i = 0; i < array.length; i++)
result[i + 1] = array[i];
return result;
}

- Coder September 01, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

{{
public int[] addOne(int[] array) {
if (array == null || array.length == 0)
return null;
int carry = 0;
int last = 0;
for (int i = array.length - 1; i >= 0; i--) {
last = array[i];
last = last + 1;
carry = last / 10;
last = last % 10;
array[i] = last;

if (carry == 0)
return array;
}
// need copy
int[] result = new int[array.length + 1];
result[0] = 1;
for (int i = 0; i < array.length; i++)
result[i + 1] = array[i];
return result;
}
}}

- Coder September 01, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static int[] addNumber(int [] inputArr) throws Exception {
		boolean carryOver = false;
		for (int num = inputArr.length-1; num > -1; num--) {
			if (inputArr[num] < 0) throw new Exception("Invalid number");
			if (inputArr[num] < 9) {
				inputArr[num] = inputArr[num] + 1;
				carryOver = false;
				break;
			} else {
				inputArr[num] = 0;
				carryOver = true;
			}
		}
		// If all nines
		if (carryOver) {
			inputArr = new int[inputArr.length+1];
			Arrays.fill(inputArr, 0);
			inputArr[0] = 1;
		}
		// Trim output if input had leading zeroes
		int k = 0;
		for(;k<inputArr.length; k++) {
			if (inputArr[k] != 0) break;
		}
		if (k>0) {
			return Arrays.copyOfRange(inputArr, k, inputArr.length);
		}
		return inputArr;
}

- samit.roy September 01, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static int[] increment(int[] array) {

        int[] new_array = new int[array.length];

        boolean nextDigitPlusOne = true;
        for( int i = array.length - 1; i >= 0 ; i--) {
            if (nextDigitPlusOne) {
                if ( array[i] == 9 ) {
                    new_array[i] = 0;
                }
                else {
                    new_array[i] = array[i] + 1;
                    nextDigitPlusOne = false;
                }
            }
            else {
                new_array[i] = array[i];
            }
        }

        if ( nextDigitPlusOne ) {
            new_array = new int[array.length + 1];
            new_array[0] = 1;
        }

        return new_array;
    }

- Anonymous September 02, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This one should take into account all numbers up to long value
Could definitely use optimization but should be O(n) for space and time.

package com.test.IntegerArray;

public class IncrementArray {
	public IncrementArray(){}
	
	public void Test (int[] Test){
		int lengthofArray = Test.length;
		long multiplier = 1;
		long totalnumber=0;
		String ArrayNumberString;
		int[] ReturnArray;
		
		
		for(int i=lengthofArray-1; i >=0; i-- ){
			//convert array to number
			totalnumber = totalnumber + Test[i]*multiplier;
			multiplier = multiplier*10;
			
		}
		totalnumber++; //Add number
		
		//Convert new number back to Integer array by converting to string first and then setting the character
		
		ArrayNumberString = Long.toString(totalnumber);
		System.out.println("ArrayNumberString = " + ArrayNumberString);
		ReturnArray = new int[ArrayNumberString.length()];
		for(int i=0; i<ArrayNumberString.length(); i++){
			ReturnArray[i]=ArrayNumberString.charAt(i) - '0';
			System.out.print(ReturnArray[i] + "|");
		}
		System.out.println("");
		System.out.println("Return Array = " + ReturnArray);
		
		
		
	}
	

	public static void main(String[] args){
		IncrementArray Trial = new IncrementArray();
		int[] TestArray = {2,1,4,7,4,8,3,6,4,7,2,3,8,2};
		Trial.Test(TestArray);
	}

}

- Justine September 02, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

void setZeroes(vector<vector<int> > &matrix)
{
    int col0 = 1, rows = matrix.size(), cols = matrix[0].size();

    for (int i = 0; i < rows; i++)
    {
        if (matrix[i][0] == 0) col0 = 0;
        for (int j = 1; j < cols; j++)
            if (matrix[i][j] == 0)
                matrix[i][0] = matrix[0][j] = 0;
    }

    for (int i = rows - 1; i >= 0; i--)
    {
        for (int j = cols - 1; j >= 1; j--)
            if (matrix[i][0] == 0 || matrix[0][j] == 0)
                matrix[i][j] = 0;
        if (col0 == 0) matrix[i][0] = 0;
    }
}

- sosisarah September 02, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static int[] bigAdd(int[] digits) {
	int currentDigitsSum = 1;
	for (int i=digits.length - 1; i > -1; i--) {
		currentDigitsSum = digits[i] + currentDigitsSum;
		digits[i] = currentDigitsSum % 10;
		if (currentDigitsSum /10 ==0) {
			return digits;
		} else {
			currentDigitsSum /= 10;
		}
	}
	if (currentDigitsSum != 0) {
		int[] newDigits = new int[digits.length + 1];
		System.arraycopy(digits, 0, newDigits, 1, digits.length);
		newDigits[0] = currentDigitsSum % 10;
		return newDigits;
	}
	return null;
}

- mengjun1990 September 02, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static int[] bigAdd(int[] digits) {
	int currentDigitsSum = 1;
	for (int i=digits.length - 1; i > -1; i--) {
		currentDigitsSum = digits[i] + currentDigitsSum;
		digits[i] = currentDigitsSum % 10;
		if (currentDigitsSum /10 ==0) {
			return digits;
		} else {
			currentDigitsSum /= 10;
		}
	}
	if (currentDigitsSum != 0) {
		int[] newDigits = new int[digits.length + 1];
		System.arraycopy(digits, 0, newDigits, 1, digits.length);
		newDigits[0] = currentDigitsSum % 10;
		return newDigits;
	}
	return null;

}

- mengjun1990 September 02, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static int[] bigAdd(int[] digits) {
int currentDigitsSum = 1;
for (int i=digits.length - 1; i > -1; i--) {
currentDigitsSum = digits[i] + currentDigitsSum;
digits[i] = currentDigitsSum % 10;
if (currentDigitsSum /10 ==0) {
return digits;
} else {
currentDigitsSum /= 10;
}
}
if (currentDigitsSum != 0) {
int[] newDigits = new int[digits.length + 1];
System.arraycopy(digits, 0, newDigits, 1, digits.length);
newDigits[0] = currentDigitsSum % 10;
return newDigits;
}
return null;
}

- mengjun1990 September 02, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static int[] bigAdd(int[] digits) {
	int currentDigitsSum = 1;
	for (int i=digits.length - 1; i > -1; i--) {
		currentDigitsSum = digits[i] + currentDigitsSum;
		digits[i] = currentDigitsSum % 10;
		if (currentDigitsSum /10 ==0) {
			return digits;
		} else {
			currentDigitsSum /= 10;
		}
	}
	if (currentDigitsSum != 0) {
		int[] newDigits = new int[digits.length + 1];
		System.arraycopy(digits, 0, newDigits, 1, digits.length);
		newDigits[0] = currentDigitsSum % 10;
		return newDigits;
	}
	return null;
}

- mengjun1990 September 02, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static int[] bigAdd(int[] digits) {
	int currentDigitsSum = 1;
	for (int i=digits.length - 1; i > -1; i--) {
		currentDigitsSum = digits[i] + currentDigitsSum;
		digits[i] = currentDigitsSum % 10;
		if (currentDigitsSum /10 ==0) {
			return digits;
		} else {
			currentDigitsSum /= 10;
		}
	}
	if (currentDigitsSum != 0) {
		int[] newDigits = new int[digits.length + 1];
		System.arraycopy(digits, 0, newDigits, 1, digits.length);
		newDigits[0] = currentDigitsSum % 10;
		return newDigits;
	}
	return null;
}

- mengjun1990 September 02, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

def increment_array(a)
  i = a.size - 1
  while i >= 0 && a[i] == 9
    a[i] = 0
    i -= 1
  end

  if i < 0
    a.unshift(1)
  else
    a[i] += 1
  end
end

- brian September 02, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

test

- Anonymous September 02, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

def increment_array(a)
  i = a.size - 1
  while i >= 0 && a[i] == 9
    a[i] = 0
    i -= 1
  end

  if i < 0
    a.unshift(1)
  else
    a[i] += 1
  end
end

- Brian September 02, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Time: worst is O(n), only if all digits are 9; avg is much smaller - O(k), where k is the number of last digits in a row that are 9
Space: O(1) (it's not totally clear if they want a new array, but it sounds like incrementing in-place is okay)

def increment_array(a)
  i = a.size - 1

  while i >= 0 && a[i] == 9
    a[i] = 0
    i -= 1
  end

  if i < 0
    a.unshift(1)
  else
    a[i] += 1
  end

  a
end

- Brian September 02, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I know there are lots of correct codes here, but here's mine :)

vector<int> add(vector<int> &A,vector<int> &B)
{
	vector<int> ans;
	reverse(A.begin(),A.end());
	reverse(B.begin(),B.end());

	int carry=0;

	int i=0;
	while (i<A.size() || i<B.size()){
		int sum=(i<A.size() ? A[i]: 0) + ( i<B.size() ? B[i]:0) + carry;
		ans.push_back(sum%10);
		carry=sum/10;
		i++;
	}

	if (carry>0)
		ans.push_back(carry);

	reverse(ans.begin(),ans.end());

	return ans;

}

- MehrdadAP September 02, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <iostream>
#include <string>
#include <sstream>
#include <cstdlib>
#include <cstdio>
#include <vector>

using namespace std;



int main(){

  int a[100];
  int N;
  string s;
  
  cin>>N;
  
  for(int i=0;i<N;i++){
	cin>>a[i];
  }
  
  char arr[100];
  
  for(int i=0;i<N;i++){
	sprintf(arr,"%d",a[i]);
	s.push_back(arr[0]);
  }
  
  char result[100];
  sprintf(result,"%d",atoi(s.c_str())+1);
  
  vector<int> v;
  int j=0;
  while(result[j] != '\0'){
	v.push_back(result[j]-'0');
	j++;
  }
  
  j=0;
  while(j<v.size()){
	cout<<v[j]<<endl;
	j++;
  }
  
  
  
  
  
  return 0;
}

- rhenobudiasa September 03, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

vector<int> solution(vector<int> a){
   
  char arr[100];
  string s;
  
  int i=0;
  while(i<a.size()){
	sprintf(arr,"%d",a[i]);
	s.push_back(arr[0]);
	i++;
  }
  
  
  sprintf(arr,"%d",atoi(s.c_str())+1);
  
  vector<int> v;
  int j=0;
  while(arr[j] != '\0'){
	v.push_back(arr[j]-'0');
	j++;
  }
   
  return v;
  
}

- rhenobudiasa September 03, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

vector<int> solution(vector<int> a){
   
  char arr[100];
  string s;
  
  int i=0;
  while(i<a.size()){
	sprintf(arr,"%d",a[i]);
	s.push_back(arr[0]);
	i++;
  }
  
  
  sprintf(arr,"%d",atoi(s.c_str())+1);
  
  vector<int> v;
  int j=0;
  while(arr[j] != '\0'){
	v.push_back(arr[j]-'0');
	j++;
  }
   
  return v;

}

- rhenobudiasa September 03, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

vector<int> solution(vector<int> a){{

char arr[100];
string s;

int i=0;
while(i<a.size())

sprintf(arr,"%d",a[i]);
	s.push_back(arr[0]);
	i++;

sprintf(arr,"%d",atoi(s.c_str())+1);

vector<int> v;
int j=0;
while(arr[j] != '\0')

v.push_back(arr[j]-'0');
	j++;

return v;

- Anonymous September 03, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <vector>
#include <exception>

using namespace std;

void incrementIntegerArray(vector<int>& A) {
  
  // Checking for invalid input - skip to second for loop for algorithm

  if (A[0] < 0 || A[0] > 9) { // Not a valid array of digits
    throw exception();
  }
  
  int i;
  for (i = 1; i < A.size(); ++i) {
    
    if (A[i] < 0 || A[i] > 9) { // Not a valid array of digits
      throw exception();
    }
    if (A[i] != 9) {
      break;
    }
  }
  
  if (i == A.size() && A[0] == 9) { // A is all 9's
    throw exception();
  }
  if (i < A.size() && A[0] == 0) { // A + 1 will have a leading 0
    throw exception();
  }
  
  // Algorithm
  
  int carry = 1;
  
  for (i = static_cast<int>(A.size() - 1); i > 0; --i) {
    int sum = A[i] + carry;
    A[i] = sum % 10;
    carry = sum / 10;
  }
  
  A[0] += carry;
}

- DManchala16@students.claremontmckenna.edu September 03, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

vector<int> solution(vector<int> a){
   
  char arr[100];
  string s;
  
  int i=0;
  while(i<a.size()){
	sprintf(arr,"%d",a[i]);
	s.push_back(arr[0]);
	i++;
  }
  
  
  sprintf(arr,"%d",atoi(s.c_str())+1);
  
  vector<int> v;
  int j=0;
  while(arr[j] != '\0'){
	v.push_back(arr[j]-'0');
	j++;
  }
   
  return v;
  
}

- rhazehaze September 03, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

vector<int> solution(vector<int> a){
char arr[100];
string s;

int i=0;
while(i<a.size()){
sprintf(arr,"%d",a[i]);
s.push_back(arr[0]);
i++;
}

sprintf(arr,"%d",atoi(s.c_str())+1);

vector<int> v;
int j=0;
while(arr[j] != '\0'){
v.push_back(arr[j]-'0');
j++;
}

return v;

}

- rhenobudiasa September 03, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This solution relies on the nature of ints dropping their decimal values. Should be 0(n) time, but solves without converting to a string. Needs java.util.Arrays imported. Catches edge cases such as 9999's where an extra digit is added, and should word for very "any" size of array etc.

public static void addOne(int [] start)
	{
		int originalNum = 0;
		
		for(int x=0; x<start.length; x++)
		{
			originalNum += start[x];
			originalNum *= 10;
		}
		originalNum /= 10;
		
		int added = originalNum + 1;
		int endNumber = added;
		int old, digit, index, count=0;
		
		while(added > 0)
		{
			old = added;
			added /= 10;
			count+=1;
		}
		int [] finished = new int[count];
		
		for(count-=1; count >= 0; count--)
		{
			int temp = endNumber;
			endNumber /= 10;
			digit = temp-endNumber*10;
			finished[count] = digit;
		}
		System.out.println(Arrays.toString(finished));	
	}

- bschlangen September 03, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Method returns new int array, takes into account requirements regarding array length and leading zeros. Optimized to use 1 pass array navigation. Main time consuming operation is array copy.

public static int[] incrementIntArray(int[] inputOriginalIntArray)
    {
        if(inputOriginalIntArray==null) return null;
     //Create copy of input array to not mutate it
        int[] inputIntArray = Arrays.copyOfRange(inputOriginalIntArray,0,inputOriginalIntArray.length);

        // Increment by 1 using taking into account 9 in the end
        int i = inputIntArray.length-1; //firstNonNine
        while (i>=0 && inputIntArray[i] == 9) {
            inputIntArray[i]=0;
            i--;

            if(i<0)   //All are 9
            {
                int[] result = new int[inputIntArray.length+1];
                result[0]=1;
                return result;
            }
        }
       //first non 9 found, lets increment it
        inputIntArray[i]++;

       //check if there are leading zeros, calculate first non zero
        int j = 0;        //  fistNonZero
        while(j<i && inputIntArray[j] == 0) j++;

        if(inputIntArray.length==j)
        {
            return new int[]{1};    //if all are zeros
        }  else if(j==0)
        {
            return inputIntArray;   //no leading zeros at all, just return modified array
        }   else
            return Arrays.copyOfRange(inputIntArray,j,inputIntArray.length); //there are leading zeros, return trimmed array

    }

- Alexander Opekunov September 04, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public int[] prob1(int[] ar1) {

for(int i = (ar1.length-1);i>=0;i--){
++ar1[i];
if(ar1[i]>9) {
ar1[i]=0;
continue;
} else {
if(ar1[0]==0) {
int[] ar2 = new int[ar1.length-1];
for(int j =1;j<ar1.length;j++) {
ar2[j-1]=ar1[j];
}
return ar2;
}
return ar1;
}
}
if(ar1[0]==0) {
int[] ar2 = new int[ar1.length+1];
ar2[0]=1;
for(int i =0;i<ar1.length;i++) {
ar2[i+1]=ar1[i];
}
return ar2;
}
return ar1;
}

[1, 3, 4, 5] =>[1, 3, 4, 6] loop runs only 1 time
[9, 8, 4, 3] =>[9, 8, 4, 4] loop runs only 1 time
[9, 9, 9, 9] =>[1, 0, 0, 0, 0] all element are parsed twice and 1 new array is created.
[0, 9, 9, 9] =>[1, 0, 0, 0] all element are parsed 1 time
[0,1,2,3] =>[1, 2, 4] all element are parsed 1 time and a new array is created.

- rr September 05, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public int[] prob1(int[] ar1) {

        for(int i = (ar1.length-1);i>=0;i--){
            ++ar1[i];
            if(ar1[i]>9) {
                ar1[i]=0;
                continue;
            } else {
                if(ar1[0]==0) {
                    int[] ar2 = new int[ar1.length-1];
                    for(int j =1;j<ar1.length;j++) {
                        ar2[j-1]=ar1[j];
                    }
                    return ar2;
                }
                return ar1;
            }
        }
        if(ar1[0]==0) {
            int[] ar2 = new int[ar1.length+1];
            ar2[0]=1;
            for(int i =0;i<ar1.length;i++) {
                ar2[i+1]=ar1[i];
            }
            return ar2;
        }
        return ar1;
    }

[1, 3, 4, 5] =>[1, 3, 4, 6]
[9, 8, 4, 3] =>[9, 8, 4, 4]
[9, 9, 9, 9] =>[1, 0, 0, 0, 0]
[0, 9, 9, 9] =>[1, 0, 0, 0]
[0,1,2,3] =>[1, 2, 4]

- Anonymous September 05, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

[1, 3, 4, 5] =>[1, 3, 4, 6] loop runs only 1 time
[9, 8, 4, 3] =>[9, 8, 4, 4] loop runs only 1 time
[9, 9, 9, 9] =>[1, 0, 0, 0, 0] all element are parsed twice and 1 new array is created.
[0, 9, 9, 9] =>[1, 0, 0, 0] all element are parsed 1 time
[0,1,2,3] =>[1, 2, 4] all element are parsed 1 time and a new array is created.

- rewati.raman September 05, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

public int[] prob1(int[] ar1) {

        for(int i = (ar1.length-1);i>=0;i--){
            ++ar1[i];
            if(ar1[i]>9) {
                ar1[i]=0;
                continue;
            } else {
                if(ar1[0]==0) {
                    int[] ar2 = new int[ar1.length-1];
                    for(int j =1;j<ar1.length;j++) {
                        ar2[j-1]=ar1[j];
                    }
                    return ar2;
                }
                return ar1;
            }
        }
        if(ar1[0]==0) {
            int[] ar2 = new int[ar1.length+1];
            ar2[0]=1;
            for(int i =0;i<ar1.length;i++) {
                ar2[i+1]=ar1[i];
            }
            return ar2;
        }
        return ar1;
    }

[1, 3, 4, 5] =>[1, 3, 4, 6]
[9, 8, 4, 3] =>[9, 8, 4, 4]
[9, 9, 9, 9] =>[1, 0, 0, 0, 0]
[0, 9, 9, 9] =>[1, 0, 0, 0]
[0,1,2,3] =>[1, 2, 4]

- rewati.raman September 05, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Where arr is the input array:

{{ (arr.join.to_i + 1).to_s.split(//) }}

- Sam September 05, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Where arr is the input array:

{{ (arr.join.to_i + 1).to_s.split(//) }}

- Sam September 05, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Where input_array is the input array of integers from 0-9

(input_array.join.to_i + 1).to_s.split(//)

- Sam September 05, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Where input_array is the input array of integers from 0-9

(input_array.join.to_i + 1).to_s.split(//)

- Sam September 05, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

// add adds the carry carry to the digit n.
// It returns the result and the carry.
func add(n, carry int) (int, int) {
	if n == 9 && carry == 1 {
		return 0, 1
	}
	return n+1, 0
}

// add1 adds 1 to a list of single digits assuming the list as a single number.
// It returns the new list after adding.
func add1(arr []int) []int {
	carry := 1
	for i := len(arr)-1; i >=0; i-- {
		// replace the old digit with the new digit after adding carry 1
		arr[i], carry = add(arr[i], 1)
		if carry == 0 {
			break
		}
	}
	// case where all digits are 9 e.g. [9, 9 , 9]
	if carry == 1 {
		arr = append([]int{1}, arr...)
	}
	return arr
}

- zingcat September 06, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

def addOne(number):
    if not number or len(number) == 0:
        return number

    if number[-1] < 9:
        return number[:-1] + [number[-1] + 1]
    else:
        result = [] + number
        i = len(number) - 1
        result[i] += 1
        while i > 0 and result[i] > 9:
            result[i] = 0
            result[i - 1] += 1
            i -= 1

        if result[0] > 9:
            result.insert(0, 1)
            result[1] = 0
        return result

- rchg1988 September 07, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

vector<int> Increment(vector<int>& data)
{
	int j = 1;
	vector<int> result;
	for (vector<int>::reverse_iterator it = data.rbegin(); it != data.rend(); it++)
	{
		j += *it;
		if (j < 10) {
			result.push_back(j);
			j = 0;
		} else {
			result.push_back(j - 10);
			j = 1;
		}
	}
	if (j == 1)
		result.push_back(j);
	reverse(result.begin(), result.end());
	return result;
}

- Teh Kok How September 11, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

vector<int> Increment(vector<int>& data)
{
	int j = 1;
	vector<int> result;
	for (vector<int>::reverse_iterator it = data.rbegin(); it != data.rend(); it++)
	{
		j += *it;
		if (j < 10) {
			result.push_back(j);
			j = 0;
		} else {
			result.push_back(j - 10);
			j = 1;
		}
	}
	if (j == 1)
		result.push_back(j);
	reverse(result.begin(), result.end());
	return result;
}

- Teh Kok How September 11, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class Increment {

	public static int[] incr(int[] a) {
		if (a.length == 0) return a;
		int curr = a.length - 1;
		return incr(a, curr);
		
	}
	
	private static int[] incr(int[] a, int curr) {
		if (curr == 0) {
			if (a[curr] < 9) {
				a[curr]++;
				return a;
			} else {
				a[curr] = 0;
				return a;
			}		
		}
		if (a[curr] < 9) {
			a[curr]++;
			return a;
		} else {
			a[curr--] = 0;
			return incr(a, curr);
		}
		
	}
	

	public static void main(String[] args) {
		int[] a = {1,2,3,4};
		int[] b = incr(a);
		for (int i : b) {
			System.out.print(i);
		}

	}

}

- ytwu07 September 16, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

python 3

arr = [9,8,8,3]
arr = ''.join(str(x) for x in arr)
arr = int(arr) + 1
arr = [int(x) for x in str(arr)]
print(arr)

- Anonymous September 22, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Since the number plus only one, we can simplify the code as follows:

void addOne(vector<int> &a) {
	int i = a.size() - 1;
	while (i >= 0 && a[i] == 9)
		a[i--] = 0;

	if (i < 0) {
		a.push_back(0);
		a[0] = 1;
	}
	else {
		++a[i];
	}
}

- malinbupt September 23, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static int[] calculateArray(int[] a){
		int carry = 1;
		int temp =0 ;
		for(int i=a.length-1;i>=0;i--){
			temp = a[i]+carry;
			carry = (a[i]+carry)/10;
			a[i] = (temp)%10;
		}
		if(carry==0){
			return a;
		}
		int newArray[] = new int[a.length+1];
		newArray[0]=carry;
		for(int i=1;i<newArray.length;i++){
			newArray[i]=a[i-1];
		}
		return newArray;
	}

- Hitesh October 07, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static int[] calculateArray(int[] a){
int carry = 1;
int temp =0 ;
for(int i=a.length-1;i>=0;i--){
temp = a[i]+carry;
carry = (a[i]+carry)/10;
a[i] = (temp)%10;
}
if(carry==0){
return a;
}
int newArray[] = new int[a.length+1];
newArray[0]=carry;
for(int i=1;i<newArray.length;i++){
newArray[i]=a[i-1];
}
return newArray;
}

- Hitesh October 07, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static int [] addOne(int [] array)
{

if(array.length == 0 || array [0] == 0) return array;

String adder = "";

for(int x = 0 ; x < array.length; x++)
{
adder += array [x];
}
//turn the adder numbers into integer
int result = Integer.parseInt(adder) + 1;
//reuse the adder variable
adder = result+"";
int [] newArray = new int [adder.length()];

for(int x = 0 ; x < newArray.length; x++)
{
newArray [x] = Integer.parseInt(adder.substring(x, x+1));
}

return newArray;

}

- Anonymous October 11, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static int [] addOne(int [] array)
{

if(array.length == 0 || array [0] == 0) return array;

String adder = "";

for(int x = 0 ; x < array.length; x++)
{
adder += array [x];
}
//turn the adder numbers into integer
int result = Integer.parseInt(adder) + 1;
//reuse the adder variable
adder = result+"";
int [] newArray = new int [adder.length()];

for(int x = 0 ; x < newArray.length; x++)
{
newArray [x] = Integer.parseInt(adder.substring(x, x+1));
}

return newArray;

}

- dfdfdfdf October 11, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static int [] addOne(int [] array)
{

if(array.length == 0 || array [0] == 0) return array;

String adder = "";

for(int x = 0 ; x < array.length; x++)
{
adder += array [x];
}
//turn the adder numbers into integer
int result = Integer.parseInt(adder) + 1;
//reuse the adder variable
adder = result+"";
int [] newArray = new int [adder.length()];

for(int x = 0 ; x < newArray.length; x++)
{
newArray [x] = Integer.parseInt(adder.substring(x, x+1));
}

return newArray;

}

- dfdfdfdf October 11, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Python

Please let me know if anyone have other thoughts

def incrementOne(givenArr):
    arrLen = len(givenArr)
    counter = 0
    for i in range(arrLen-1,-1,-1):
        if counter < arrLen-1:
            
            if int(givenArr[i])== 9:
                givenArr[i]=str(0)
            else:
                givenArr[i] =str(int(givenArr[i])+1)
                if(int(givenArr[i])) <= 9 :
                    break
                else:
                    givenArr[i]=str(0)
    print givenArr        
        
    

    
    
givenArray = ['6','7','9','9']

incrementOne(givenArray)

- saikat1239 November 04, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I got question on this. What happens if the last digit is 9 say {9,9,9,9}?

- Subbu January 12, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

class NumberUtil {
    int[] increaseOne(int[] nums) {
        if(nums == null || nums.length == 0)
            return nums;
        for(int i = nums.length - 1; i >= 0; i--) {
            if(nums[i] < 9) {
                nums[i]++;
                return nums;
            }
            nums[i] = 0;
        }
        int[] newNums = new int[nums.length + 1];
        newNums[0] = 1;
        return newNums;
    }
    public static void main(String[] args) {
        NumberUtil test = new NumberUtil();
        System.out.println(Arrays.toString(test.increaseOne(new int[] {1, 2, 3, 4})));
        System.out.println(Arrays.toString(test.increaseOne(new int[] {9, 9, 9, 9})));
        System.out.println(Arrays.toString(test.increaseOne(new int[] {9})));
    }
}

- hive April 24, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static int[] getSum1Array(int[] a) {
		if (a == null || a.length == 0) {
			return null;
		}
		int[] r = new int[a.length];
		boolean carry = true;
		int i = a.length - 1;
		while(i >= 0) {
			if (carry && a[i] < 9) {
				r[i] = a[i] + 1;
				carry = false;
			} else if (carry && a[i] == 9) {
				r[i] = 0;
			} else {
				r[i] = a[i];
			}
			i--;
		}
		if (carry) {
			int[] r2 = new int[r.length + 1];
			Arrays.fill(r2, 0);
			r2[0] = 1;		
			return r2;
		}
		
		return r;
	}

- guilhebl May 31, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I'll ask the interviewer if the array contains negative numbers in the array.

No lead zeros are created from my code below. However, I don't check if lead zero exists in the income array.

public int [] addOne( int [] inputArray){
		//Ques: Neg numbers?
		
		if (inputArray==null ) return null;
		
		int position= inputArray.length-1;
		int value = inputArray[position];
		value++;
		
		while(value >9){
			
			inputArray[position]=0;	
			position--;
			
			if (position<0){
				int [] temp= new int [inputArray.length+1]; 
				
				//Copy array to temp
				for (int i=inputArray.length; i<temp.length ;i--){
					temp[i]=inputArray[i];
				}
				
				inputArray=temp;
			}	
			value = inputArray[position];
			value++;
		}		
		return inputArray;
	}

- koeber99 July 16, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int[] addBy1(int[] array) {
    if (array == null || array.length == 0) {
        throw new IllegalArgumentException("Input must be non-empty array");
    }
    int[] newArray = new int[array.length];
    int hasCarry = true
    for(int i=newArray.length-1; i>=0; i--) {
        int val = array[i] + (hasCarry ? 1 : 0);
        newArray[i] = val % 10;
        hasCarry = val / 10 == 1;
    }  
    if (!hasCarry) {
        return newArray;
    }
    else {
        int[] temp = new int[array.length+1];    
        temp[0] = 1;
        // other entries in temp should be 0
        return temp;
    }
}

- jjongpark August 27, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Javascript solution

function compute (arr) {

    var sum = 0, result = [];
    for (var i= arr.length, j = 0; i > 0; i--)
        sum += arr[j++] * Math.pow(10, i - 1);

    sum++;
    while (sum > 1) {
        result.push(sum % 10);
        sum = Math.floor(sum / 10);
        if (sum == 1) result.push(1);
    }
    return result.reverse(); // Forgot to add this :-]
}

- donelle.sanders August 30, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

java solution!

int[] array = {1,4,4,9,9,9,1,9,9};
        
        if(array != null && array[0] > 0 && array.length > 0){
            int arraySize = array.length;
            int currentPosition = arraySize-1;
            while(array[currentPosition] == 9){
                currentPosition--;
                if(currentPosition < 0) return;
            }
            array[currentPosition] = array[currentPosition]+1;
        }
        System.out.println(Arrays.toString(array));

- Ivan January 11, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int[] array = {1,4,4,9,9,9,1,9,9};
        
        if(array != null && array[0] > 0 && array.length > 0){
            int arraySize = array.length;
            int currentPosition = arraySize-1;
            while(array[currentPosition] == 9){
                currentPosition--;
                if(currentPosition < 0) return;
            }
            array[currentPosition] = array[currentPosition]+1;
        }
        System.out.println(Arrays.toString(array));

- Ivan January 11, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int[] array = {1,4,4,9,9,9,1,9,9};
        
        if(array != null && array[0] > 0 && array.length > 0){
            int arraySize = array.length;
            int currentPosition = arraySize-1;
            while(array[currentPosition] == 9){
                currentPosition--;
                if(currentPosition < 0) return;
            }
            array[currentPosition] = array[currentPosition]+1;
        }
        System.out.println(Arrays.toString(array));

- Ivan January 11, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static int[] addOne(int[] array){
    
    for (int i = array.length-1; i >= 0; i--){
      int current = array[i];
      if (current < 9){
        array[i] = current + 1;
        return array;
      }else{
        array[i] = 0;
      }
    }
    
    int[] exc = new int[array.length+1];
    exc[0] = 1;
    
    return exc;

}

- Davide January 20, 2018 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More