Problem

Submissions

Hints & solutions

Discuss

Count triplets in a sorted doubly linked list whose sum is equal to a given value x

Moderate

0/80

Average time to solve is 15m

Contributed by

35 upvotes

Asked in companies

Problem statement

You are given a sorted doubly linked list of distinct nodes that means no two nodes present in the list have the same data. You are also given an integer 'X'.Your task is to count the number of triplets in the list that sum up to a given value 'X'.

For example, DLL is 1<->2<->3<->4 NULL and the given integer 'X' is 9, then the number of triplets having the sum 9 is only one, and that is (2,3,4).

Note:

1. If no such triplets exist, return zero.
2. At least three elements will always be present in the linked list.

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

Input format :

The first line of input contains an integer ‘T’ denoting the number of test cases.

The next ‘2*T’ lines represent the ‘T’ test cases.

The first line of each test case contains space-separated integers denoting the nodes of the linked list. Each line is guaranteed to have -1 at the end to signify the end of the linked list.

The second line of each test case contains a single integer 'X' denoting the value of triplet sum.

Output format :

For each test case, print an integer denoting the count of the triplets.

The output of every test case will be printed in a separate line.

Note:

You don’t have to print anything, it has already been taken care of. Just implement the given function.

Constraints:

1 <= 'T' <= 10
3 <= 'N' <= 100
1 <= 'X' <= 10^8
1 <= 'V' <= 10^8

Where 'V' denotes any linked list element.

Time Limit: 1 sec

Sample Input 1 :

3
1 2 3 8 9 -1
13
1 2 3 4 5 6 7 8 9 -1
15
7 33 88 91 -1
40

Sample Output 1 :

2
8
0

Explanation of the Sample Input 1:

For the first test case:
The linked List is 1<-->2<-->3<-->8<-->9 NULL
We can clearly see that 2 triplets exist for this case, i.e., (2,3,8) and (1,3,9)

For the second test case:
The linked List is :1<-->2<-->3<-->4←>5<-->6<-->7<-->8<-->9 NULL
For this case we can see that there are total of eight triplets i.e. (2,4,9),(4,5,6),(2,6,7),(3,4,8),(1,5,9),(1,6,8),(2,5,8)and (3,5,7)

For the third test case:
The Linked List is 7<-->33<-->88<-->91 NULL
For this test case, we can see that there is no such triplet that gives us the 40, so the answer will be zero here.

Sample Input 2 :

1
3 7 9 23 45 -1
19
8 13 16 -1
37

Sample Output 2 :

1 
1

Explanation of the Sample Input 2:

In the first test case only the triplets (3, 7, 9) sum up to 19, Therefore the answer is 1.

In the second test case there is only 1 triplet (8, 13, 16) and that does sum to 37. Therefore the answer is 1.

Hint 1

Hint 2

Hint 3

Try and think of how you can check for each element, whether including it in triplet can make the sum X

Approaches (3)

Approach 1

Approach 2

Approach 3

Brute force

The idea is to traverse the linked list using three nested loops,

Such each possible combination is tried and checked whether it sums up to the value X and, if it does, increment the counter for the result.

Steps:

Initialize the COUNT to zero.
For the first loop, initialize the pointer PTR1 to the head of the given linked list, HEAD.
For the next nested loop, we initialize the pointer PTR2 to the next loop pointer, i.e., PTR1NEXT. Similarly, in the third loop, we initialize pointer PTR3 to next of the second loop pointer, i.e., PTR2.
And for each iteration in the last loop, check whether elements in the triplet sum up to X or not.
If the sum corresponds to X i.e. if((PTR1.DATA + PTR2.DATA+PTR3.DATA) equals X), increase the COUNT.
Else do nothing and move forward to the next iteration.

Time Complexity

O(N^3), Where ‘N’ denotes the number of elements in the Linked List

Since we are using three nested loops.

Space Complexity

O(1)

We are using constant space.

(100% EXP penalty)

Count triplets in a sorted doubly linked list whose sum is equal to a given value x

Console