Triple Sum

Easy
0/40
Average time to solve is 15m
profile
Contributed by
7 upvotes
Asked in companies
HSBCRakuten IndiaJio Platforms Limited

Problem statement

It was Todd’s Birthday, So Bojack decided to give Todd a Binary tree with ‘N’ nodes. But the binary tree was too big to keep in his house, so Bojack decided to give exactly three nodes from that tree such that the sum of these three numbers equals ‘X’. Can you help Bojack determine if it is possible to make a sum equal to ‘X’?

For Example : 
X = 11


The sum of nodes 7, 3, 1 is 11. So we will return True.
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line contains a single integer ‘T’ denoting the number of test cases.

The first line of each test case contains the elements of the binary tree in the level order form separated by a single space.

The second line of the test case contains an integer denoting ‘X’.

If any node does not have a left or right child, take -1 in its place. Refer to the example below.


1
2 3
-1 4 -1 -1
5 -1
-1 -1

Explanation :
Level 1 :
The root node of the tree is 1

Level 2 :
Left child of 1 = 2
Right child of 1 = 3

Level 3 :
Left child of 2 = null (-1)
Right child of 2 = 4
Left child of 3 = null (-1)
Right child of 3 = null (-1)

Level 4 :
Left child of 4 = 5
Right child of 4 = null (-1)

Level 5 :
Left child of 5 = null (-1)
Right child of 5 = null (-1)

The first not-null node (of the previous level) is treated as the parent of the first two nodes of the current level. The second not-null node (of the previous level) is treated as the parent node for the next two nodes of the current level and so on.

The input ends when all nodes at the last level are null (-1).

Note: The above format was just to provide clarity on how the input is formed for a given tree. 

The sequence will be put together in a single line separated by a single space. Hence, for the above-depicted tree, the input will be given as:

1 2 3 -1 4 -1 -1 5 -1 -1 -1
Output Format : 
For each test case, print a boolean True or False.

Output for each test case will be printed in a separate line.
Note : 
You are not required to print anything; it has already been taken care of. Just implement the function and return the answer.
Constraints : 
1 <= T <= 100
1 <= N <= 3000
1 <= NodeVal <= 1000
1 <= X <= 1000

Time Limit: 1sec
Sample Input 1 :
2
3 1 2 -1 -1 -1 -1
6
1 2 3 4 -1 -1 -1 -1 -1
3
Sample Output 1 :
True
False
Explanation For Sample Output 1 :

For the First Test Case, The three nodes 1, 2, 3 have a sum equal to 6. Hence, the answer is true.


For the second Test Case, No combination of any three nodes results in a sum equal to 3. Hence, the answer is False.
Sample Input 2 :
2
1 8 1 3 4 -1 -1 -1 -1 -1 -1
8
1 1 1 -1 -1 -1 -1
2
Sample Output 2 :
True
False
Hint

Try to find the value of every node and check if the sum of any three nodes is equal to X.

Approaches (2)
Naive Approach

The Approach is simple. We will find the value of every node using dfs and then increase the count of every value. After completing dfs, We will loop through the list and, for a given value, check if there are two other elements present such that the sum of these three numbers is X.

 

The steps are as follows :

  1. Take a list arr to store the count of elements.
  2. In the ‘dfs’ function:
    1. Write the base condition, i.e., if the root is NULL return.
    2. If the data of the current node is less than X, then Increment its value in the list by 1.
    3. Call ‘dfs’ function for the left and right sides of the node.
  3. In the Main Function:
    1. Call the ‘dfs’ function to store the count of every element in the list.
    2. Now iterate through the list arr from 1 to X(say iterator be i) :
      1. If the count of arr[ i ] > 0, decrease the count by 1 to avoid retaking the current number.
      2. Iterate through the list arr from i to X(say iterator be j) :
        1. If the count of arr[ j ] > 0, then decrease the count by 1.
        2. Iterate through the list from j to X(say iterator be k) :
          1. If the count of arr[ k ] > 0 and sum of i + j + k is equal to X, then return true.
        3. Increment the value of arr[ j ] again by 1.
      3. Increment the value of arr[ i ] again by 1.
    3. Return false if we could not find any such triplets.
Time Complexity

O(X^3). Where X is the value given in the problem statement.

 

We are iterating through the list in nested loops from 1 to X, Hence the time complexity is O(X^3).

 

Space Complexity

O(X), Where X is the value given in the problem statement

 

We are using a list arr of size X to store the count of nodes, Hence the space complexity is O(X).

Code Solution
(100% EXP penalty)
Triple Sum
Full screen
Console