TopCoder Statistics - Problem Statement

Problem Statement

Look at the following pseudo-code, which computes the n-th Fibonacci number:

int fibonacci(int n)
	begin
	if n equals 0
		begin
		print(0)
		return 0
		end
	if n equals 1
		begin
		print(1)
		return 1
		end
	return fibonacci(n - 1) + fibonacci(n - 2)
	end

For example, if one calls fibonacci(3), then the following will happen:

fibonacci(3) calls fibonacci(2) and fibonacci(1) (the first call).
fibonacci(2) calls fibonacci(1) (the second call) and fibonacci(0).
The second call of fibonacci(1) prints 1 and returns 1.
fibonacci(0) prints 0 and returns 0.
fibonacci(2) gets the results of fibonacci(1) and fibonacci(0) and returns 1.
The first call of fibonacci(1) prints 1 and returns 1.
fibonacci(3) gets the results of fibonacci(2) and fibonacci(1) and returns 2.

In total, '1' will be printed twice and '0' will be printed once.

We want to know how many times '0' and '1' will be printed for a given n. You are to return a int[] which contains exactly two elements. The first and second elements of the return value must be equal to the number of times '0' and '1', respectively, will be printed during a fibonacci(n) call.

Definition

Class:: NumberofFiboCalls
Method:: fiboCallsMade
Parameters:: int
Returns:: int[]
Method signature:: int[] fiboCallsMade(int n)
(be sure your method is public)

Constraints

n will be between 0 and 40, inclusive.

Examples

0

Returns: {1, 0 }

If I call the Fibonacci function with n = 0, it just calls the 1st base case. Hence, the result is {1,0}.
1

Returns: {0, 1 }

If I call the Fibonacci function with n = 1, it just calls the 2nd base case. Hence the result is {0,1}.
2

Returns: {1, 1 }
3

Returns: {1, 2 }

The test case given in the problem statement.
4

Returns: {2, 3 }
5

Returns: {3, 5 }
6

Returns: {5, 8 }
7

Returns: {8, 13 }
8

Returns: {13, 21 }
9

Returns: {21, 34 }
10

Returns: {34, 55 }
11

Returns: {55, 89 }
12

Returns: {89, 144 }
13

Returns: {144, 233 }
14

Returns: {233, 377 }
15

Returns: {377, 610 }
16

Returns: {610, 987 }
17

Returns: {987, 1597 }
18

Returns: {1597, 2584 }
19

Returns: {2584, 4181 }
20

Returns: {4181, 6765 }
21

Returns: {6765, 10946 }
22

Returns: {10946, 17711 }
23

Returns: {17711, 28657 }
24

Returns: {28657, 46368 }
25

Returns: {46368, 75025 }
26

Returns: {75025, 121393 }
27

Returns: {121393, 196418 }
28

Returns: {196418, 317811 }
29

Returns: {317811, 514229 }
30

Returns: {514229, 832040 }
31

Returns: {832040, 1346269 }
32

Returns: {1346269, 2178309 }
33

Returns: {2178309, 3524578 }
34

Returns: {3524578, 5702887 }
35

Returns: {5702887, 9227465 }
36

Returns: {9227465, 14930352 }
37

Returns: {14930352, 24157817 }
38

Returns: {24157817, 39088169 }
39

Returns: {39088169, 63245986 }
40

Returns: {63245986, 102334155 }

Statistics

Problem Statement for "NumberofFiboCalls"

Problem Statement

Definition

Constraints

Examples