Halve or Split
A sequence t is defined for every non-negative index by these rules: t(0) = 0, t(1) = 1, for an even index t(2k) = t(k), and for an odd index t(2k + 1) = t(k) + t(k + 1). Return t(n).
The rules are recursive and following them directly is the point; a loop with a table works as well but takes more thought.
For example, t(5) = t(2) + t(3), where t(2) = t(1) = 1 and t(3) = t(1) + t(2) = 2, so t(5) = 3.
Example 1
n 5
returns 3
5 is odd with k = 2, so t(5) = t(2) + t(3) = 1 + 2 = 3.
Example 2
n 0
returns 0
t(0) is given directly as 0.
Constraints
0 <= n <= 1000
Write it in your browser, against the clock. The model solution, stepped through line by line, comes after.