Google Interview Question
Software Engineer / DevelopersCountry: United States
public class XSLT {
public static void main(String[] args) {
int[] arr = {9,9,9};
int num = 1;
int a=0;
for(int i=0;i<arr.length;i++) {
a=a*10+arr[i];
}
System.out.println("Old ::"+a);
int newSum = a+num;
int ram = newSum;
boolean carry=false;
int temp = 0;
while(ram>0) {
ram/=10;
temp++;
}
if(temp>arr.length)
carry=true;
ram/=10;
a/=10;
if(!carry)
while(newSum>0 && a>0) {
if(ram%10>a%10) {
carry=true;
}
ram/=10;
a/=10;
}
ram=newSum;
System.out.println("New SUm ::"+newSum);
int lenth=0;
while(ram>0) {
ram/=10;
lenth++;
}
if(carry) {
System.out.println("Carry is there");
arr = new int[lenth];
while(newSum>0) {
arr[lenth-1]=newSum%10;
System.out.println(arr[lenth-1]);
lenth--;
newSum/=10;
}
}
else
System.out.println("No carry");
}
}
If we are interested in the final result, then the we can achieve the result without conversion. The code is given below
#include <stdio.h>
#include <stdlib.h>
int main()
{
int a[] = {7,3,5,3,9};
int i;
// Instead of adding 1 separately, set carry initially
int carry = 1;
int size = sizeof(a)/sizeof(a[0]);
int* result = (int*)malloc((size+1)*sizeof(int));
for(i=size-1;i>=0;i--)
{
result[i+1] = (a[i]+carry)%10;
carry = (a[i]+carry)/10;
}
result[0] = carry;
for(i=0;i<size+1;i++)
printf("%d",result[i]);
printf("\n");
return 0;
}
import java.util.Arrays;
public class ArrayToNumber {
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
//int [] inputArray = {9,9,9};
int [] inputArray = {7,3,5,3,9};
System.out.println( "out put:"+ Arrays.toString(inputNumber(inputArray)));
}
/**
*
For example input = {7,3,5,3,9} convert this to number 73539,
add 1 so it becomes 73540 and convert to array {7,3,5,4,0}.
Array can be of any length, so you can't always represent array in form
of in-built number format. So you have to do this summation in-place.
Also, how would you increase array size in-case input = {9,9,9}
so output = (1,0,0,0}
Assume, all elements of arrays are between 0 and 9.
*/
public static int [] inputNumber(int [] inputArray){
int integerValue=0;
int [] outputArray = new int[inputArray.length];
int [] overFlowOutputArray = null;
//Converting array of elements into integer number
for(int i=0; i<inputArray.length;i++){
integerValue=integerValue*10+inputArray[i];
}
//Adding one to the integer number which got from previous step
integerValue = integerValue+1;
//Converting integer number back array
for(int j=inputArray.length-1; integerValue>0;j--){
//Check the array need to be increased and return the array
if(j==-1){
overFlowOutputArray = new int[inputArray.length+1];
System.arraycopy(outputArray, 0, overFlowOutputArray, 1, inputArray.length);
overFlowOutputArray[0] = integerValue%10;
return overFlowOutputArray;
}
outputArray[j] = integerValue%10;
integerValue = integerValue/10;
}
return outputArray;
}
}
import java.util.Arrays;
public class ArrayToNumber {
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
//int [] inputArray = {9,9,9};
int [] inputArray = {7,3,5,3,9};
System.out.println( "out put:"+ Arrays.toString(inputNumber(inputArray)));
}
/**
*
For example input = {7,3,5,3,9} convert this to number 73539,
add 1 so it becomes 73540 and convert to array {7,3,5,4,0}.
Array can be of any length, so you can't always represent array in form
of in-built number format. So you have to do this summation in-place.
Also, how would you increase array size in-case input = {9,9,9}
so output = (1,0,0,0}
Assume, all elements of arrays are between 0 and 9.
*/
public static int [] inputNumber(int [] inputArray){
int integerValue=0;
int [] outputArray = new int[inputArray.length];
int [] overFlowOutputArray = null;
//Converting array of elements into integer number
for(int i=0; i<inputArray.length;i++){
integerValue=integerValue*10+inputArray[i];
}
//Adding one to the integer number which got from previous step
integerValue = integerValue+1;
//Converting integer number back array
for(int j=inputArray.length-1; integerValue>0;j--){
//Check the array need to be increased and return the array
if(j==-1){
overFlowOutputArray = new int[inputArray.length+1];
System.arraycopy(outputArray, 0, overFlowOutputArray, 1, inputArray.length);
overFlowOutputArray[0] = integerValue%10;
return overFlowOutputArray;
}
outputArray[j] = integerValue%10;
integerValue = integerValue/10;
}
return outputArray;
}
}
public static int[] add(int[] arr, int num){
int carry = 0;
for(int x = arr.length -1; x >= 0; x--){
int place = (int) Math.pow(10, ((arr.length-1) -x));
int otherNum = (num % (place*10)) / place;
int newNum = arr[x] + otherNum + carry;
carry = newNum /10;
arr[x] = newNum % 10;
}
if(carry != 1)
return arr;
else{
int[] res = new int[arr.length+1];
res[0] = carry;
for(int x = 1; x < res.length; x++){
res[x] = arr[x-1];
}
return res;
}
}
class Test{
public static void main(String[] args){
int a[] = {9,3,4};
int add = 999,carry = 0,val=0,sum=0;
for(int i = a.length-1; i >= 0; i--){
val = add%10;
add = add/10;
sum = val + a[i] + carry;
if(sum > 9){
carry = 1;
a[i] = sum % 10;
}else{
a[i] = sum;
carry = 0;
}
}
if(add > 0 || carry == 1){
System.out.println("add " + (add+ carry) + " before array like arr[-1].. hahha");
}
for(int i = 0; i< a.length; i++){
System.out.print(a[i]+" ");
}
}
}
#include<stdio.h>
#include<conio.h>
int main(){
int n,a[20],b[20],i,count=0;
long num=0,num1;
clrscr();
printf("Enter number of elements in the array: ");
scanf(" %d",&n);
for(i=0;i<n;i++){
printf("Enter the %d element of array: ",i+1);
scanf(" %d",&a[i]);
num=num*10+a[i];
}
printf("\nThe elements inside the array is: ");
for(i=0;i<n;i++)
printf("%d\t",a[i]);
num=num+1;
num1=num;
while(num/10!=0){
count=count+1;
num=num/10;
}count++;
n=count;
for(i=count-1;i>=0;i--){
b[i]=num1%10;
num1=num1/10;
}
printf("\nThe new array is: ");
for(i=0;i<n;i++)
printf(" %d",b[i]);
getch();
return 0;
}
private static int[] calculate(int[] input) {
int len = input.length, sum = 0, i = 0;
boolean flag = true;
for(i =0; i<len; i++) {
sum = sum*10 + input[i];
if(input[i] != 9) flag = false;
}
sum += 1;
if(flag){
len = len+1;
int[] returnArr = new int[len];
for(i=len-1; i >=0; i--) {
returnArr[i] = sum%10;
sum=sum/10;
}
return returnArr;
} else {
for(i=len-1; i >= 0; i--) {
input[i] = sum%10;
sum = sum/10;
}
}
return input;
}
public class HAarray{
public static int[] add(int [] data){
int [] hold=new int[data.length];
for(int i=data.length-1;i>=0;i--){
if(data[i]==9 ){
if(i==0){
return newArray(data.length);
}
data[i]=0;
}
else {
data[i]=data[i]+1;
return data;
}
}
return data;
}
public static int [] newArray(int lengthh){
int [] chk=new int[lengthh+1];
for(int i=0;i<chk.length;i++){
if(i==0){
chk[i]=1;
}
else {
chk[i]=0;
}
}
return chk;
}
}
import java.util.Arrays;
public class AddNumberToArray {
public static void main(String[] args) {
int[] a = { 9, 9, 9, 9, 9, 5, 8, 9, 9, 9, 3, 5, 6, 7 };
int[] ans = addNumber(a);
System.out.println(Arrays.toString(ans));
}
private static int[] addNumber(int[] a) {
int l = a.length;
int lastEl = a[l - 1] + 1;
if (lastEl < 10) {
a[l - 1] = lastEl;
return a;
} else {
int carry = 1;
a[l - 1] = lastEl % 10;
int j;
for (int i = l - 2; i >= 0; i--) {
j = a[i] + carry;
a[i] = j % 10;
carry = j / 10;
}
if (carry == 1) {
int[] res = new int[l + 1];
res[0] = carry;
System.arraycopy(a, 0, res, 1, l);
return res;
}
return a;
}
}
}
How about this approach?
Since in worst case, the array size will increase by only one assuming the addend is that the array size, so in that case, we can go for the following approach:
Len:= arr.size()
put all the digits from arr[Len+1] back to the first position.
Now if after all this addition, carry exists, then add that carry to arr[0].
Else left-shift the array by 1.
public static int [] arrayPlusOne(int[]num)
{
int i=1;
while(num[num.length-i]==9&&i < num.length){
num[num.length-i]=0;
i++;
}
if(num[0]==9 && num[1]==9){
int finArr[]=new int[num.length+1];
finArr[0]=1;
for(int j=1;j<num.length;j++)
finArr[j]=0;
return finArr;
}
else{
num[num.length-i]+=1;
return num;
}
}
- Ashish May 14, 2013