Amazon Interview Question Software Engineer in Tests
Solution
#include <iostream>
struct Number // structure to create a doubly link list of numbers
{
Number *right;
Number *left ;
short int digit;
};
class BigNumber // Class which holds functions to create, add, substract the list list
{
BigNumber *actualAdd(BigNumber *num_1, BigNumber *num_2) // internal API for adding the numbers
{
BigNumber *result = new BigNumber(); //Temporary buffer to hold the result
short int tempResult = 0, carryOver = 0; // to check carry overs and hold temporary results
while (num_1->num->left != NULL) // move in the link list .. from right to left ex number 1234 so 4321
{
if (num_2->num->left != NULL) // move in the smaller link list .. same as the above one
{
tempResult = num_1->num->digit + num_2->num->digit;
if (carryOver != 0 ) // check to see if there is any carry
{
tempResult = carryOver+ tempResult;
carryOver = 0;
}
if (tempResult/10 != 0) // adding the carry if any and then divide by 10 if possible finally save the digit
{
carryOver = tempResult/10;
Number *temp = new Number();
temp->digit = tempResult%10;
result->num->left = temp; // result link list goes from right to left (reverse order)
temp->right = result->num;
temp->left = NULL;
result->num = temp;
}
else // if carry + last digit is a single digit add it to the list
{
Number *temp = new Number();
temp->digit = tempResult%10;
result->num->left = temp; // result link list goes from right to left (reverse order)
temp->right = result->num;
temp->left = NULL;
result->num = temp;
}
}
else // if there is no element in smaller number takes elements from the larger one
{
Number *temp = new Number;
if (carryOver != 0 ) // if there is a carry add it to the number
{
tempResult = carryOver + num_1->num->digit;
carryOver = 0;
if (tempResult/10 != 0)
{
carryOver = tempResult/10;
temp->digit = tempResult%10;
result->num->left = temp;
temp->right = result->num;
temp->left = NULL;
}
}
else
{
temp->digit = num_1->num->digit;
result->num->left = temp;
temp->right = result->num;
temp->left = NULL;
}
result->num = temp;
}
if (num_1->num->left != NULL)
num_1->num = num_1->num->left; // if larger link list has not reached end move left
if (num_2->num->left != NULL)
num_2->num = num_2->num->left; // if smaller link list has not reached end move left
}
if (carryOver != 0) // for the last carry over digit
{
Number *temp = new Number();
temp->digit = carryOver;
result->num->left = temp; // result link list goes from right to left (reverse order)
temp->right = result->num;
temp->left = NULL;
result->num = temp;
}
num_1->num = num_1->head; // set num back to head or the last digit ex: set to 4 in case of 1234
num_2->num = num_2->head; // set num back to head or the last digit ex: set to 4 in case of 1234
return result;
}
BigNumber *actualSubtract(BigNumber *num_1, BigNumber *num_2) // internal API for substraction
{
BigNumber *result = new BigNumber();
result->num->right = NULL;
short int tempResult = 0;
Number *tempnum = new Number();
BigNumber *copy = new BigNumber();
while (num_1->num->left != NULL) // copy/saves the original link
{
num_1->num = num_1->num->left;
Number *temp1 = new Number();
temp1->digit = num_1->num->digit;
copy->num->left = temp1;
temp1->right = copy->num;
temp1->left = NULL;
copy->num = temp1;
}
num_1->num = num_1->head;
while (num_1->num->left != NULL) // move in the larger number from right to left
{
if (num_2->num->left != NULL) // move in the smaller number from right to left
{
if (num_1->num->digit < num_2->num->digit) // if there is a carry subtract one from the number
{
tempnum = num_1->num->left;
while (tempnum->left != NULL && tempnum->digit >= 0) // adjust the carry over
{
if (tempnum->digit == 0)
{
tempnum->digit =9;
tempnum = tempnum->left;
}
else
{
tempnum->digit = tempnum->digit -1 ; // adjust the carry over
tempnum = tempnum->left;
}
}
if (tempnum->digit >= 0)
{
tempResult = (num_1->num->digit + 10) - num_2->num->digit;
}
if (num_1->num->left == NULL )
{
tempResult = (num_1->num->digit ) - num_2->num->digit;
}
}
else
{
tempResult = (num_1->num->digit ) - num_2->num->digit;
}
if (tempResult >= 0)
{
Number *temp = new Number();
temp->digit = tempResult;
result->num->left = temp; // move the result link list from right to left
temp->right = result->num;
temp->left = NULL;
result->num = temp;
}
}
else
{
if (num_1->num->digit >= 0)
{
tempResult = num_1->num->digit;
Number *temp = new Number();
temp->digit = tempResult;
result->num->left = temp;
temp->right = result->num;
temp->left = NULL;
result->num = temp;
}
}
if (num_1->num->left != NULL)
num_1->num = num_1->num->left; // if larger link list has not reached end move left
if (num_2->num->left != NULL)
num_2->num = num_2->num->left; // if smaller link list has not reached end move left
}
while (num_1->num->right != NULL) // copy the saved link list
{
num_1->num->digit = copy->num->digit;
copy->num = copy->num->right;
num_1->num = num_1->num->right;
}
num_1->num = num_1->head; // set num back to head or the last digit ex: set to 4 in case of 1234
num_2->num = num_2->head; // set num back to head or the last digit ex: set to 4 in case of 1234
return result;
}
public:
Number *num, *head,*tail;
bool SignBit;
BigNumber()
{
num = new Number(); // initilize the link list data structure.
head = new Number();
SignBit = false;
}
~BigNumber() // destructure to delete the list list created.
{
while (num->left != NULL) // if the head is at right most .. delete everything till the end
{
num = num->left;
delete num->right;
}
while (num->right != NULL) // if the head is at right most .. delete everything till the end
{
num = num->right;
delete num->left;
}
}
int getLength (Number *num) // get the length of the link list passed.
{
head = num;
int result = 0;
while (num->left != NULL)
{
result++;
num = num->left;
}
tail = num;
return result;
}
BigNumber *Add(BigNumber *num_1, BigNumber *num_2) // public API for adding
{
BigNumber *result = new BigNumber();
if ((num_1->SignBit == false && num_2->SignBit == false) || (num_1->SignBit == true && num_2->SignBit == true))
{
if( getLength(num_1->num) > getLength(num_2->num)) // irrespective of user input it check to which is a longer number to compute
{ // if the user inputs the shorter number first then it calls the private API accordingly , vice versa
result = actualAdd(num_1, num_2);
if (num_1->SignBit == true && num_2->SignBit == true)
{
while(result->num->digit <= 0)
{
result->num = result->num->right;
}
result->num->digit = result->num->digit * -1;
}
}
else if( getLength(num_1->num) < getLength(num_2->num))
{
result = actualAdd(num_2, num_1);
if (num_1->SignBit == true && num_2->SignBit == true)
{
while(result->num->digit <= 0)
{
result->num = result->num->right;
}
result->num->digit = result->num->digit * -1;
}
}
if( getLength(num_1->num) == getLength(num_2->num))
{
result = actualAdd(num_1, num_2);
if (num_1->SignBit == true && num_2->SignBit == true)
{
while(result->num->digit <= 0)
{
result->num = result->num->right;
}
result->num->digit = result->num->digit * -1;
}
}
}
else
{
result = Subtract(num_1, num_2); // call subtract is any sign is negative
}
return result;
}
bool DetermineBigger( BigNumber *n1, BigNumber *n2 ) // to determine the larger number if the number of digits are same
{
Number *head1, *head2;
head1 = n1->num;
head2 = n2->num;
n1->num = n1->head;
n2->num = n2->head;
while (n1->num->left != NULL && n1->num->digit > n2->num->digit)
{
n1->num = n1->num->left;
n2->num = n2->num->left;
}
if (n1->num->digit < n2->num->digit)
{
n1->num= head1;
n2->num= head2;
return true;
}
else
{
n1->num= head1;
n2->num= head2;
return false;
}
}
BigNumber *Subtract(BigNumber *num_1,BigNumber *num_2) // Public API for substraction
{
BigNumber *result = new BigNumber();
num_2->SignBit = true;
if ((num_1->SignBit != true && num_2->SignBit != true) || (num_1->SignBit == false || num_2->SignBit == false))
{
if( getLength(num_1->num) > getLength(num_2->num)) // irrespective of user input it check to which is a longer number to compute
{ // if the user inputs the shorter number first then it calls the private API accordingly , vice versa
result = actualSubtract(num_1, num_2);
if (num_1->SignBit == true) // negative neagative = add with negative sign
{
while(result->num->digit <= 0)
{
result->num = result->num->right;
}
result->num->digit = result->num->digit * -1; // add negative sign in the start
}
}
else if( getLength(num_1->num) < getLength(num_2->num))
{
result = actualSubtract(num_2, num_1); // negative neagative = add with negative sign
while(result->num->digit <= 0) //remove all the leading zeros
{
result->num = result->num->right;
}
result->num->digit = result->num->digit * -1; // add negative sign in the start
}
else
{
if (DetermineBigger(num_1, num_2))
{
result = actualSubtract(num_2, num_1);
while(result->num->digit <= 0) //remove all the leading zeros
{
result->num = result->num->right;
}
result->num->digit = result->num->digit * -1; // add negative sign in the start
}
else
{
result = actualSubtract(num_1, num_2);
if (num_1->SignBit == true)
{
while(result->num->digit <= 0) //remove all the leading zeros
{
result->num = result->num->right;
}
result->num->digit = result->num->digit * -1; // add negative sign in the start
}
}
}
}
else
{
result = Add(num_1,num_2); // call add if any of the signs are negative
}
return result;
}
void CreateLinkedList() // Public API to create the link list of numbers
{
bool SBit1 = false,SBit2 = false;
cout<<"Input the Numeber and press enter when done"<<"\n";
int tempInput = 0;
while ((tempInput = getchar()) != 10 )
{
if (tempInput == 45 && SBit1 == false && SBit2 == false)
{
SignBit = true; // store the negative sign
SBit1 = true;
}
else if (tempInput < 58 && tempInput > 47)
{
Number *temp = new Number();
temp->digit = tempInput-48;
temp->left = num;
temp->right = NULL;
num->right = temp;
num = num->right;
SBit2 = true;
}
else
{
num = new Number();
SignBit = false;
SBit1 = false;
SBit2 = false;
cout<<"invalid input... re-enter the number ... press enter when done";
}
}
head = num;
cout<<"\n";
}
void DisplayLinkedList() // public API to display the link list.
{
bool flag = false;
cout<<"The result is "<<"\n";
while (num->right != NULL)
{
flag = true;
cout<<num->digit;
num = num->right;
}
if (!flag)
{
cout<<"NULL Input";
}
cout<<"\n";
}
};
int main(int argc, char *argv[])
{
BigNumber *big1 = new BigNumber(); // create an object of class BigNumber
BigNumber *big2 = new BigNumber();
BigNumber *big3 = new BigNumber();
big1->CreateLinkedList(); // take user input of numbers.
big2->CreateLinkedList();
big3 = big3->Add(big1,big2); // adds the two link list
big3->DisplayLinkedList(); // displays the link list
big3 = big3->Subtract(big1,big2); // substracts the two link list
big3->DisplayLinkedList(); // displays the link list
// ------------------------------Test cases I have considered ---------------------------------------
//---------- Ideal inputs ----------
//First number = 50 Second number = 1 --> OUTPUT = on add = 51 .... on subtract = 49
//First number = 2 Second number = 18 --> OUTPUT = on add = 20 .... on subtract = -16
//First number = 18 Second number = 2 --> OUTPUT = on add = 20 .... on subtract = 16
//---------- Ideal inputs -----------
//First number = 2 Second number = 1 --> OUTPUT = on add = 3 .... on subtract = 1 (check precession)
//First number = 20 Second number = 10 --> OUTPUT = on add = 30 ....on subtract = 10 (check precession)
//First number = 1000 Second number = 1 --> OUTPUT = on add = 1001 ....on subtract = 999 (check precession)
//
//First number = 1 Second number = 9 --> OUTPUT = on add = 10 .... subtract = -8 (check precession on addation)
//First number = 9 Second number = 1 --> OUTPUT = on add = 10 .... subtract = 8 (check precession on subtraction)
//First number = 1 Second number = 99 --> OUTPUT = on add = 100 .... subtract = 98 (check precession on addation)
//First number = 99 Second number = 1 --> OUTPUT = on add = 100 .... subtract = 98 (check precession on subtraction)
//First number = -1 Second number = -1 --> OUTPUT = on add = -2 .... subtract = -2 (negative negative = addation with negative sign)
//First number = -1 Second number = 1 --> OUTPUT = on add = 0 .... subtract = -2 (negative negative = addation with negative sign)
//First number = 001 Second number = 1 --> OUTPUT = on add = 0 .... subtract = -2 (effect of initial zeros)
//First number = -1 Second number = 001 --> OUTPUT = on add = 0 .... subtract = -2 (effect of initial zeros)
//First number = -3 Second number = 20 --> OUTPUT = on add = 17 .... subtract = -23 (general)
//First number = 3 Second number = 20 --> OUTPUT = on add = 23 .... subtract = -17 (check sign substration and addation)
//First number = 3 Second number = -20 --> OUTPUT = on add = 23 .... subtract = -17 (check sign substration and addation)
//First number = 11 Second number = 12 --> OUTPUT = on add = 23 .... subtract = -1 (if second number is larger)
//First number = 1000 Second number = 999 --> OUTPUT = on add = 1999 .... subtract = 1 (check correct carry over)
//First number = 999 Second number = 1000 --> OUTPUT = on add = 1999 .... subtract = -1 (check correct carry over)
//First number = -0 Second number = -0 --> OUTPUT = crash (invalid number)
//
//Both numbers NULL -->OUTPUT = NULL Input
//First number is NULL -->OUTPUT = on subtract = negative second number
//Second number is NULL -->OUTPUT = on add = positive first num
//Both numbers zero -->OUTPUT = 0
//First inputs is zero -->OUTPUT = add does 0+input number ....subtract = negative number
//Second input is zero -->> OUTPUT = add does + input number ... subtract = positive number
//Both the numbers same --> OUTPUT = on add it adds up the numbers ... on subtract prints the result with the precision of the larger number i.e. 0000 - 000 = 000
//Input the first number as any non number from keyboard -->OUTPUT = invalid input... re-enter the number ... press enter when done
//Input the second number as any non number from keyboard -->OUTPUT = invalid input... re-enter the number ... press enter when done
//Repeated invalid input --> OUTPUT = invalid input... re-enter the number ... press enter when done <<-- till the time rite input is made to that number
//Combination of add and subtraction with the same input --> OUTPUT = correct result.
//Puting ideal values after wrong input --> OUTPUT = correct values for both add and subtraction
// Also tried inputing large values upto 10 digit --> OUTPUT = valid valued for add and subtract
//Input the first number as any non number from keyboard -->OUTPUT = invalid input... re-enter the number ... press enter when done
//Input the second number as any non number from keyboard -->OUTPUT = invalid input... re-enter the number ... press enter when done
//Repeated invalid input --> OUTPUT = invalid input... re-enter the number ... press enter when done <<-- till the time rite input is made to that number
//Inputed large values upto 10 digit --> OUTPUT = valid values for add and subtract
//Inputed numbers upto 20 digits --> OUTPUT = i check the last numbers which were correct couldn't check the whole result.
//Inputed numbers upto 40 digits --> OUTPUT = i check the last numbers which were correct couldn't check the whole result.
//Combination of add and subtraction with the same input --> OUTPUT = correct result.
//Combination of add and subtraction with the different input for every operation(like equation )--> OUTPUT = valid result.
//Puting ideal values after wrong input --> OUTPUT = correct values for both add and subtraction
// ------------------------------test cases I have considered ---------------------------------------
}
it has all the cases you can think of
1.) Input can be in any order(smaller first, vice versa)
2.) includes negative numbers
3.) Carry over/under for +ve and -ve
4.) -ve + -ve = - but -ve * -ve = +ve (all cases).
except for -0 and -0 it works for anything .... i know it seems simple but when u sit down to test yr own code ... u tend to realize so many conditions.
let me know if you need any explanations.
1) - add zero to one of them so they have same length
2 3 4)a+(-b)=a-b, so no special handling of negative is required
the problem is not with numbers of different length .. it's when they are of same length (100)- (199)(think of it the order can't be changed) and since we are using link list we can't say [199 > 100]
and yes i agree the second condition doesn't require any special case ... but you would require them in cases like -a - -a = which is not subtraction but rather addition
Using python would not show the programming skills. probably interviewer would like to see the implementation of basic data type as ADT.
I would probably go for an Array(Vector) of Unsigned Chars. Implement the ADT array with the capacity to increase the size. We can store each digit in one byte and later on do byte operation of Add or subtract. We can access each byte based on index
include <iostream>
struct Number // structure to create a doubly link list of numbers
{
Number *right;
Number *left ;
short int digit;
};
class BigNumber // Class which holds functions to create, add, substract the list list
{
BigNumber *actualAdd(BigNumber *num_1, BigNumber *num_2) // internal API for adding the numbers
{
BigNumber *result = new BigNumber(); //Temporary buffer to hold the result
short int tempResult = 0, carryOver = 0; // to check carry overs and hold temporary results
while (num_1->num->left != NULL) // move in the link list .. from right to left ex number 1234 so 4321
{
if (num_2->num->left != NULL) // move in the smaller link list .. same as the above one
{
tempResult = num_1->num->digit + num_2->num->digit;
if (carryOver != 0 ) // check to see if there is any carry
{
tempResult = carryOver+ tempResult;
carryOver = 0;
}
if (tempResult/10 != 0) // adding the carry if any and then divide by 10 if possible finally save the digit
{
carryOver = tempResult/10;
Number *temp = new Number();
temp->digit = tempResult%10;
result->num->left = temp; // result link list goes from right to left (reverse order)
temp->right = result->num;
temp->left = NULL;
result->num = temp;
}
else // if carry + last digit is a single digit add it to the list
{
Number *temp = new Number();
temp->digit = tempResult%10;
result->num->left = temp; // result link list goes from right to left (reverse order)
temp->right = result->num;
temp->left = NULL;
result->num = temp;
}
}
else // if there is no element in smaller number takes elements from the larger one
{
Number *temp = new Number;
if (carryOver != 0 ) // if there is a carry add it to the number
{
tempResult = carryOver + num_1->num->digit;
carryOver = 0;
if (tempResult/10 != 0)
{
carryOver = tempResult/10;
temp->digit = tempResult%10;
result->num->left = temp;
temp->right = result->num;
temp->left = NULL;
}
}
else
{
temp->digit = num_1->num->digit;
result->num->left = temp;
temp->right = result->num;
temp->left = NULL;
}
result->num = temp;
}
if (num_1->num->left != NULL)
num_1->num = num_1->num->left; // if larger link list has not reached end move left
if (num_2->num->left != NULL)
num_2->num = num_2->num->left; // if smaller link list has not reached end move left
}
if (carryOver != 0) // for the last carry over digit
{
Number *temp = new Number();
temp->digit = carryOver;
result->num->left = temp; // result link list goes from right to left (reverse order)
temp->right = result->num;
temp->left = NULL;
result->num = temp;
}
num_1->num = num_1->head; // set num back to head or the last digit ex: set to 4 in case of 1234
num_2->num = num_2->head; // set num back to head or the last digit ex: set to 4 in case of 1234
return result;
}
BigNumber *actualSubtract(BigNumber *num_1, BigNumber *num_2) // internal API for substraction
{
BigNumber *result = new BigNumber();
result->num->right = NULL;
short int tempResult = 0;
Number *tempnum = new Number();
BigNumber *copy = new BigNumber();
while (num_1->num->left != NULL) // copy/saves the original link
{
num_1->num = num_1->num->left;
Number *temp1 = new Number();
temp1->digit = num_1->num->digit;
copy->num->left = temp1;
temp1->right = copy->num;
temp1->left = NULL;
copy->num = temp1;
}
num_1->num = num_1->head;
while (num_1->num->left != NULL) // move in the larger number from right to left
{
if (num_2->num->left != NULL) // move in the smaller number from right to left
{
if (num_1->num->digit < num_2->num->digit) // if there is a carry subtract one from the number
{
tempnum = num_1->num->left;
while (tempnum->left != NULL && tempnum->digit >= 0) // adjust the carry over
{
if (tempnum->digit == 0)
{
tempnum->digit =9;
tempnum = tempnum->left;
}
else
{
tempnum->digit = tempnum->digit -1 ; // adjust the carry over
tempnum = tempnum->left;
}
}
if (tempnum->digit >= 0)
{
tempResult = (num_1->num->digit + 10) - num_2->num->digit;
}
if (num_1->num->left == NULL )
{
tempResult = (num_1->num->digit ) - num_2->num->digit;
}
}
else
{
tempResult = (num_1->num->digit ) - num_2->num->digit;
}
if (tempResult >= 0)
{
Number *temp = new Number();
temp->digit = tempResult;
result->num->left = temp; // move the result link list from right to left
temp->right = result->num;
temp->left = NULL;
result->num = temp;
}
}
else
{
if (num_1->num->digit >= 0)
{
tempResult = num_1->num->digit;
Number *temp = new Number();
temp->digit = tempResult;
result->num->left = temp;
temp->right = result->num;
temp->left = NULL;
result->num = temp;
}
}
if (num_1->num->left != NULL)
num_1->num = num_1->num->left; // if larger link list has not reached end move left
if (num_2->num->left != NULL)
num_2->num = num_2->num->left; // if smaller link list has not reached end move left
}
while (num_1->num->right != NULL) // copy the saved link list
{
num_1->num->digit = copy->num->digit;
copy->num = copy->num->right;
num_1->num = num_1->num->right;
}
num_1->num = num_1->head; // set num back to head or the last digit ex: set to 4 in case of 1234
num_2->num = num_2->head; // set num back to head or the last digit ex: set to 4 in case of 1234
return result;
}
public:
Number *num, *head,*tail;
bool SignBit;
BigNumber()
{
num = new Number(); // initilize the link list data structure.
head = new Number();
SignBit = false;
}
~BigNumber() // destructure to delete the list list created.
{
while (num->left != NULL) // if the head is at right most .. delete everything till the end
{
num = num->left;
delete num->right;
}
while (num->right != NULL) // if the head is at right most .. delete everything till the end
{
num = num->right;
delete num->left;
}
}
int getLength (Number *num) // get the length of the link list passed.
{
head = num;
int result = 0;
while (num->left != NULL)
{
result++;
num = num->left;
}
tail = num;
return result;
}
BigNumber *Add(BigNumber *num_1, BigNumber *num_2) // public API for adding
{
BigNumber *result = new BigNumber();
if ((num_1->SignBit == false && num_2->SignBit == false) || (num_1->SignBit == true && num_2->SignBit == true))
{
if( getLength(num_1->num) > getLength(num_2->num)) // irrespective of user input it check to which is a longer number to compute
{ // if the user inputs the shorter number first then it calls the private API accordingly , vice versa
result = actualAdd(num_1, num_2);
if (num_1->SignBit == true && num_2->SignBit == true)
{
while(result->num->digit <= 0)
{
result->num = result->num->right;
}
result->num->digit = result->num->digit * -1;
}
}
else if( getLength(num_1->num) < getLength(num_2->num))
{
result = actualAdd(num_2, num_1);
if (num_1->SignBit == true && num_2->SignBit == true)
{
while(result->num->digit <= 0)
{
result->num = result->num->right;
}
result->num->digit = result->num->digit * -1;
}
}
if( getLength(num_1->num) == getLength(num_2->num))
{
result = actualAdd(num_1, num_2);
if (num_1->SignBit == true && num_2->SignBit == true)
{
while(result->num->digit <= 0)
{
result->num = result->num->right;
}
result->num->digit = result->num->digit * -1;
}
}
}
else
{
result = Subtract(num_1, num_2); // call subtract is any sign is negative
}
return result;
}
bool DetermineBigger( BigNumber *n1, BigNumber *n2 ) // to determine the larger number if the number of digits are same
{
Number *head1, *head2;
head1 = n1->num;
head2 = n2->num;
n1->num = n1->head;
n2->num = n2->head;
while (n1->num->left != NULL && n1->num->digit > n2->num->digit)
{
n1->num = n1->num->left;
n2->num = n2->num->left;
}
if (n1->num->digit < n2->num->digit)
{
n1->num= head1;
n2->num= head2;
return true;
}
else
{
n1->num= head1;
n2->num= head2;
return false;
}
}
BigNumber *Subtract(BigNumber *num_1,BigNumber *num_2) // Public API for substraction
{
BigNumber *result = new BigNumber();
num_2->SignBit = true;
if ((num_1->SignBit != true && num_2->SignBit != true) || (num_1->SignBit == false || num_2->SignBit == false))
{
if( getLength(num_1->num) > getLength(num_2->num)) // irrespective of user input it check to which is a longer number to compute
{ // if the user inputs the shorter number first then it calls the private API accordingly , vice versa
result = actualSubtract(num_1, num_2);
if (num_1->SignBit == true) // negative neagative = add with negative sign
{
while(result->num->digit <= 0)
{
result->num = result->num->right;
}
result->num->digit = result->num->digit * -1; // add negative sign in the start
}
}
else if( getLength(num_1->num) < getLength(num_2->num))
{
result = actualSubtract(num_2, num_1); // negative neagative = add with negative sign
while(result->num->digit <= 0) //remove all the leading zeros
{
result->num = result->num->right;
}
result->num->digit = result->num->digit * -1; // add negative sign in the start
}
else
{
if (DetermineBigger(num_1, num_2))
{
result = actualSubtract(num_2, num_1);
while(result->num->digit <= 0) //remove all the leading zeros
{
result->num = result->num->right;
}
result->num->digit = result->num->digit * -1; // add negative sign in the start
}
else
{
result = actualSubtract(num_1, num_2);
if (num_1->SignBit == true)
{
while(result->num->digit <= 0) //remove all the leading zeros
{
result->num = result->num->right;
}
result->num->digit = result->num->digit * -1; // add negative sign in the start
}
}
}
}
else
{
result = Add(num_1,num_2); // call add if any of the signs are negative
}
return result;
}
void CreateLinkedList() // Public API to create the link list of numbers
{
bool SBit1 = false,SBit2 = false;
cout<<"Input the Numeber and press enter when done"<<"\n";
int tempInput = 0;
while ((tempInput = getchar()) != 10 )
{
if (tempInput == 45 && SBit1 == false && SBit2 == false)
{
SignBit = true; // store the negative sign
SBit1 = true;
}
else if (tempInput < 58 && tempInput > 47)
{
Number *temp = new Number();
temp->digit = tempInput-48;
temp->left = num;
temp->right = NULL;
num->right = temp;
num = num->right;
SBit2 = true;
}
else
{
num = new Number();
SignBit = false;
SBit1 = false;
SBit2 = false;
cout<<"invalid input... re-enter the number ... press enter when done";
}
}
head = num;
cout<<"\n";
}
void DisplayLinkedList() // public API to display the link list.
{
bool flag = false;
cout<<"The result is "<<"\n";
while (num->right != NULL)
{
flag = true;
cout<<num->digit;
num = num->right;
}
if (!flag)
{
cout<<"NULL Input";
}
cout<<"\n";
}
};
int main(int argc, char *argv[])
{
BigNumber *big1 = new BigNumber(); // create an object of class BigNumber
BigNumber *big2 = new BigNumber();
BigNumber *big3 = new BigNumber();
big1->CreateLinkedList(); // take user input of numbers.
big2->CreateLinkedList();
big3 = big3->Add(big1,big2); // adds the two link list
big3->DisplayLinkedList(); // displays the link list
big3 = big3->Subtract(big1,big2); // substracts the two link list
big3->DisplayLinkedList(); // displays the link list
// ------------------------------Test cases I have considered ---------------------------------------
//---------- Ideal inputs ----------
//First number = 50 Second number = 1 --> OUTPUT = on add = 51 .... on subtract = 49
//First number = 2 Second number = 18 --> OUTPUT = on add = 20 .... on subtract = -16
//First number = 18 Second number = 2 --> OUTPUT = on add = 20 .... on subtract = 16
//---------- Ideal inputs -----------
//First number = 2 Second number = 1 --> OUTPUT = on add = 3 .... on subtract = 1 (check precession)
//First number = 20 Second number = 10 --> OUTPUT = on add = 30 ....on subtract = 10 (check precession)
//First number = 1000 Second number = 1 --> OUTPUT = on add = 1001 ....on subtract = 999 (check precession)
//
//First number = 1 Second number = 9 --> OUTPUT = on add = 10 .... subtract = -8 (check precession on addation)
//First number = 9 Second number = 1 --> OUTPUT = on add = 10 .... subtract = 8 (check precession on subtraction)
//First number = 1 Second number = 99 --> OUTPUT = on add = 100 .... subtract = 98 (check precession on addation)
//First number = 99 Second number = 1 --> OUTPUT = on add = 100 .... subtract = 98 (check precession on subtraction)
//First number = -1 Second number = -1 --> OUTPUT = on add = -2 .... subtract = -2 (negative negative = addation with negative sign)
//First number = -1 Second number = 1 --> OUTPUT = on add = 0 .... subtract = -2 (negative negative = addation with negative sign)
//First number = 001 Second number = 1 --> OUTPUT = on add = 0 .... subtract = -2 (effect of initial zeros)
//First number = -1 Second number = 001 --> OUTPUT = on add = 0 .... subtract = -2 (effect of initial zeros)
//First number = -3 Second number = 20 --> OUTPUT = on add = 17 .... subtract = -23 (general)
//First number = 3 Second number = 20 --> OUTPUT = on add = 23 .... subtract = -17 (check sign substration and addation)
//First number = 3 Second number = -20 --> OUTPUT = on add = 23 .... subtract = -17 (check sign substration and addation)
//First number = 11 Second number = 12 --> OUTPUT = on add = 23 .... subtract = -1 (if second number is larger)
//First number = 1000 Second number = 999 --> OUTPUT = on add = 1999 .... subtract = 1 (check correct carry over)
//First number = 999 Second number = 1000 --> OUTPUT = on add = 1999 .... subtract = -1 (check correct carry over)
//First number = -0 Second number = -0 --> OUTPUT = crash (invalid number)
//
//Both numbers NULL -->OUTPUT = NULL Input
//First number is NULL -->OUTPUT = on subtract = negative second number
//Second number is NULL -->OUTPUT = on add = positive first num
//Both numbers zero -->OUTPUT = 0
//First inputs is zero -->OUTPUT = add does 0+input number ....subtract = negative number
//Second input is zero -->> OUTPUT = add does + input number ... subtract = positive number
//Both the numbers same --> OUTPUT = on add it adds up the numbers ... on subtract prints the result with the precision of the larger number i.e. 0000 - 000 = 000
//Input the first number as any non number from keyboard -->OUTPUT = invalid input... re-enter the number ... press enter when done
//Input the second number as any non number from keyboard -->OUTPUT = invalid input... re-enter the number ... press enter when done
//Repeated invalid input --> OUTPUT = invalid input... re-enter the number ... press enter when done <<-- till the time rite input is made to that number
//Combination of add and subtraction with the same input --> OUTPUT = correct result.
//Puting ideal values after wrong input --> OUTPUT = correct values for both add and subtraction
// Also tried inputing large values upto 10 digit --> OUTPUT = valid valued for add and subtract
//Input the first number as any non number from keyboard -->OUTPUT = invalid input... re-enter the number ... press enter when done
//Input the second number as any non number from keyboard -->OUTPUT = invalid input... re-enter the number ... press enter when done
//Repeated invalid input --> OUTPUT = invalid input... re-enter the number ... press enter when done <<-- till the time rite input is made to that number
//Inputed large values upto 10 digit --> OUTPUT = valid values for add and subtract
//Inputed numbers upto 20 digits --> OUTPUT = i check the last numbers which were correct couldn't check the whole result.
//Inputed numbers upto 40 digits --> OUTPUT = i check the last numbers which were correct couldn't check the whole result.
//Combination of add and subtraction with the same input --> OUTPUT = correct result.
//Combination of add and subtraction with the different input for every operation(like equation )--> OUTPUT = valid result.
//Puting ideal values after wrong input --> OUTPUT = correct values for both add and subtraction
// ------------------------------test cases I have considered ---------------------------------------
include <iostream>
struct Number // structure to create a doubly link list of numbers
{
Number *right;
Number *left ;
short int digit;
};
class BigNumber // Class which holds functions to create, add, substract the list list
{
BigNumber *actualAdd(BigNumber *num_1, BigNumber *num_2) // internal API for adding the numbers
{
BigNumber *result = new BigNumber(); //Temporary buffer to hold the result
short int tempResult = 0, carryOver = 0; // to check carry overs and hold temporary results
while (num_1->num->left != NULL) // move in the link list .. from right to left ex number 1234 so 4321
{
if (num_2->num->left != NULL) // move in the smaller link list .. same as the above one
{
tempResult = num_1->num->digit + num_2->num->digit;
if (carryOver != 0 ) // check to see if there is any carry
{
tempResult = carryOver+ tempResult;
carryOver = 0;
}
if (tempResult/10 != 0) // adding the carry if any and then divide by 10 if possible finally save the digit
{
carryOver = tempResult/10;
Number *temp = new Number();
temp->digit = tempResult%10;
result->num->left = temp; // result link list goes from right to left (reverse order)
temp->right = result->num;
temp->left = NULL;
result->num = temp;
}
else // if carry + last digit is a single digit add it to the list
{
Number *temp = new Number();
temp->digit = tempResult%10;
result->num->left = temp; // result link list goes from right to left (reverse order)
temp->right = result->num;
temp->left = NULL;
result->num = temp;
}
}
else // if there is no element in smaller number takes elements from the larger one
{
Number *temp = new Number;
if (carryOver != 0 ) // if there is a carry add it to the number
{
tempResult = carryOver + num_1->num->digit;
carryOver = 0;
if (tempResult/10 != 0)
{
carryOver = tempResult/10;
temp->digit = tempResult%10;
result->num->left = temp;
temp->right = result->num;
temp->left = NULL;
}
}
else
{
temp->digit = num_1->num->digit;
result->num->left = temp;
temp->right = result->num;
temp->left = NULL;
}
result->num = temp;
}
if (num_1->num->left != NULL)
num_1->num = num_1->num->left; // if larger link list has not reached end move left
if (num_2->num->left != NULL)
num_2->num = num_2->num->left; // if smaller link list has not reached end move left
}
if (carryOver != 0) // for the last carry over digit
{
Number *temp = new Number();
temp->digit = carryOver;
result->num->left = temp; // result link list goes from right to left (reverse order)
temp->right = result->num;
temp->left = NULL;
result->num = temp;
}
num_1->num = num_1->head; // set num back to head or the last digit ex: set to 4 in case of 1234
num_2->num = num_2->head; // set num back to head or the last digit ex: set to 4 in case of 1234
return result;
}
BigNumber *actualSubtract(BigNumber *num_1, BigNumber *num_2) // internal API for substraction
{
BigNumber *result = new BigNumber();
result->num->right = NULL;
short int tempResult = 0;
Number *tempnum = new Number();
BigNumber *copy = new BigNumber();
while (num_1->num->left != NULL) // copy/saves the original link
{
num_1->num = num_1->num->left;
Number *temp1 = new Number();
temp1->digit = num_1->num->digit;
copy->num->left = temp1;
temp1->right = copy->num;
temp1->left = NULL;
copy->num = temp1;
}
num_1->num = num_1->head;
while (num_1->num->left != NULL) // move in the larger number from right to left
{
if (num_2->num->left != NULL) // move in the smaller number from right to left
{
if (num_1->num->digit < num_2->num->digit) // if there is a carry subtract one from the number
{
tempnum = num_1->num->left;
while (tempnum->left != NULL && tempnum->digit >= 0) // adjust the carry over
{
if (tempnum->digit == 0)
{
tempnum->digit =9;
tempnum = tempnum->left;
}
else
{
tempnum->digit = tempnum->digit -1 ; // adjust the carry over
tempnum = tempnum->left;
}
}
if (tempnum->digit >= 0)
{
tempResult = (num_1->num->digit + 10) - num_2->num->digit;
}
if (num_1->num->left == NULL )
{
tempResult = (num_1->num->digit ) - num_2->num->digit;
}
}
else
{
tempResult = (num_1->num->digit ) - num_2->num->digit;
}
if (tempResult >= 0)
{
Number *temp = new Number();
temp->digit = tempResult;
result->num->left = temp; // move the result link list from right to left
temp->right = result->num;
temp->left = NULL;
result->num = temp;
}
}
else
{
if (num_1->num->digit >= 0)
{
tempResult = num_1->num->digit;
Number *temp = new Number();
temp->digit = tempResult;
result->num->left = temp;
temp->right = result->num;
temp->left = NULL;
result->num = temp;
}
}
if (num_1->num->left != NULL)
num_1->num = num_1->num->left; // if larger link list has not reached end move left
if (num_2->num->left != NULL)
num_2->num = num_2->num->left; // if smaller link list has not reached end move left
}
while (num_1->num->right != NULL) // copy the saved link list
{
num_1->num->digit = copy->num->digit;
copy->num = copy->num->right;
num_1->num = num_1->num->right;
}
num_1->num = num_1->head; // set num back to head or the last digit ex: set to 4 in case of 1234
num_2->num = num_2->head; // set num back to head or the last digit ex: set to 4 in case of 1234
return result;
}
public:
Number *num, *head,*tail;
bool SignBit;
BigNumber()
{
num = new Number(); // initilize the link list data structure.
head = new Number();
SignBit = false;
}
~BigNumber() // destructure to delete the list list created.
{
while (num->left != NULL) // if the head is at right most .. delete everything till the end
{
num = num->left;
delete num->right;
}
while (num->right != NULL) // if the head is at right most .. delete everything till the end
{
num = num->right;
delete num->left;
}
}
int getLength (Number *num) // get the length of the link list passed.
{
head = num;
int result = 0;
while (num->left != NULL)
{
result++;
num = num->left;
}
tail = num;
return result;
}
BigNumber *Add(BigNumber *num_1, BigNumber *num_2) // public API for adding
{
BigNumber *result = new BigNumber();
if ((num_1->SignBit == false && num_2->SignBit == false) || (num_1->SignBit == true && num_2->SignBit == true))
{
if( getLength(num_1->num) > getLength(num_2->num)) // irrespective of user input it check to which is a longer number to compute
{ // if the user inputs the shorter number first then it calls the private API accordingly , vice versa
result = actualAdd(num_1, num_2);
if (num_1->SignBit == true && num_2->SignBit == true)
{
while(result->num->digit <= 0)
{
result->num = result->num->right;
}
result->num->digit = result->num->digit * -1;
}
}
else if( getLength(num_1->num) < getLength(num_2->num))
{
result = actualAdd(num_2, num_1);
if (num_1->SignBit == true && num_2->SignBit == true)
{
while(result->num->digit <= 0)
{
result->num = result->num->right;
}
result->num->digit = result->num->digit * -1;
}
}
if( getLength(num_1->num) == getLength(num_2->num))
{
result = actualAdd(num_1, num_2);
if (num_1->SignBit == true && num_2->SignBit == true)
{
while(result->num->digit <= 0)
{
result->num = result->num->right;
}
result->num->digit = result->num->digit * -1;
}
}
}
else
{
result = Subtract(num_1, num_2); // call subtract is any sign is negative
}
return result;
}
bool DetermineBigger( BigNumber *n1, BigNumber *n2 ) // to determine the larger number if the number of digits are same
{
Number *head1, *head2;
head1 = n1->num;
head2 = n2->num;
n1->num = n1->head;
n2->num = n2->head;
while (n1->num->left != NULL && n1->num->digit > n2->num->digit)
{
n1->num = n1->num->left;
n2->num = n2->num->left;
}
if (n1->num->digit < n2->num->digit)
{
n1->num= head1;
n2->num= head2;
return true;
}
else
{
n1->num= head1;
n2->num= head2;
return false;
}
}
BigNumber *Subtract(BigNumber *num_1,BigNumber *num_2) // Public API for substraction
{
BigNumber *result = new BigNumber();
num_2->SignBit = true;
if ((num_1->SignBit != true && num_2->SignBit != true) || (num_1->SignBit == false || num_2->SignBit == false))
{
if( getLength(num_1->num) > getLength(num_2->num)) // irrespective of user input it check to which is a longer number to compute
{ // if the user inputs the shorter number first then it calls the private API accordingly , vice versa
result = actualSubtract(num_1, num_2);
if (num_1->SignBit == true) // negative neagative = add with negative sign
{
while(result->num->digit <= 0)
{
result->num = result->num->right;
}
result->num->digit = result->num->digit * -1; // add negative sign in the start
}
}
else if( getLength(num_1->num) < getLength(num_2->num))
{
result = actualSubtract(num_2, num_1); // negative neagative = add with negative sign
while(result->num->digit <= 0) //remove all the leading zeros
{
result->num = result->num->right;
}
result->num->digit = result->num->digit * -1; // add negative sign in the start
}
else
{
if (DetermineBigger(num_1, num_2))
{
result = actualSubtract(num_2, num_1);
while(result->num->digit <= 0) //remove all the leading zeros
{
result->num = result->num->right;
}
result->num->digit = result->num->digit * -1; // add negative sign in the start
}
else
{
result = actualSubtract(num_1, num_2);
if (num_1->SignBit == true)
{
while(result->num->digit <= 0) //remove all the leading zeros
{
result->num = result->num->right;
}
result->num->digit = result->num->digit * -1; // add negative sign in the start
}
}
}
}
else
{
result = Add(num_1,num_2); // call add if any of the signs are negative
}
return result;
}
void CreateLinkedList() // Public API to create the link list of numbers
{
bool SBit1 = false,SBit2 = false;
cout<<"Input the Numeber and press enter when done"<<"\n";
int tempInput = 0;
while ((tempInput = getchar()) != 10 )
{
if (tempInput == 45 && SBit1 == false && SBit2 == false)
{
SignBit = true; // store the negative sign
SBit1 = true;
}
else if (tempInput < 58 && tempInput > 47)
{
Number *temp = new Number();
temp->digit = tempInput-48;
temp->left = num;
temp->right = NULL;
num->right = temp;
num = num->right;
SBit2 = true;
}
else
{
num = new Number();
SignBit = false;
SBit1 = false;
SBit2 = false;
cout<<"invalid input... re-enter the number ... press enter when done";
}
}
head = num;
cout<<"\n";
}
void DisplayLinkedList() // public API to display the link list.
{
bool flag = false;
cout<<"The result is "<<"\n";
while (num->right != NULL)
{
flag = true;
cout<<num->digit;
num = num->right;
}
if (!flag)
{
cout<<"NULL Input";
}
cout<<"\n";
}
};
int main(int argc, char *argv[])
{
BigNumber *big1 = new BigNumber(); // create an object of class BigNumber
BigNumber *big2 = new BigNumber();
BigNumber *big3 = new BigNumber();
big1->CreateLinkedList(); // take user input of numbers.
big2->CreateLinkedList();
big3 = big3->Add(big1,big2); // adds the two link list
big3->DisplayLinkedList(); // displays the link list
big3 = big3->Subtract(big1,big2); // substracts the two link list
big3->DisplayLinkedList(); // displays the link list
// ------------------------------Test cases I have considered ---------------------------------------
//---------- Ideal inputs ----------
//First number = 50 Second number = 1 --> OUTPUT = on add = 51 .... on subtract = 49
//First number = 2 Second number = 18 --> OUTPUT = on add = 20 .... on subtract = -16
//First number = 18 Second number = 2 --> OUTPUT = on add = 20 .... on subtract = 16
//---------- Ideal inputs -----------
//First number = 2 Second number = 1 --> OUTPUT = on add = 3 .... on subtract = 1 (check precession)
//First number = 20 Second number = 10 --> OUTPUT = on add = 30 ....on subtract = 10 (check precession)
//First number = 1000 Second number = 1 --> OUTPUT = on add = 1001 ....on subtract = 999 (check precession)
//
//First number = 1 Second number = 9 --> OUTPUT = on add = 10 .... subtract = -8 (check precession on addation)
//First number = 9 Second number = 1 --> OUTPUT = on add = 10 .... subtract = 8 (check precession on subtraction)
//First number = 1 Second number = 99 --> OUTPUT = on add = 100 .... subtract = 98 (check precession on addation)
//First number = 99 Second number = 1 --> OUTPUT = on add = 100 .... subtract = 98 (check precession on subtraction)
//First number = -1 Second number = -1 --> OUTPUT = on add = -2 .... subtract = -2 (negative negative = addation with negative sign)
//First number = -1 Second number = 1 --> OUTPUT = on add = 0 .... subtract = -2 (negative negative = addation with negative sign)
//First number = 001 Second number = 1 --> OUTPUT = on add = 0 .... subtract = -2 (effect of initial zeros)
//First number = -1 Second number = 001 --> OUTPUT = on add = 0 .... subtract = -2 (effect of initial zeros)
//First number = -3 Second number = 20 --> OUTPUT = on add = 17 .... subtract = -23 (general)
//First number = 3 Second number = 20 --> OUTPUT = on add = 23 .... subtract = -17 (check sign substration and addation)
//First number = 3 Second number = -20 --> OUTPUT = on add = 23 .... subtract = -17 (check sign substration and addation)
//First number = 11 Second number = 12 --> OUTPUT = on add = 23 .... subtract = -1 (if second number is larger)
//First number = 1000 Second number = 999 --> OUTPUT = on add = 1999 .... subtract = 1 (check correct carry over)
//First number = 999 Second number = 1000 --> OUTPUT = on add = 1999 .... subtract = -1 (check correct carry over)
//First number = -0 Second number = -0 --> OUTPUT = crash (invalid number)
//
//Both numbers NULL -->OUTPUT = NULL Input
//First number is NULL -->OUTPUT = on subtract = negative second number
//Second number is NULL -->OUTPUT = on add = positive first num
//Both numbers zero -->OUTPUT = 0
//First inputs is zero -->OUTPUT = add does 0+input number ....subtract = negative number
//Second input is zero -->> OUTPUT = add does + input number ... subtract = positive number
//Both the numbers same --> OUTPUT = on add it adds up the numbers ... on subtract prints the result with the precision of the larger number i.e. 0000 - 000 = 000
//Input the first number as any non number from keyboard -->OUTPUT = invalid input... re-enter the number ... press enter when done
//Input the second number as any non number from keyboard -->OUTPUT = invalid input... re-enter the number ... press enter when done
//Repeated invalid input --> OUTPUT = invalid input... re-enter the number ... press enter when done <<-- till the time rite input is made to that number
//Combination of add and subtraction with the same input --> OUTPUT = correct result.
//Puting ideal values after wrong input --> OUTPUT = correct values for both add and subtraction
// Also tried inputing large values upto 10 digit --> OUTPUT = valid valued for add and subtract
//Input the first number as any non number from keyboard -->OUTPUT = invalid input... re-enter the number ... press enter when done
//Input the second number as any non number from keyboard -->OUTPUT = invalid input... re-enter the number ... press enter when done
//Repeated invalid input --> OUTPUT = invalid input... re-enter the number ... press enter when done <<-- till the time rite input is made to that number
//Inputed large values upto 10 digit --> OUTPUT = valid values for add and subtract
//Inputed numbers upto 20 digits --> OUTPUT = i check the last numbers which were correct couldn't check the whole result.
//Inputed numbers upto 40 digits --> OUTPUT = i check the last numbers which were correct couldn't check the whole result.
//Combination of add and subtraction with the same input --> OUTPUT = correct result.
//Combination of add and subtraction with the different input for every operation(like equation )--> OUTPUT = valid result.
//Puting ideal values after wrong input --> OUTPUT = correct values for both add and subtraction
// ------------------------------test cases I have considered ---------------------------------------
forgot to add ... also test your code.
- Roy October 09, 2009