Google Interview Question SDE1s
Country: United States
Did you test it?
For "1234", "111" returns 4432.
You should add digits from the end not from the beginning.
@-thelineofcode: Thank you very much. I have corrected the code. It is working now. There was major flaw in logic which I didn't pay attention to. Thanks again.
[1] How about the negative number? i.e. num1 = "7777", num2 = "-9999999999".
[2] How about the number with sign(+ or -) , need we write a subtraction method?
[3] How to check under which case, we should use "plus" or "subtraction"? It seems that we can not integrate them together.
[4] How to implement a subtraction method between two string numbers, seems that is much different with "plus", if you really start write the code, not just thinking. Any help is welcoming!
private static String addNumberUsingString(String strNum1, String strNum2) {
if (strNum1.length() == 0 && strNum2.length() == 0)
return "0";
if (strNum1.length() == 0) {
return strNum2;
}
if (strNum2.length() == 0)
return strNum1;
int loopCount = strNum1.length() > strNum2.length() ? strNum1.length() : strNum2.length();
int carry = 0;
StringBuffer resultBuffer = new StringBuffer();
for (int i = loopCount - 1; i > -1; i--) {
int n1 = 0, n2 = 0;
if (strNum1.length() >= i + 1)
n1 = Integer.parseInt(strNum1.substring(i, i + 1));
if (strNum2.length() >= i + 1)
n2 = Integer.parseInt(strNum2.substring(i, i + 1));
int sonuc = carry+n1 + n2;
String strSonuc = Integer.toString(sonuc);
resultBuffer.append(strSonuc.substring(strSonuc.length() - 1));
if (strSonuc.length() > 1)
carry = Integer.parseInt(strSonuc.substring(strSonuc.length() - 2, strSonuc.length() - 1));
else
carry = 0;
}
StringBuffer newResult = new StringBuffer(carry > 0 ? Integer.toString(carry) : "");
for (int i = resultBuffer.length()-1; i > -1; i--) {
newResult.append(resultBuffer.substring(i, i+1));
}
return newResult.toString();
}
public class AddBigNumbers {
public static String addBigNumber(String num1, String num2){
StringBuffer total = new StringBuffer();
int maxlength = num1.length() >= num2.length() ? num1.length() : num2.length();
for (int i=0; i<maxlength; i++){
if (num1.length() < maxlength) { num1 = "0" + num1; }
if (num2.length() < maxlength) { num2 = "0" + num2; }
}
char[] n1 = num1.toCharArray();
char[] n2 = num2.toCharArray();
int carry = 0;
for (int i=maxlength-1; i>=0; i--){
int val = (n1[i]-'0') + (n2[i]-'0') + carry;
if (val > 9) {
carry = 1;
total.append(val % 10);
}
else {
carry = 0;
total.append(val);
}
}
return total.reverse().toString();
}
public static void main(String str[]){
System.out.println(addBigNumber("2147483647","2147483647"));
}
}
A general naive solution but a working one .. Only problem being if String starts with 0 e.g : String s1="000099999", then it does not work .. any suggestions ????
import java.util.ArrayList;
import java.util.List;
public class AddNumbers {
public static void main(String[] args) {
String s1 = "9";
String s2 = "7";
StringBuilder sb = new StringBuilder("");
List<Integer> x = new ArrayList<Integer>();
int s1_length = s1.length();
int s2_length = s2.length();
int carry = 0;
int to_be_appended;
int to_be_appended_temp = 0;
int diff_in_length = s1.length() - s2.length();
if (s1.length() >= s2.length()) {
int difference_in_length = s1.length();
for (int i = s2.length() - 1; i >= 0; i--) {
char x1 = s1.charAt(i);
char x2 = s2.charAt(i);
String m = x1 + "";
String m1 = x2 + "";
int value1 = Integer.parseInt(m);
int value2 = Integer.parseInt(m1);
int result = value1 + value2 + carry;
if (result > 10) {
carry = 1;
to_be_appended = result - 10;
} else {
carry = 0;
to_be_appended = result;
}
sb.append(to_be_appended);
if (i == 0 && result > 10 && s1.length() == s2.length()) {
carry = 1;
sb.append(carry);
}
}
for (int k = diff_in_length - 1; k >= 0; k--) {
char x3 = s1.charAt(k);
String new_string = "" + x3;
int val = Integer.parseInt(new_string);
val = val + carry;
if (val >= 10) {
carry = 1;
to_be_appended_temp = val - 10;
} else {
carry = 0;
to_be_appended_temp = val;
}
sb.append(to_be_appended_temp);
if (val >= 10 && k == 0) {
carry = 1;
sb.append(carry);
}
}
String s = sb.toString();
System.out.print("resulting number is=======");
for (int m = s.length() - 1; m >= 0; m--) {
System.out.print(s.charAt(m));
}
}
}
}
package com.nav.algos;
import java.util.ArrayList;
import java.util.List;
public class AddNumbers {
/**
* @param args
*/
public static void main(String[] args) {
String s1 = "9999999999999999";
String s2 = "77777777777777";
StringBuilder sb = new StringBuilder("");
List<Integer> x = new ArrayList<Integer>();
int s1_length = s1.length();
int s2_length = s2.length();
int carry = 0;
int to_be_appended;
int to_be_appended_temp = 0;
int diff_in_length = s1.length() - s2.length();
if (s1.length() >= s2.length()) {
int difference_in_length = s1.length();
for (int i = s2.length() - 1; i >= 0; i--) {
char x1 = s1.charAt(i);
char x2 = s2.charAt(i);
String m = x1 + "";
String m1 = x2 + "";
int value1 = Integer.parseInt(m);
int value2 = Integer.parseInt(m1);
int result = value1 + value2 + carry;
if (result > 10) {
carry = 1;
to_be_appended = result - 10;
} else {
carry = 0;
to_be_appended = result;
}
sb.append(to_be_appended);
if (i == 0 && result > 10 && s1.length() == s2.length()) {
carry = 1;
sb.append(carry);
}
}
for (int k = diff_in_length - 1; k >= 0; k--) {
char x3 = s1.charAt(k);
String new_string = "" + x3;
int val = Integer.parseInt(new_string);
val = val + carry;
if (val >= 10) {
carry = 1;
to_be_appended_temp = val - 10;
} else {
carry = 0;
to_be_appended_temp = val;
}
sb.append(to_be_appended_temp);
if (val >= 10 && k == 0) {
carry = 1;
sb.append(carry);
}
}
String s = sb.toString();
System.out.print("resulting number is=======");
for (int m = s.length() - 1; m >= 0; m--) {
System.out.print(s.charAt(m));
}
}
}
}
import java.util.Scanner;
import java.util.Stack;
/**
*
* @author uğur
*/
public class AddTwoBigInteger {
public static void main (String args[]) {
Scanner scanner = new Scanner(System.in);
String inp1 = scanner.next();
String inp2 = scanner.next();
Stack<Character> stack1 = new Stack<>();
Stack<Character> stack2 = new Stack<>();
for (int i = 0 ; i < inp1.length() ; i++ ) {
stack1.add(inp1.charAt(i));
}
for (int i = 0 ; i < inp2.length() ; i++ ) {
stack2.add(inp2.charAt(i));
}
Stack<Integer> result = new Stack<>();
int carry = 0;
while ( !stack1.isEmpty() || !stack2.isEmpty() ) {
int i1;
int i2;
if (stack1.isEmpty() ) {
i1 = 0;
}
else {
i1 = Character.getNumericValue( stack1.pop() );
}
if (stack2.isEmpty() ) {
i2 = 0;
}
else {
i2 = Character.getNumericValue( stack2.pop() );
}
result.add( (i1 + i2 + carry ) % 10 );
carry = (i1 + i2 + carry ) / 10;
}
if ( carry != 0 ) {
result.add(carry);
}
while( !result.isEmpty() ) {
System.out.print(result.pop());
}
}
}
import java.util.Scanner;
import java.util.Stack;
/**
*
* @author uğur
*/
public class AddTwoBigInteger {
public static void main (String args[]) {
Scanner scanner = new Scanner(System.in);
String inp1 = scanner.next();
String inp2 = scanner.next();
Stack<Character> stack1 = new Stack<>();
Stack<Character> stack2 = new Stack<>();
for (int i = 0 ; i < inp1.length() ; i++ ) {
stack1.add(inp1.charAt(i));
}
for (int i = 0 ; i < inp2.length() ; i++ ) {
stack2.add(inp2.charAt(i));
}
Stack<Integer> result = new Stack<>();
int carry = 0;
while ( !stack1.isEmpty() || !stack2.isEmpty() ) {
int i1;
int i2;
if (stack1.isEmpty() ) {
i1 = 0;
}
else {
i1 = Character.getNumericValue( stack1.pop() );
}
if (stack2.isEmpty() ) {
i2 = 0;
}
else {
i2 = Character.getNumericValue( stack2.pop() );
}
result.add( (i1 + i2 + carry ) % 10 );
carry = (i1 + i2 + carry ) / 10;
}
if ( carry != 0 ) {
result.add(carry);
}
while( !result.isEmpty() ) {
System.out.print(result.pop());
}
}
}
#include <stdio.h>
#include <string.h>
struct node {
char data;
struct node *left;
};
struct node *framedigit(char *ptr){
int i,digit;
struct node *head,*temp,*prev;
head = prev = temp = NULL;
for (i = strlen(ptr)-1;i>=0;i--){
digit = ptr[i] - '0';
temp = (struct node *)malloc(sizeof(struct node));
temp->data = digit;
temp->left = NULL;
if(head == NULL){
head = prev = temp;
}else{
prev->left = temp;
prev = temp;
}
}
return head;
}
void printdigit(struct node *ptr){
if(ptr == NULL)return;
printdigit(ptr->left);
printf("%d",ptr->data);
}
struct node *sumof(struct node *p1,struct node *p2){
int sum = 0;
int carry = 0;
int rem = 0;
struct node *head,*temp,*prev;
head = prev = temp = NULL;
while((p1!=NULL) && (p2 != NULL)){
sum = p1->data + p2->data + carry;
rem = sum % 10;
carry = sum/10;
temp = (struct node *)malloc(sizeof(struct node));
temp->data = rem;
temp->left = NULL;
if(head == NULL){
head = prev = temp;
}else{
prev->left = temp;
prev = temp;
}
p1 = p1->left;
p2 = p2->left;
}
while(p1!=NULL){
sum = p1->data + carry;
rem = sum % 10;
carry = sum/10;
temp = (struct node *)malloc(sizeof(struct node));
temp->data = rem;
temp->left = NULL;
if(head == NULL){
head = prev = temp;
}else{
prev->left = temp;
prev = temp;
}
p1 = p1->left;
}
while(p2!=NULL){
sum = p2->data + carry;
rem = sum % 10;
carry = sum/10;
temp = (struct node *)malloc(sizeof(struct node));
temp->data = rem;
temp->left = NULL;
if(head == NULL){
head = prev = temp;
}else{
prev->left = temp;
prev = temp;
}
p2 = p2->left;
}
return head;
}
main()
{
char *ptr1 = "12323984";
char *ptr2 = "28888888888888888884";
struct node *p1,*p2,*p;
p1 = framedigit(ptr1);
p2 = framedigit(ptr2);
p = sumof(p1,p2);
printdigit(p);
}
output
28888888888901212868
use recursion. first represend two numbers in string with same length, which means to add "0" before head for the shorter number. Then add digits by recursive:
f(n) = f(n-1).subString(1) + sum of n's digits +1 or f(n) = f(n-1).subString(0,1) + sum of n's digits. This does not work for negative numbers.
public static String add(String a , String b){
String result = "";
int lengthA = a.length();
int lengthB = b.length();
if(lengthA>lengthB){
int x = lengthA - lengthB ;
String s0 = "";
for(int i=0;i<x;i++)
s0 +="0";
b = s0+b;
} else if(lengthA<lengthB){
int x = lengthB - lengthA ;
String s0 = "";
for(int i=0;i<x;i++)
s0 +="0";
a = s0+a;
}
result = calculate(a,b);
return result;
}
public static String calculate(String a , String b){
if(a.length()==0) return "";
if(a.length()==1){
return String.valueOf(Integer.parseInt(a)+Integer.parseInt(b));
}
String str = calculate(a.substring(1), b.substring(1, b.length()));
if(str.length()==a.length()){
return String.valueOf(Integer.parseInt(a.substring(0,1))+Integer.parseInt(b.substring(0,1))+1)+str.substring(1) ;
}else{
return String.valueOf(Integer.parseInt(a.substring(0,1))+Integer.parseInt(b.substring(0,1)))+str ;
}
}
The code snippets posted so far are just naive re-implementations of the same idea behind BigInteger. This question is about what happens when even BigInteger isn't big enough, so none of the responses here seem to come close to answering the question.
- Amit Kumar Yadav January 17, 2014public static String addUsingString(String firstNumber, String secondNumber) { if(firstNumber == null && secondNumber != null) return secondNumber; if(secondNumber == null && firstNumber != null) return firstNumber; int carry = 0; String result = ""; for(int i = firstNumber.length() - 1, j = secondNumber.length() - 1 ; i >= 0 || j >= 0 ; i--, j--) { if(i < 0) { while(j >= 0) { int valTwo = (int)secondNumber.charAt(j)- (int)'0'; int sum = carry + valTwo; carry = 0; // reseting carry for next iteration if(sum > 9) { carry = sum / 10; sum = sum % 10; } result = sum + result; j--; } if(carry != 0) result = carry + result; return result; } else if(j < 0) { while(i >= 0) { int valOne = (int)firstNumber.charAt(i)- (int)'0'; int sum = carry + valOne; carry = 0; // reseting carry for next iteration if(sum > 9) { carry = sum / 10; sum = sum % 10; } result = sum + result; i--; } if(carry != 0) result = carry + result; return result; } else { int valOne = (int)firstNumber.charAt(i) - (int)'0'; int valTwo = (int)secondNumber.charAt(j) - (int)'0'; int sum = carry + valOne + valTwo; carry = 0; // reseting carry for next iteration if(sum > 9) { carry = sum / 10; sum = sum % 10; } result = sum + result; } } if(carry != 0) result = carry + result; return result; }