Count Triplets

Easy
0/40
Average time to solve is 15m
profile
Contributed by
25 upvotes
Asked in companies
PayPalDunzoOLX Group

Problem statement

You have been given an integer ‘X’ and a non-decreasing sorted doubly linked list with distinct nodes.

Your task is to return the number of triplets in the list that sum up to the value ‘X’.

Detailed explanation ( Input/output format, Notes, Images )
Input format : 
The first line contains a single integer ‘T’ denoting the number of test cases. The test cases follow.

The first line of each test case contains a single integer ‘X’.

The second line of the input 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.
Output Format: 
For each test case, print in a new line a single integer denoting the number of triplets that have the sum equal to ‘X’.
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 ^ 3
- 3 * 10 ^ 5 <= X <= 3 * 10 ^ 5
- 10 ^ 5 <= data <= 10 ^ 5 and data != - 1

Where ‘N’ is the number of nodes in the given linked list, and ‘X’ is the required triplet sum value.

Time limit: 1 sec
Sample Input 1:
2
13
-4 2 3 8 9 -1
5
-4 -2 3 4 5 -1
Sample Output 1:
2
2
Explanation to Sample Input 1:
In the first test case, there are two possible triplets {2,3,8} and {-4,8,9}, whose sum is 13.
In the second test case there are two triplets possible {-4,4,5} and {-2,3,4} whose sum is 5.
Sample Input 2:
2
-4
-3 8 10 -1
12
1 4 6 2 -1
Sample Output 2:
0
1
Explanation to Sample Input 2:
In the first test case, there is no triplet whose sum is -4.
In the second test case, there is only one triplet {6,4,2}, whose sum is 12.
Hint

Try to explore all the possible triplets.

Approaches (3)
Brute Force

The idea is to explore all the triplets and count those triplets which have a sum equal to ‘X’. We will use a variable 'COUNT' which will be initialized to 0, to count the number of triplets with sum ‘X’. The steps are as follows:

  • We will iterate the linked list and pick each node one by one and pivot that node as the first element of the triplet, let this node be 'FIRSTPTR'.
  • For the second element of the triplet, iterate from the next node of 'FIRSTPTR' till the end of the linked list and one by one pick each node and pivot that, let’s say this node is 'SECONDPTR'. So we will pivot 'SECONDPTR' as the second element of the triplet.
  • For the third element, iterate from the next node of 'SECONDPTR' till the end of the list and pivot each node as the third element.
  • If the sum of the three pivoted nodes is equal to ‘X’ increment 'COUNT' by 1.
Time Complexity

O(N ^ 3), where ‘N’ is the number of nodes in the doubly linked list.

 

For each pivoted node, we are pivoting each node in front of the pivoted node and then exploring all nodes in front of the second pivoted node. So, the overall Time complexity will be O(N ^ 3).

Space Complexity

O(1).

 

We are not using any additional space. So, space complexity will be O(1).

Code Solution
(100% EXP penalty)
Count Triplets
Full screen
Console