Modular Node

Easy
0/40
Average time to solve is 25m
profile
Contributed by
2 upvotes
Asked in companies
Goldman SachsAdobe

Problem statement

You are given a singly linked list containing ‘N’ nodes, where every node in the linked list contains a pointer “next” which points to the next node in the list and having integer values. You are also given an integer ‘K’.

You recently studied modular operation and you wanted to find out the last node in the linked list such that ‘x%K’ = 0 , where ‘x’ is the position of the node from the beginning.

Return the last node that satisfies the above property.

Example : 
N = 7 , K = 3
Linked List = 1 -> 3 -> 2 -> 4 -> 6 -> 5 -> 7

Explanation : 


The first node has ‘x%K’ = 1%3 = 1.
The second node has ‘x%K’ = 2%3 = 2.
The third node has ‘x%K’ = 3%3 = 0.
The fourth node has ‘x%K’ = 4%3 = 1.
The fifth node has ‘x%K’ = 5%3 = 2.
The sixth node has ‘x%K’ = 6%3 = 0.
The seventh node has ‘x%K’ = 7%3 = 1.
So, the last node which has ‘x%k’ = 0 is the sixth node with value 5.
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line contains an integer 'T' which denotes the number of test cases to be run. Then the test cases follow.

The first line of each test case contains two space-separated integers ‘N’ denoting the number of nodes in the linked list and ‘K’.

The next line of the test case contains ‘N + 1’ space-separated integers which are the nodes of the linked list and each line ends with -1 to indicate that the sublist is over. Thus, -1 will never be a linked list element.
Output format : 
For each test case, output an integer denoting the value of the last node with ‘x%K’ = 0. 

Print the output of each test case in a new line.
Note : 
You don’t need to print anything. It has already been taken care of. Just implement the given function.
Constraints : 
1 <= T <= 5
1 <= N <= 10^5
1 <= K <= N
Sum of N over all Test cases <= 10^5

Time Limit : 1 sec
Sample Input 1 :
2
3 3
1 2 3 -1
5 2
3 7 1 9 8 -1
Sample Output 1 :
3
9
Explanation Of Sample Input 1 :
For test case 1 we have, 

The linked list is 1 -> 2 -> 3.

The last node with ‘x%3’ = 0 is with ‘x=3’.

The third node has value 3.

So, we output 3.

For test case 2 we have,

The linked list is 3 -> 7 -> 1 -> 9 -> 8.

The last node with ‘x%2’ = 0 is with ‘x=4’.

The fourth node has value 9.

So, we output 9.
Sample Input 2 :
2
3 2
6 5 2 -1
2 1
9 7 -1
Sample Output 2 :
5
7
Hint

Simulate the problem statement.

 

Approaches (1)
Optimal Approach

 

Approach : 
 

  • We maintain a counter for each node from the beginning and check if the current node counter satisfies the property of ‘n%K=0’.
  • For every node satisfying the condition, we store the current node as our result.
  • This way, the last node that satisfies the condition will be stored as the final result.


 

Algorithm : 
 

  • Initialize a null node ‘ans’.
  • Initialize a variable ‘x’ as 0.
  • Run a while loop till the end of the linked list.
    • Increment ‘x’.
    • Check if ‘x%K’ = 0.
    • If yes, update ‘ans’ to the current node.
  • Return ‘ans’ as the final result.

 

Time Complexity

O(N) , where ‘N’ is the size of the linked list.
 

We are traversing the linked list once, so the overall time complexity is O(N).

 

Space Complexity

O(1)

 

Constant extra space is required. Hence, the overall Space Complexity is O(1).

 

Code Solution
(100% EXP penalty)
Modular Node
Full screen
Console