CEN303 2013-15 Questions |
Start: Dec.15.2013 at 02:00:00 PM
Finish: Dec.15.2013 at 07:00:00 PM
The contest is finished!
• Contest scoreboard
|
Feedback | | If you notice incorrect translations in Contester, please let author know.
|
|
Time limit 2000/4000/4000/4000 ms. Memory limit 65000/65000/65000/65000 Kb.
Question by Sidrit Reka.
Sum of the depths of all odd numbers in a BST
The depth of a node in a tree, is the number of steps to
reach to the node from the root. The depth of the root
node is assumed to be zero.
Question:
You will be given a series of numbers to be
inserted into an initially empty Binary Search
Tree (BST). Calculate the sum of the depths of
all odd numbers found in the BST.
Input specification
You will be first given a number (n) the number
of nodes to be inserted in the BST where 1 <= n
<= 10000. Then you will be given n space separated
numbers (nums[n]) where each of the number in
the series is 1 <= nums[i] <= 10000.
Output specification
Calculate and show the sum of the depths of all
odd numbers found in the BST.
Sample Input I
7
4 7 3 2 7 6 3
|
Sample Output I
2
|
- The depth of 4 is 0,
- The depth of 3 is 1,
- The depth of 7 is 1,
- The depth of 2 is 2,
- The depth of 6 is 2.
We have 2 odd numbers in our BST (3, 7). We add their depths (1 + 1 = 2).
Sample Input II
12
6 8 2 4 1 2 7 9 4 3 6 5
|
Sample Output II
12
|
- The depth of 6 is 0,
- The depth of 2 is 1,
- The depth of 8 is 1,
- The depth of 1 is 2,
- The depth of 4 is 2,
- The depth of 7 is 2,
- The depth of 9 is 2,
- The depth of 3 is 3,
- The depth of 5 is 3.
We have 5 odd numbers in our BST (1, 3, 5, 7, 9). We add their depths (2 + 3 + 3 + 2 + 2 = 12).
Для отправки решений необходимо выполнить вход.
|