Path Sum IV

Moderate
0/80
Average time to solve is 20m
5 upvotes
Asked in company
alibaba

Problem statement

You are given an array 'A' of length 'N' consisting of three-digit integers in ascending order. You can construct a binary tree from these integers. All integers are of form DPV (3 digits), where 'D' tells depth in the tree, 'P' tells position in the tree, and 'V' tells value in this position.

binary-tree

For Example:

215 means value 5 is in position 1 at depth 2.

Your task in the problem is to find the sum of all paths from node to leaf.

Note:

The maximum depth allowed is 4, i.e. the maximum number of positions can be 8 ( or 2 ^ (4 - 1)).
Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line of the input contains ‘T’ denoting the number of test cases.

The first line of each test case contains an integer ‘N’, representing the length of the array.

The second line of each test case contains N space-separated integers of the array A.
Output Format: 
For each test case print a single line containing a single integer denoting the sum of all paths from the root node.

The output of each test case is printed on a new line.
Constraints: 
1 <= T <= 10
1 <= N <= 150
100 <= A[i] <= 999 
1 <= D <= 4
1 <= P <= 8
0 <= V <= 9

Where ‘T’ denotes the number of test cases and 'N' denotes the length of array 'A'.

Time limit: 1 sec.
Sample Input 1:
2
3
113 215 221
2
113 221
Sample Output 1:
12
4
Explanation for Sample Input 1:
For test case 1:

binary-tree

The path sum is (3 + 5) + (3 + 1) = 12.

For test case 2:

binary-tree

The path sum is (3 + 1) = 4.
Sample Input 2:
2
3
115 217 322 
4
117 212 313 421
Sample Output 2:
14
13
Hint

Can we use DFS approach?

Approaches (1)
DFS approach

Explanation:

  • Here we solve the problem assuming we have been given a normal tree. We traverse it by keeping a root to leaf running(or prefix) sum. If we see a leaf node, we add the running sum to the final result.
  • Now each tree node is represented by a number. 1st digit is the level, 2nd is the position in that level, 3rd digit is the value. We need to find a way to traverse this tree and get the sum.
  • To move left of the current node we increase the depth by 1. And make position p to 2*p-1.
  • To move right of the current node we increase the depth by 1. And make position p to 2*p.

 

Algorithm:

  • From the first two digits of the integer given, we can determine the position of the value (the last digit) in the binary tree.
  • Initially, we can hash/map the position with value, and traverse through the binary tree as if it were a complete binary tree. We also maintain the prefix sum from the root node to leaf while traversing.
  • From each position, we check if we can move to left and right of the node. If we can’t move in either direction it means the current node is the leaf node. And we return the prefix sum till now.
  • If we can move in either direction we move thereafter adding the current node value in the prefix sum till now.
Time Complexity

O(N),  where ‘N’ is the length of the array.

 

As we will only be traversing the array and the tree, which contains ‘N’ nodes. The time complexity will be O(N).

Space Complexity

O(N),  where ‘N’ is the length of the array.

 

The only space required will be to make a map/hash, which is O(N) in space.

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