Match Number

Easy
0/40
Average time to solve is 12m
profile
Contributed by
12 upvotes
Asked in companies
Grant ThorntonOyelabsAuto Motu

Problem statement

Given two linked lists, check whether they represent the same number. Each node of the list represents part of the whole integer which needs to be matched. Return True if the lists match, otherwise return False.

Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line of the input contains an integer 'T' denoting the number of test cases.
The next '2T' line contains some integers each line denotes one linked list. 
Elements of the linked list are separated by space. A linked list is terminated by -1.
Output Format: 
For each test case, print True if the given lists match, else print False.
Note: 
You do not need to print anything, it has already been taken care of. Just implement the function and return the answer.
Constraints: 
1 <= T  <=  10
1 <= N1 <= 10^4
1 <= N2 <= 10^4

Where N1, N2 represents the length of linked list one and two respectively.

Time Limit: 1 sec
Sample Input 1:
2
0 0 1 2 -1
0 1 2 -1
43 5 678 -1
4 3 56 87 -1
Sample Output 1:
True
False
Explanation For Sample Input 1:
Here we have 2 test cases, hence there are 2 pairs, a total of 4 linked lists. The second line and third line depict the first pair and the fourth line and the fifth line depicts the second pair of the linked list.

Test Case 1: The first linked list of the first pair represents the number 0012 which is 12 and the second linked list of the first pair represents the number 012 which is 12. Because both the linked list represents the same number hence the answer is true.

Test case 2: The first linked list of the second pair represents the number 435678 and the second linked list of the second pair represents the number 435687. Because both the linked list represents the different numbers hence the answer is false.
Sample Input 2:
2
1 2 4 0 -1
12 4 2 -1
6 0 2 -1 
2 4 1 -1
Sample Output 2:
False
False
Hint

Try recursively converting both the linked list elements to something whole such as string which you can compare.

Approaches (1)
Recursive Approach
  1. Maintain two empty strings at the start for each linked list.
  2. Now recursively go through each element of the first linked list and convert its elements into char representation.
  3. Simultaneously add those char to the string of linked list-1.
  4. Repeat the same process for the second linked list.
  5. We also need to eliminate appending zeros as ‘01’ and ‘1’ represent the same number.
  6. Hence we skip adding those elements for which element data is 0 and the size of the string is 0 because that would denote appended zeros.
  7. We get two strings, each of which denotes a combined number formed by elements of the linked list.
  8. Compare those two strings and return true if they match, else return false.
Time Complexity

O(max(N1, N2)), Where N1 denotes the length of linked list-1 and N2 denotes the length of linked list-2.

 

As we are iterating two linked lists of size N1 and N2, time complexity will be O(max(N1, N2)).

Space Complexity

O(max(N1, N2)) N1 denotes the length of linked list-1 and N2 denotes the length of linked list-2.

 

As we are using two strings of length N1 and N2. and due to recursion, we will require extra stack space of O(max(N1, N2)).

Code Solution
(100% EXP penalty)
Match Number
Full screen
Console