Multiply Two linked list
You have given two linked list of maximum size of 100
You have to do multiply operation on linked list and produce output
Note:- use long long int to handle large number and perform modulo 10^9+7 inorder to make the number of proper size
223 21231 0 021 0
Output641000
The solution is as follows:-
Hints
1 do modulo operation on each number during joining
2 multiply two numbers and do modulo on it too otherwise its range will be overflow
3 so formula will become somewhat like this num3=((num1%10^9+7)*(num2%10^9+7)) %(10^9+7)
Code:-
1 {
2
3 #include<bits/stdc++.h>
4
5 using namespace std;
6
7
8
9 /* Linked list Node */
10
11 struct Node
12
13 {
14
15 int data;
16
17 struct Node* next;
18
19 };
20
21
22
23 /* Function to create a new Node with given data */
24
25 struct Node *newNode(int data)
26
27 {
28
29 struct Node *new_Node = (struct Node *) malloc(sizeof(struct Node));
30
31 new_Node->data = data;
32
33 new_Node->next = NULL;
34
35 return new_Node;
36
37 }
38
39
40
41
42
43 Node *reverse(Node **r)
You have to do multiply operation on linked list and produce output
Note:- use long long int to handle large number and perform modulo 10^9+7 inorder to make the number of proper size
Example(To be used only for expected output):
Input223 21231 0 021 0
Output641000
The solution is as follows:-
Hints
1 do modulo operation on each number during joining
2 multiply two numbers and do modulo on it too otherwise its range will be overflow
3 so formula will become somewhat like this num3=((num1%10^9+7)*(num2%10^9+7)) %(10^9+7)
Code:-
1 {
2
3 #include<bits/stdc++.h>
4
5 using namespace std;
6
7
8
9 /* Linked list Node */
10
11 struct Node
12
13 {
14
15 int data;
16
17 struct Node* next;
18
19 };
20
21
22
23 /* Function to create a new Node with given data */
24
25 struct Node *newNode(int data)
26
27 {
28
29 struct Node *new_Node = (struct Node *) malloc(sizeof(struct Node));
30
31 new_Node->data = data;
32
33 new_Node->next = NULL;
34
35 return new_Node;
36
37 }
38
39
40
41
42
43 Node *reverse(Node **r)
44
45 {
46
47 Node *prev =NULL;
48
49 Node *cur = *r;
50
51 Node *nxt;
52
53 while(cur!=NULL)
54
55 {
56
57 nxt = cur->next;
58
59 cur->next = prev;
60
61 prev = cur;
62
63 cur = nxt;
64
65 }
66
67 *r = prev;
68
69 }
70
71 /* Function to insert a Node at the beginning of the Doubly Linked List */
72
73 void push(struct Node** head_ref, int new_data)
74
75 {
76
77 /* allocate Node */
78
79 struct Node* new_Node = newNode(new_data);
80
81
82
83 /* link the old list off the new Node */
84
85 new_Node->next = (*head_ref);
86
87
88
89 /* move the head to point to the new Node */
90
91 (*head_ref) = new_Node;
92
93 }
94
95 void freeList(struct Node *Node)
96
97 {
98
99 struct Node* temp;
100
101 while(Node != NULL)
102
103 {
104
105 temp=Node;
106
107 Node = Node->next;
108
109 free(temp);
110
111 }
112
113 }
114
115
116
117 /* Multiply contents of two linked lists */
118
119 long long multiplyTwoLists (struct Node* , struct Node*);
120
121
122
123 // A utility function to print a linked list
124
125 void printList(struct Node *Node)
126
127 {
128
129 while(Node != NULL)
130
131 {
132
133 printf("%d ", Node->data);
134
135 Node = Node->next;
136
137 }
138
139 printf("
140
141 ");
142
143 }
144
145
146
147 /* Driver program to test above function */
148
149 int main(void)
150
151 {
152
153 int t,n,m,i,x;
154
155 cin>>t;
156
157 while(t--)
158
159 {
160
161 struct Node* first = NULL;
162
163 struct Node* second = NULL;
164
165 cin>>n;
166
167 for(i=0;i<n;i++)
168
169 {
170
171 cin>>x;
172
173 push(&first, x);
174
175 }
176
177 cin>>m;
178
179 for(i=0;i<m;i++)
180
181 {
182
183 cin>>x;
184
185 push(&second, x);
186
187 }
188
189 reverse(&first);
190
191 reverse(&second);
192
193 long long res = multiplyTwoLists(first,second);
194
195 cout<<res<<endl;
196
197 freeList(first);
198
199 freeList(second);
200
201 }
202
203 return 0;
204
205 }
206
207
208
209 }
210
211
212
213
214 long long multiplyTwoLists (Node* l1, Node* l2)
215
216 {
217
218 //Your code here
219
220 long long num1=0,num2=0,num3=0;
221
222 Node* temp1=l1,*temp2=l2;
223
224 num1=fun(num1,temp1);
225
226 num2=fun(num2,temp2);
227
228 num3=(num1*num2)%1000000007;
229
230 return num3;
231
232 }
233
234 long long fun(long long num,Node *temp)
235
236 {
237
238 if(temp==NULL) return 0;
239
240 while(1)
241
242 {
243
244 num=(num+temp->data);
245
246 num=num%(1000000007);
247
248 temp=temp->next;
249
250 if(temp==NULL)
251
252 break;
253
254 num=num*10;
255
256 }
257
258 return num;
259
260
261 }
Comments
Post a Comment