C Programming Language

Problem Title: Sum of The Leaves

Main Material: Function and Recursion

Poki gets the assignment from her teacher to count the number of leaves from a tree in the following way:

Figures describe the number of leaves. Poki's job is to count from top to bottom in the direction of the left or right branches.

In the picture above, the number of leaves from top to bottom branch is 7, 8, 10, 11.

• 7 is obtained from 1 + 2 + 4
• 8 is obtained from 1 + 2 + 5
• 10 is obtained from 1 + 3 + 6
• 11 obtained from 1 + 3 + 7

Poki asks for your help to create a program that can help count the number of leaves.

Format Input

Input consists of one integer T, number of test case given by Poki. For each test case, there are N, on the next line, followed by a row of A_i numbers as many as N .

Format Output

Output should be expressed in format Case #X: - X is the number of the test case, then the next row represents the lowest number of D leaves per branch. The Lower Branch is a branch that has absolutely no other branches below it.

Constraints

1 T 100 1 N 100 1 Ai 100

Sample Input & Output (standard input & output)

3

7

1 2 3 4 5 6 7

Case #1:

7

8

10

11

5

1 2 3 4 5

Case #2:

7

8

4

2

3 3

Case #3:

6

Explanation For Case #2:

The order of input to form a tree is from left to right then down with a maximum number of branches of two.

• 7 is obtained from 1 + 2 + 4
• 8 is obtained from 1 + 2 + 5
• 10 is obtained from 1 + 3 + 6

In the illustration above, the Arrays that can be used can be described as follows:

To get the Left branch, we can use formula (2 * index). To get the Right branch, you can use the formula (2 * index) + 1.

For example:

• Left and Right branches of A [1] are A [2] and A [3].
• Left and Right branches of A [2] are A [4] and A [5].
• Left and Right branches of A [3] do not exist. However, if there is, it will be placed into A [6] and A [7].

Perform recursive techniques to count the number of leaves in the tree.

A[1] A[2] A[3]||A|A|A[5] 12 13 14 15