Count Triplets in sorted DLL

Moderate

0/80

1 upvote

Asked in company

Problem statement

You are given a sorted doubly linked list and an integer value x. Your task is to count the number of triplets in the doubly linked list whose sum is equal to x.

Detailed explanation ( Input/output format, Notes, Images )

Input format :

The first line of input contains a single integer T, representing the number of test cases or queries to be run. 

Then the T test cases follow.

The first line of every test case contains the elements of the doubly linked list  separated by a single space and terminated by -1. Hence, -1 would never be a list element.

The second line of every test case contains the value of x.

Output Format :

For each test case, print the count of triplets.

The output of each test case is printed in a separate line.

Note:

You do not need to print anything, it has already been taken care of. Just implement the given function.

Constraints :

1 <= T <= 10
3 <= N <= 100
-10^8 <= data <= 10^8 and data != -1
-3*10^8 <= x <= 3*10^8
Where T is the number of test cases, N is the length of the doubly linked list and x is the given value of the sum.

Sample Input 1:

2
1 2 4 5 6 8 9 -1
17
1 2 3 -1
5

Sample Output 1:

2
0

Explanation for Sample Input 1:

For first test case : 
The triplets are : (2, 6, 9) , (4, 5, 8).

Sample Input 2:

2
-2 0 0 2 -1
0
1 1 1 1 -1
3

Sample Output 2:

2
4

Hint 1

Hint 2

Go through all possible triplets.

Approaches (2)

Approach 1

Approach 2

Naive approach

The simplest way is to go through all the possible triplets and incrementing count by 1 whenever any desired triplet is found.

Algorithm:

Take three nested loops to iterate the whole list.
For every possible triplet check whether it sums up to the given value x, if yes increment the count by 1 and iterate further.
Return the value of count.

Time Complexity

O(N^3), Where N is the number of nodes in the linked list.

All the possible triplets are accessed, resulting in a time complexity of O(N^3).

Space Complexity

O(1)

Constant extra space is required.

(100% EXP penalty)

Count Triplets in sorted DLL

Console