Amazon Qualcomm Interview Question
Software Engineer / DevelopersCountry: India
Interview Type: In-Person
using recursion here is an overkill (also giving that the lists can be of arbitrary length). can be done within a single loop
I first find the difference in length of both linked lists and save this value in a variable called state. If state is positive, the first list is longer, if it's negative, the second list is longer and if it's 0, their lengths are equal.
To handle the carry properly, and to handle the difference in length, we need to do the addition starting from the end of the lists. So, I wrote a recursive function (Add2) that gets the then current head of the linked lists, a reference to int to pass the carry, and the value of the state variable. As long as the state variable is nonzero, we know that the two linked lists this function gets are not equal in length. That's why if the state variable is positive, we only add the value from the first linked list and if the state variable is negative, we only add the value from the second linked list.
The critical part happens here. Note that we only advance the pointer of the longer linked list while recursively calling Add2 at this point. The other important part is updating the state variable for the next call. We either increment or decrement the state value (whichever brings it closer to 0).
Only if they are equal in length, we add both of them and advance both pointers for the next call of Add2.
After we do the additions, we update the value of that node to be less than 10, and calculate the new carry. Since the carry variable is a reference, we can successfully pass this value to the previous call of our function. At the end, Add2 returns the head of the then current result. Inside Add, we also need to take care of the carry for cases where the result has more digits than both the first linked list and second linked list (e.g: 999+1). So if the carry is greater than 0, we create another node and put that node at the head of the resulting list.
In interviews like that of Amazon, please don't expect the interviewer to give the expected complexity, etc. They want us to give an optimal solution. Gone are the days of merely solving problems. This is the time of scalability. So better make ur solutions how-much-ever optimal in the first go itself. My own experience with Amazon, I had high hopes, but they said, my problem solving skills are bad, though i gave all solutions. But not optimal ones.
There could be multiple approaches. Two of them are listed below:
Approach 1: Convert the linked lists to numbers. Add them. And then convert back the resultant number to a linked list.
Approach 2: Take two stacks and push a linked list to a stack. After done pushing, simply start popping the stacks, add the numbers, get the carry over, generate another node with the result and add to front to a new linked list.
I prefer the second approach as this is less prone to errors while coding and faster when in-built library functions for stacks are used, although it takes memory with order of m+n where m and n are lengths of the linked lists.
1)I don't think they would allow you to do that. If you were to add numbers, he would have given the numbers.
2)Stacks is more like reversing the linked list and then adding them up. He asked to avoid reversing the linked list.
The first approach might lead to overflow if the list is too huge such that the sum of its elements is beyond the range of int/long.
The second approach is the only one that looks achievable. we can do something like this:
1. find the length of 2 lists => len_l1 and len_l2(lets say len_l1 > len_l2)
2. traverse the bigger list skipping (len_l1 - len_l2) nodes in l1.
3. now keep pushing teh current top of each list into the stack and call step 3 recursively passing (l1->next, l2->next).
4. in the recursive method implementing step 3, check if(nodeFromListOne->next == NULL && nodeFromListTwo->next == NULL). if so, this is the last node and we must start returning (popping from stack) after this instead of contuining with recusrion.
5. return the sum of digitList1 and digitList2 as well as the carryover value.
6. in the caller stack (to whom these values are returned), use the carry over value returned for summation again. also to store the sum, we can either create a new list or update either list1 or list 2 with the sum
if input is like more than 9000000000000000000 u should not have data type to store this as number
manjunath426jc:
The difference between the recursive solution by 'crdmp' and the 2nd approach of 'Victor' is that in recursive solution, the system(language-library and/or OS) will maintain a stack where as in 'Victor' case the program will explicitly maintain a stack.
To me none of them are reversing the list and using explicit stack is always better than a recursive solution since system's method stack consumes more memory and cause performance overhead than explicit stack maintenance.
In fact my vote goes to Victor's 2nd approach.
/*Solution Code to algorithm suggested by lanse.cse
1. reverse the lists.
2. add them digit by digit and construct the result list.
3. reverse the result list.
NOTE: This code demonstrates the solution. The code will fail for invalid or no input and maybe other cases. Output for the following code : 9,1,3,1,3,8
*/
#include <iostream>
using namespace std;
//! Node to store digits
struct Node{
short digit; //doesn't make a difference if I use short or int
Node* next;
};
//!Function reverses an input list
void reverseList(Node*& head){
Node* curr = head;
Node* nxt = head->next;
curr->next = NULL;
while(true){
head = nxt;
if(head->next==NULL){
head->next = curr;
break;
}
nxt = nxt->next;
head->next = curr;
curr = head;
}
}
//! Function to compute the sum of two input lists. Complexity: O(m+n), sizes of lists m,n
void sumOfLists(Node*& list1, Node*& list2, Node*& result){
// Reverse lists: Time: O( m + n). operating on input lists to save space complexity
reverseList(list1);
reverseList(list2);
Node* ptr;
ptr = new Node();
result = ptr;
int n1=0,n2=0,sum=0,carry=0;
bool n1flag=true,n2flag=true;
while(n1flag || n2flag){
n1= n1flag?list1->digit:0;
n2 = n2flag?list2->digit:0;
sum = n1+n2+carry;
carry = (sum>=10)?1:0;
ptr->digit = (sum-10*carry);
if(n1flag)
if(list1->next==NULL)
n1flag = false;
else
list1 = list1->next;
if(n2flag)
if(list2->next==NULL)
n2flag = false;
else
list2 = list2->next;
if(n1flag || n2flag){
ptr->next = new Node();
ptr = ptr->next;
}else
ptr->next = NULL;
}
reverseList(result);
}
void printListValues(Node*& list){
Node* ptr=list;
do{
cout<<ptr->digit<<",";
ptr = ptr->next;
}while(ptr->next!=NULL);
cout<<ptr->digit<<endl;
}
int main(){
//construct two lists, replace the below digits to test your values
int myNum1[] = {9,1,2,3,2,9};//First list 912329,
int myNum2[] = {0,8,0,9}; //second list 0809
Node *newNd1, *num1, *num2, *result;
newNd1=new Node;num1 = newNd1;
int sz = sizeof(myNum1) / sizeof(int);
for(int i=0;i<sz;++i){
newNd1->next = (i==sz-1)?NULL:(new Node);
newNd1->digit = myNum1[i];
newNd1=newNd1->next;
}
newNd1 = new Node;num2 = newNd1;
sz = sizeof(myNum2) / sizeof(int);
for(int i=0;i<sz;++i){
newNd1->digit = myNum2[i];
newNd1->next = (i==sz-1)?NULL:(new Node);
newNd1=newNd1->next;
}
//Find sum
sumOfLists(num1,num2,result); //. Result should be 913138
printListValues(result);
}
how abt this idea?
first we will fetch the lengths. then we will add 0's in the heads place of smaller linkedlist till the lingth of both becomes same..
lets assume linked list numbers are 999 and 999
the heads 99(this 9,9 are both the heads of two linked lists) will become 18. we will keep 18 . bein in the same place , we will calculate , the next's su, if there is carry , we will increment , the currnt number.then we will move to next. will repeat the same while ->next != null.
I have a feeling that the question is not complete. because here's a bruteforce O(n) solution.
Assume 'n' elements in each linked list,
construct an array from each linked list,
start from the end of the arrays and keep adding elements and storing into another array with carry. The max size of the second array can be 2n.
Build another linked list from the result array.
Time complexity: O(n + n + 2n + 2n) => O(6n) => O(n)
Space complexity: O(n + n + 2n) => O(4n) => O(n)
so what are we trying to optimize? space , time ? or something else?
So can we just process the linked lists and get the number? I.e. multiply by 10 for each -> next. Or are we assuming the numbers are just too big to fit in a long?
lets say the numbers are 1->2->3 and 1->2
After reversing the lists look like 3->2->1 and 2->1
Now add the two lists node by node and properly take care of the carry over of the addition of the nodes, if any.
so, the resultant added list will look like 5->3->1
Now reverse the "resultant added list" to get the result of addition of two original lists. That is 1->3->5 is the actual answer.
For addition, instead of reversing the link list, shouldn't we make the exact no by traversing through the list. because if we reverse the link list we are changing the input also.
And building the exact number is easier than reversing the link list.
take your example itself.
1->2->3.
no will be= (1*10+2)*10+3=123
1->2
no will be= 1*10+2=12
now add the nos= 123+12=135.
Store the resulting number in Link list. that can be done in reverse order. (because we will do divide by 10).
then reverse this Link List.
In this approach we don't have to worry about carry over also.
Please suggest.
ashpiy, how would handle the number if it exceeds the integer range..how would you store the numbers before addition and the result after addition..?
Guys, there is some amount of repeated code. Any optimized version would be highly appreciated..
Please suggest any other better approach..
Time Complexity is O(n).
#include <stdio.h>
#include <stdlib.h>
struct Number
{
int key;
struct Number* next;
};
typedef struct Number node;
void createDigits(node **);
void printDigits(node *);
void reverseDigits(node **);
void addDigits(node *, node *, node **);
int main()
{
node* head1 = NULL;
node* head2 = NULL;
node* head3 = NULL;
printf("Create the first number..\n");
createDigits(&head1);
if(head1 == NULL)
{
printf("First Input is not correct..\n");
return 1;
}
printf("Create the second number..\n");
createDigits(&head2);
if(head2 == NULL)
{
printf("Second Input is not correct..\n");
return 1;
}
printf("Number 1: \n");
printDigits(head1);
printf("\n");
printf("Number 2: \n");
printDigits(head2);
printf("\n");
printf("Number 1 reversed..\n");
reverseDigits(&head1);
printDigits(head1);
printf("\n");
printf("Number 2 reversed..\n");
reverseDigits(&head2);
printDigits(head2);
printf("\n");
printf("Add the two reversed numbers node by node..\n");
addDigits(head1, head2, &head3);
printf("Reversing the result to get the actual result..\n");
reverseDigits(&head3);
printf("sum of two numbers in linked representation is: \n");
printDigits(head3);
printf("\n");
return 0;
}
void createDigits(node **list)
{
int digit = 0;
node* tNode = NULL;
printf("Enter positive digits to insert..(enter -999 to exit)\n");
scanf("%d",&digit);
if(digit == -999)
{
printf("Input completed..\n");
}
else
{
if(NULL == *list)
{
*list = (node *)malloc(sizeof(node));
(*list)->key = digit;
(*list)->next = NULL;
createDigits(list);
}
else
{
tNode = *list;
while(tNode->next != NULL)
tNode = tNode->next;
tNode->next = (node *)malloc(sizeof(node));
tNode = tNode->next;
tNode->key = digit;
tNode->next = NULL;
createDigits(list);
}
}
}
void printDigits(node* list)
{
if(list->next != NULL)
{
printf("%d->",list->key);
printDigits(list->next);
}
else if(list->next == NULL && list->key != -999)
{
printf("%d\n",list->key);
}
else
{
printf("Empty List..\n");
}
}
void reverseDigits(node** list)
{
node* temp1 = *list;
node* temp2 = NULL;
node* temp3 = NULL;
while(temp1)
{
*list = temp1;
temp2 = temp1->next;
temp1->next = temp3;
temp3 = temp1;
temp1 = temp2;
}
//return *list;
}
void addDigits(node* head1, node* head2, node** head3)
{
node* temp = NULL;
int keyVal = 0;
static int pass = 0;
if(head1 != NULL && head2 != NULL)
{
keyVal = head1->key + head2->key + pass;
if(*head3 == NULL)
{
*head3 = (node *)malloc(sizeof(node));
if(*head3 == NULL)
{
printf("Memory Allocation Failed..\n");
}
if(keyVal >= 10)
{
(*head3)->key = keyVal-10;
pass = 1;
}
else
{
(*head3)->key = keyVal;
pass = 0;
}
(*head3)->next = NULL;
}
else
{
temp = *head3;
while(temp->next != NULL)
temp = temp->next;
temp->next = (node *)malloc(sizeof(node));
if(temp->next == NULL)
{
printf("Memory Allocation Failed..\n");
}
temp = temp->next;
if(keyVal >= 10)
{
temp->key = keyVal-10;
pass = 1;
}
else
{
temp->key = keyVal;
pass = 0;
}
temp->next = NULL;
}
head1 = head1->next;
head2 = head2->next;
addDigits(head1, head2, head3);
}
else if(head1 == NULL && head2 != NULL)
{
keyVal = head2->key + pass;
if(*head3 == NULL)
{
*head3 = (node *)malloc(sizeof(node));
if(*head3 == NULL)
{
printf("Memory Allocation Failed..\n");
}
if(keyVal >= 10)
{
(*head3)->key = keyVal-10;
pass = 1;
}
else
{
(*head3)->key = keyVal;
pass = 0;
}
(*head3)->next = NULL;
}
else
{
temp = *head3;
while(temp->next != NULL)
temp = temp->next;
temp->next = (node *)malloc(sizeof(node));
if(temp->next == NULL)
{
printf("Memory Allocation Failed..\n");
}
temp = temp->next;
if(keyVal >= 10)
{
temp->key = keyVal%10;
pass = 1;
}
else
{
temp->key = keyVal;
pass = 0;
}
temp->next = NULL;
}
head2 = head2->next;
addDigits(head1, head2, head3);
}
else if(head1 != NULL && head2 == NULL)
{
keyVal = head1->key + pass;
if(*head3 == NULL)
{
*head3 = (node *)malloc(sizeof(node));
if(*head3 == NULL)
{
printf("Memory Allocation Failed..\n");
}
if(keyVal >= 10)
{
(*head3)->key = keyVal-10;
pass = 1;
}
else
{
(*head3)->key = keyVal;
pass = 0;
}
(*head3)->next = NULL;
}
else
{
temp = *head3;
while(temp->next != NULL)
temp = temp->next;
temp->next = (node *)malloc(sizeof(node));
if(temp->next == NULL)
{
printf("Memory Allocation Failed..\n");
}
temp = temp->next;
if(keyVal >= 10)
{
temp->key = keyVal-10;
pass = 1;
}
else
{
temp->key = keyVal;
pass = 0;
}
temp->next = NULL;
}
head1 = head1->next;
addDigits(head1, head2, head3);
}
else if(pass == 1)
{
temp = *head3;
while(temp->next != NULL)
temp = temp->next;
temp->next = (node *)malloc(sizeof(node));
if(temp->next == NULL)
{
printf("Memory Allocation Failed..\n");
}
temp = temp->next;
temp->key = pass;
temp->next = NULL;
}
}
How about:
sum = atoi(list1) + atoi(list2)
where atoi is modified version that operates on list of numbers.
Then, itoa(sum), which ouputs as a list of numbers.
Is the following rephrase of th equestion correct (rephrased/introduced words in quotes):
You have two "set" of numbers represented by "two" linked lists, where each node contains a single digit. Write a function that adds the two numbers "in the corresponding nodes" and returns the sum as a "third" linked list
By reversing LinkList is very lengthy.
We have two Linklist A and B of length x and y(we can find length by simple traversing)
Now There may be three condition:(x=y,x>y,x<y):
_____________________________________________________________________________________
[1]:length of list A and length of List B are same (x=y):
In this case we can use simple recursion which will start from the end of list and proceed to front.recursive function will return carry digit(1 OR 0).
**********
+
**********
=
**********
NOTE: '*' can be any digit (0-9)
____________________________________________________________________________________
[2]:if length of List A is greater then length of list B(x>y):
In this case we will divide our bigger link list into two part (A1 and A2).First part(A1) will be of length (x-y) and second part(A2) will be of length (y). Now second part(A2) of List A and B are of same length (y).we can add it by simple recursion as we did in condition [1].After adding these two (A2 and B) we will append first part(A1) of list A if there is not carry digit in (A2+B).If there is any carry digit in (A2+B) we will apply recursion this time in first part(A1)of A
and add one at the end of A1 and then appent the modified A'1 with (A2+B).We will get A'1(A2+B).The resultent sum.
*******************(x) *******A1(x-y) ************A2(y)
+ + ************B(y)
**********(y)
= *******A1(x-y) ************[A2+B](y)
=
*****************(x) = *****************[A1][A2+B](x)
___________________________________________________________________________________
[3]:if length of List A is lesser then length of list B(x<y):
Same as condition [2] by replacing x with y.
Recursive Function:
int addTwoList(node *A,node *B)
{
int i=0;;
if(A->link!=NULL)
{
A=A->link;
B=B->link;
i=addTwoList(node *A,node *B);
}
A->info=A->info+B->info+i;//assigning addition into A.(A=A+B).
if(A->info>9)
{
i=1;
}
return i;
}
__________________________________________________________________________________
***Ignore the above solutions***
Simple solution. Complexity - O(n)
reverse(linkedlist_of_Num1)
reverse(linkedlist_of_Num2)
int carry = 0;
while(nodenum1->next!=null or nodenum2->next!=null)
{
addition = carry + nodenum1->data + nodenum2->data;
carry = (nodenum2->data)/ 10;
nodenum2->data = addition - (carry*10)
}
//Copy the remaining elements of larger list in the nodenum2
//reverse the resultant
reverse(nodenum2)
Guys Here is a solution without reversing the link lists
Time Complexity = O(n)
Works for any length of linked lists
l1 = length_linklist(head1);
l2 = length_linklist(head2);
while(l1<l2){
temp = create_node(0);
temp->next = head1;
head1 = temp;
l1++;
}
while(l2<l1){
temp = create_node(0);
temp->next = head2;
head2 = temp;
l2++;
}
add(head1,head2);
My add function
void add(node *head1,node *head2){
if(head1!=NULL){
add(head1->next,head2->next);
int sum = head1->val+head2->val;
head1->val = sum%10+carry;
carry = sum/10;
}
}
Guys Here is a solution without reversing the link lists
Time Complexity = O(n)
Works for any length of linked lists
l1 = length_linklist(head1);
l2 = length_linklist(head2);
while(l1<l2){
temp = create_node(0);
temp->next = head1;
head1 = temp;
l1++;
}
while(l2<l1){
temp = create_node(0);
temp->next = head2;
head2 = temp;
l2++;
}
add(head1,head2);
My add function
void add(node *head1,node *head2){
if(head1!=NULL){
add(head1->next,head2->next);
int sum = head1->val+head2->val;
head1->val = sum%10+carry;
carry = sum/10;
}
}
Can perform this, by traversing the two lists and getting the two numbers. Then adding the two numbers through simple int addition and saving the result in another link list.
a. getting int
while( a != NULL)
num = num*10 + a->value;
num_final = num1+num2
get digits of final and save it in another list.
The following 'sum' method will return the requirement .
private static int sum(LinkedList l1, LinkedList l2) {
int sum = 0;
int decimal = 1;
int max = 0, min = 0;
if (l1.size() > l2.size()) {
max = l1.size() - 1;
min = l2.size() - 1;
} else {
max = l2.size() - 1;
min = l1.size() - 1;
}
for (int i = max; i >= 0; i--) {
if ((l1.size() - 1) == max) {
sum = sum + (decimal * (Integer) (l1.get(i)));
} else {
if (min >= 0) {
sum = sum + (decimal * (Integer) (l1.get(min)));
min--;
}
}
if ((l2.size() - 1) == max) {
sum = sum + (decimal * (Integer) (l2.get(i)));
} else {
if (min >= 0) {
sum = sum + (decimal * (Integer) (l2.get(min)));
min--;
}
}
decimal = decimal * 10;
}
return sum;
}
AnanthaNag KUNDANALA
point is you accumulate your resulting sum in an integer (not in a list) consider adding two very long lists like
1->1->1->1-> ... ->1->1
got you. So, I guess replacing 'int' with some other bigger primitive datatype (like long), I will be in safe side. Is n't it ?
well, probably this stuff should be clarified with an interviewer:
this also shows that you are aware of the problem..
if the lists contain thousands of nodes, any standard number type would give an overflow, thus the general solution is to use a list for the resulting sum as well
yup. thanks a ton for enlightenment. Till now, I never thought of overflow of additions & other mathematical operations with respect to the range of the primitive datatypes. Thanks once again.
And may I have you in my mail contacts list? If you have no issues to be in my contacts, please revert me at kundanala@gmail.com
let me try this...
start parsing both the link list one node at a time.. to find out which is the largest one and what is the diff in the length..
suppose list1 1->2->3->4
and list2 5->3->4->6->9->2->1
given example L1=4 L2=7 and diff=3
create a function like below..
it can be passed to function
Node* add_node(Node *N1,Node *N2,size)
{
static int carry;
int sum,remainder;
Node *temp_node;
if(N1==NULL || N2==NULL)
return NULL;
if(size<=diff)
{
size++;
temp_node=(Node*)malloc(sideof(Node*));
temp_node->next=add_node(N1,N2->next,size);
sum=N2->value+carry;
}
else
{
size++;
temp_node=(Node*)malloc(sideof(Node*));
temp_node->next=add_node(N1->next,N2->next,size);
sum=N1->value+N2->value+carry;
}
carry=sum/10;
remainder=sum%10;
temp_node->value=remainder;
return temp_node;
}
tere might more exception handling and we need to take care.. but this is my over all idea..
typedef struct list_t{
int x;
struct list_t* next;
} list_t;
// add two lists and return a list
list_t* add(list_t* A, list_t *B){
int s;
list_t* least=NULL; //pointer to the sum list least impotant digit
list_t* most=NULL; //pointer to the sum list most impotant digit
list_t* tmp=NULL;
// while there are 2 digits, add them
while( A != NULL && B != NULL){
s = A->x + B->x;
// initialize sum list
tmp = malloc(sizeof(list_t));
if(least == NULL){
least = most = tmp;
}
// add either 1 or 2 digits
if(s<9){
tmp->x = s;
tmp->next = NULL;
most->next=tmp;
most=tmp;
}
else{
tmp->x = s -10;
tmp->next = malloc(sizeof(list_t));
tmp->next->x = 1;
tmp->next->next=NULL;
most->next=tmp;
most=tmp->next;
}
A=A->next;
B=B->next;
}
while( A != NULL ){
most->next=malloc(sizeof(list_t));
most->next->x = A->x;
A = A->next;
most = most->next;
}
while( B != NULL ){
most->next=malloc(sizeof(list_t));
most->next->x = A->x;
B = B->next;
most = most->next;
}
return least;
}
LinkedList<Integer> ll = new LinkedList<Integer>();
ll.add(9);
ll.add(9);
ll.add(9);
LinkedList<Integer> ll1 = new LinkedList<Integer>();
ll1.add(9);
ll1.add(9);
ll1.add(9);
ll1.add(5);
int num1 = 0;
int num2 = 0;
for(int i =ll1.size()-1 ; i>=0;i-- ){
int temp = ll1.get(i);
for(int j =0;j<i;j++){
temp=temp*10;
}
num1=num1+temp;
}
System.out.println(num1);
for(int i =ll.size()-1 ; i>=0;i-- ){
int temp = ll1.get(i);
for(int j =0;j<i;j++){
temp=temp*10;
}
num2=num2+temp;
}
System.out.println(num2);
System.out.println("num1+num2 = "+(num1+num2));
This should do!!
// Sum 2 lists
struct node* sum2LL(struct node* head1, struct node* head2)
{
struct node* head = NULL;
struct node* headcopy = head1;
int carry = 0, sum = 0;
if(head1 == NULL && head2 == NULL)
return NULL;
else if(head1 == NULL && head2 != NULL)
return head2;
else if(head1 != NULL && head2 == NULL)
return head1;
else
{
// Both list have elements
while(head1 != NULL && head2 != NULL)
{
printf("head1->data : %d head2->data : %d Carry : %d\n", head1->data, head2->data, carry);
sum = head1->data + head2->data + carry;
if(sum > 9)
{
carry = (sum % 10) + 1 ;
printf("Sum : %d Carry : %d\n", sum, carry);
sum = sum - carry;
}else
carry = 0;
printf("Sum : %d Carry : %d\n", sum, carry);
// First node
if(headcopy == head1)
head = createNode(sum);
else
addTail(&head, sum);
head1 = head1->next;
head2 = head2->next;
}
// Both of them are empty
if(head1 == NULL && head2 == NULL)
{
if(carry == 0)
return head;
else
{
addTail(&head, carry);
return head;
}
}
//Only Head1 is empty
else if(head1 == NULL && head2 != NULL)
{
if(carry == 0)
{
struct node* tail = findTail(head);
tail->next = head2;
}
else
{
while(head2 != NULL)
{
sum = head2->data + carry;
if(sum > 9)
{
carry = (sum % 10) + 1 ;
sum = sum - carry;
}
else
carry = 0;
addTail(&head, sum);
head2 = head2->next;
}
}
return head;
}
// Only head2 is NULL
else if(head1 != NULL && head2 == NULL)
{
if(carry == 0)
{
struct node* tail = findTail(head);
tail->next = head1;
}
else
{
while(head1 != NULL)
{
sum = head1->data + carry;
if(sum > 9)
{
carry = (sum % 10) + 1 ;
sum = sum - carry;
}
else
carry = 0;
addTail(&head, sum);
head1 = head1->next;
}
}
return head;
}
}
}
Hope this solution will also work.
step 1: Calculate the length of both LinkList , say L1 and L2
step 2: Calculate the difference d, and find out which is longer.
step 3: Traverse the longer List for 'd' number of nodes.
step 4: Now start adding the nodes value of both LinkList and keep the Sum in longer List L1.
step 5: This way longer List L1 will have the its own starting number and Sum of each digit.
step 6: Finally create a function which have 'carry' as Static variable and traverse from end of a linklist using recursion. Use mod function to get the 'carry' part of each node starting from the end. And add this carry to previous node(in recursion). this way carry will propagate in backward direction.
step 7: If the carry still have some value when we come to first node then create a new node and add to the starting of the Linklist.
What say Guys..?
reverse both the list, soppose l1 = 1->2->9 and l2= 8->9
so l1 = 9->2->1 and l2 = 9-> 8
add the first elements of both list 9 + 9 = 18 put it in the stack
add second element until all the elements are empty and put it in the queue so queue become
18, 10,1
then dequeue up element if greater than 10, then remove 10 and add 1 for the next element
so it become 8, (10+1) = 11-10 =1 , 1+1 = 2 and then put it a new list become 8->1->2
now reverse the list = 2->1->8
hope this is clear
With the reversing->adding->reversing we need 5 iterations (i.e., revering two list, adding two list and reversing the resultant list).
Instead why not add the lists in the forward direction creating add-list and carry-list, then add the add-list and carry-list to get the final list. (Note: we need to iterate both the list to find the respective lengths first).
lets try this way Sum: 9999 + 9999
Add-list is 088888 and the carry list is 111110 and adding this list will give us 199998.
Complicity is 4 iterations (2 iterations to identify the length of the lists and 2 iterations for adding).
Here's my tail recursive version, which doesn't require first finding the lengths, first reversing, converting the lists to numbers, or using additional data structures such as Stack etc. It won't handle the case of overflow, so I might be solving an easier version of this problem.
The approach is to use 2 additional parameters (num & num2) to keep track of the current values we have seen for both lists. Code should be self-explanatory enough...
static int sum(Node n, Node n2, int num, int num2) {
if(n == null && n2 == null)
return num+num2;
else if(n == null)
return sum(null, n2.next, num, 10*num2 + n2.value);
else if(n2 == null)
return sum(n.next, null, 10*num + n.value, num2);
else return sum(n.next, n2.next, 10*num + n.value, 10*num2 + n2.value);
}
int addLists (node* list1, node* list2)
{
int add1=0, add2=0, final=0;
while (list1->next != NULL && list2->next!= NULL)
{
add1 = add1*10 + list1->value;
add2 = add2*10 + list2 -> value;
if(list1->next != NULL) list1 = list1->next;
else final += add1;
if(list2->next != NULL) list2 = list2->next;
else final += add2;
}
return final;
}
This problem can be solved using stack.
Step1: Insert all the elements in the list1 into a stack say s1
Step2: Insert all the elements in the list2 into a stack say s2
Step3:
int val1,val2,carry=0;
while(!s1.empty() || !s2.empty())
{
val1=0;
val2=0;
if(!s1.empty())
{
val1=s1.top();
s1.pop();
}
if(!s2.empty())
{
val2=s2.top();
s2.pop();
}
if(val1+val2+carry> 10)
{
carry=1;
insertintoll((val1+val2+carry)-10);
}
else
{
carry=0;
insertintoll((val1+val2+carry));
}
}
Note: insertintoll() function inserts the value to the front of the new linked list
Here is the code from k2code.blogspot.in/2009/12/write-program-to-add-two-long-positive.html:
node *long_add(mynode *h1, mynode *h2, mynode *h3) //h3 = h2+h1
{
node *c, *c1, *c2;
int sum, carry, digit;
carry = 0;
c1 = h1->next;
c2 = h2->next;
while(c1 != h1 && c2 != h2)
{
sum = c1->value + c2->value + carry;
digit = sum % 10;
carry = sum / 10;
h3 = insertNode(digit, h3);
c1 = c1->next;
c2 = c2->next;
}
if(c1 != h1)
{
c = c1;
h = h1;
}
else
{
c = c2;
h = h2;
}
while(c != h)
{
sum = c->value + carry;
digit = sum % 10;
carry = sum / 10;
h3 = insertNode(digit, h3);
c = c->next;
}
if(carry==1)
{
h3 = insertNode(carry, h3);
}
return(h3);
}
private static LinkedList listSum(LinkedList num1, LinkedList num2){
Deque<Integer> n1St = new ArrayDeque<Integer>();
Deque<Integer> n2St = new ArrayDeque<Integer>();
//Stack<Integer> st = new Stack<Integer>(); We resort to using ArrayDeque as it is faster than Stack
//Why is ArrayDeque faster than Stack ?
//ArrayDeque is extended from ArrayList whereas Stack is from Vector
//ArrayList is not a synchronized call & hence when we are not working with multi-threaded program, why
//take a perfromance hit by using vector, i.e., Stack
LinkedList t = num1;
while(t != null){
n1St.push(t.val);
t = t.next;
}
t = num2;
while(t != null){
n2St.push(t.val);
t = t.next;
}
int carry = 0;
int sum = 0;
LinkedList nd = new LinkedList();
nd.val = 0;
nd.next = null;
LinkedList head = nd;
LinkedList next = null;
while (!n1St.isEmpty() || !n2St.isEmpty() || (carry != 0)){
if (!n1St.isEmpty())
sum += n1St.pop();
if (!n2St.isEmpty())
sum += n2St.pop();
sum += carry;
carry = sum / 10;
sum = sum % 10;
if (next == null){
next = nd;
} else {
nd = new LinkedList();
nd.next = next;
next = nd;
}
head = nd;
nd.val = sum;
sum = 0;
}
return head;
}
Simpler recursive implementation:
private static LinkedList<int> AddNumbers(LinkedListNode<int> firstNumNode, LinkedListNode<int> secondNumNode,int carry)
{
//Base Case:
if(null == firstNumNode && null == secondNumNode)
{
//If we have done with the list but we have got Carry value, then create a na new node
//associate it with link list and return
if(carry > 0)
{
var carryNode = new LinkedListNode<int>(carry);
var newList = new LinkedList<int>();
newList.AddFirst(carryNode);
return newList;
}
else
//return null otherwise
return null;
}
//Add nodes and carry too
var tempResult = firstNumNode.Value + secondNumNode.Value + carry;
//Create a Empty List
var resultList = new LinkedList<int>();
//Create a new node using the above result assign it to the List.
var newNode = new LinkedListNode<int>(tempResult % 10);
resultList.AddFirst(newNode);
//Go ove for other nodes
var list = AddNumbers(firstNumNode.Next,secondNumNode.Next,tempResult/10);
if(null != list && null != list.First)
{
while(null != list.First)
{
var node = list.First;
//First remove the node from earlier list and then add it to result
list.Remove(list.First);
resultList.AddAfter(newNode,node);
//cache it so that next node can be added after "node"
newNode = node;
}
}
return resultList;
}
Appreciate your feedback.
#include <stdio.h>
#include<stdlib.h>
struct node
{
int data;
struct node *link;
};
struct node *temp,*head=NULL;
int create(int val)
{
struct node *newnode;
newnode = (struct node*)malloc(sizeof(struct node));
newnode->data = val;
newnode->link= NULL;
if(head==NULL)
{
head = newnode;
}
else
{
temp=head;
while(temp->link!=NULL)
{
temp=temp->link;
}
temp->link= newnode;
}
return 0;
}
int display(struct node *head)
{
temp=head;
while(temp!=NULL)
{
printf("%d",temp->data);
temp=temp->link;
if(temp!=NULL)
printf("->");
}
printf("\n");
return 0;
}
struct node* reverse(struct node *head)
{
struct node* prev = NULL;
struct node* current;
struct node* next;
current=head;
while (current != NULL)
{
next = current->link;
current->link = prev;
prev = current;
current = next;
}
head = prev;
return head;
}
struct node* addlist(struct node *head1,struct node *head2)
{
int c =0,sum=0;
struct node *temp1=head1;
struct node *temp2=head2;
struct node *head3=NULL;
while(temp1!=NULL&&temp2!=NULL)
{
sum= temp1->data+temp2->data+c;
c = sum/10;
sum=sum%10;
struct node* newnode = (struct node*)malloc(sizeof(struct node));
newnode->data =sum;
newnode->link=NULL;
if(head3==NULL)
head3=newnode;
else
{
newnode->data =sum;
newnode->link=head3;
head3=newnode;
}
temp1=temp1->link;
temp2= temp2->link;
}
while(temp1==NULL&&temp2!=NULL)
{
sum= temp2->data+c;
c = sum/10;
sum=sum%10;
struct node* newnode = (struct node*)malloc(sizeof(struct node));
newnode->data =sum;
newnode->link=head3;
head3=newnode;
temp2= temp2->link;
}
while(temp1!=NULL&&temp2==NULL)
{
sum= temp1->data+c;
c = sum/10;
sum=sum%10;
struct node* newnode = (struct node*)malloc(sizeof(struct node));
newnode->data =sum;
newnode->link=head3;
head3=newnode;
temp1= temp1->link;
}
if((temp1==NULL||temp2==NULL)&&c>0)
{
struct node* newnode = (struct node*)malloc(sizeof(struct node));
newnode->data =c;
newnode->link=head3;
head3=newnode;
}
return head3;
}
int main()
{
int n1,n2,v,i;
printf("enter no ofnodes in 1st list\n");
scanf("%d",&n1);
for(i=0;i<n1;i++)
{
printf("enter val\n");
scanf("%d",&v);
create(v);
}
struct node *head1,*head3;
head1=head;
head=NULL;
printf("enter no ofnodes in 2nd list\n");
scanf("%d",&n2);
for(i=0;i<n2;i++)
{
printf("enter val\n");
scanf("%d",&v);
create(v);
}
struct node *head2;
head2=head;
printf("first linkedlist\n");
display(head1);
head1 = reverse(head1);
printf("second linkedlist\n");
display(head2);
head2 = reverse(head2);
head3= addlist(head1,head2);
display(head3);
//code
return 0;
}
// Find the difference between the given linked list
// assuming its d(suppose 1st linked list is larger)
Node * temp1 = first1;// For first Linked List
Node *temp2 = first 2 ;//For second Linked List
for (int i = 0; i< d; i++)
temp1 = temp->next;
// Now start adding data and keep it in single Node from the left to right side
while( Temp1 != null)
{temp1->data += temp2->data;
temp1= temp1->next;
temp2 = temp2 -> next;
}
//Now start from first node of first list and check if any node data is greater than 10 then just add 1 to the left node of this node and subtract 10 from that.Repeat till all the data of linked list is less than 10
//boundary condition if first data i s greater than 10 we need to create a separate node and link it to first and make this node as first
while (true)
{
int flag = false;
if (first->data > 10)
{
// create new node
Node newnode = malloc (sizeof(node))
newnode->data = 1;
first->data -= 10;
newnode->next = first;
first = newnode;
flag = true;
}
temp1= first;
temp2 = first->next;
while(temp2 != null)
{
if(temp2->data >= 10)
{
temp2->data = temp2->data-10;
temp->data = temp1->data+1;
temp1= temp1->next;
temp2=temp2->next;
flag = true;
}
if(flag == false)
break;
}
}
{
}
two loops.. ooh gush this is really over-engineered solution:
this can be done in a single loop: just go through the lists keeping a carry flag
How do you plan to get the carry from the least significant digit to the most significant digit in a single loop?
example: 112+888
Other than the least significant digit, none of the digits themselves generate a carry. They only generate a carry once the least significant digit is calculated and the carry moves towards the left. That's why I used recursion above. But I agree with you about nested loops. They are unnecessary, the complexity shouldn't be greater than O(n).
aah got you.. I overlooked that the numbers are originally stored in a twisted way, from most to least significant digit, while naturally it should be the other way around
I think just keep carry flag is not enough. If there are several consecutive 9s just before the current digit, then one carry should lead to change all the digits which containing 9 and one more before the consecutive 9s. Using a queue will be a good solution for me...I dont know why ppl dont like this method...
I am not sure what you're taking about..
if the nos are stored in a normal way, i.e., from least to most significant digit, then the addition can be done using the following loop:
int c = 0;
for(i = 0; i < n; i++) {
z[i] = x[i] + y[i] + c;
c = (z[i] >= 10);
if(c == 1)
z[i] -= 10;
}
keep the track of previous node of temp1.. if sum is greater than 10 then add the carry to previous node data and move previous node by next
.
while( Temp1 != null)
{temp1->data += temp2->data;
if (temp1->data > 10)
{
temp1->data = temp1->data %10;
prev->data = prev->data+1;
}
temp1= temp1->next;
temp2 = temp2 -> next;
prev= prev->next;
keep the track of previous node of temp1.. if sum is greater than 10 then add the carry to previous node data and move previous node by next
.
while( Temp1 != null)
{temp1->data += temp2->data;
if (temp1->data > 10)
{
temp1->data = temp1->data %10;
prev->data = prev->data+1;
}
temp1= temp1->next;
temp2 = temp2 -> next;
prev= prev->next;
How about starting at the head of the list and pushing the numbers in a stack as we read them.
When end of list reached, pop out numbers from the stack and multiple them with increasing powers of 10 and keep adding them to the result.
Set old number as 0, new data from link list
Now multiply old number with 10 and add link list number.
while(linklist->next != null)
Sum = old number* 10 + link list number
old number = sum
}
Answer is Sum
traver
if the question means it should be finished in one pass(no turning back), I think the point is how to take care of '9', if it's 1999, you should keep all the four digits and when the summation of next digit is 10, your current result should be be 20000.
In my opinion, after determine which list is longer and their length difference, we can keep add corresponding digits one by one from the front to rear. In the procedure, we can use a Queue to store the node pointer of all the previous nodes we need to keep tracking. If the current digit is not 9, we can give up all the previous tracked nodes in the Queue.
The rule:
If current->value==9: Queue.enqueue(9)
if current->value>9: while(!Queue.isEmpty): Queue.dequeue()->value+1 //add more necessary code to take care of carry
Queue.enqueue(current->value%10)
if current->value<9: while(!Queue.isEmpty): Queue.dequeue()
Queue.enqueue(current->value)
Following code is tested. It handles the case where first list is longer than the second, or second is longer than the first as well as when they are of equal length.
}
- crdmp December 26, 2011