Google Interview Question
Android EngineersCountry: United States
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.
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
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];
}
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
}
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;
}
{{
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;
}
}}
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;
}
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;
}
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);
}
}
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;
}
}
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;
}
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;
}
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;
}
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;
}
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;
}
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
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;
}
#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;
}
#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;
}
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));
}
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
}
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.
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]
[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.
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]
// 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
}
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
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;
}
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;
}
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);
}
}
}
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;
}
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;
}
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;
}
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;
}
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;
}
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)
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})));
}
}
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;
}
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;
}
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;
}
}
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 :-]
}
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));
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));
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));
}
- Scott September 01, 2015