# Google Foo.bar: Breeding Like Rabbits

This is a quite fun question in Google’s secret foo.bar challange.

Omitting all the rabbit or professor related stuff, the core problem is that we have a sequence of numbers defined by the set of recursive equations, then for a given number S, the goal is to find an index n such that R(n)=S.

You might get the illusion that we can probably derive some sort of analytical formula to solve it in constant time. It’s exact what I did in the beginning, unfortunately it’s quite difficult to do (if possible).

So go back to searching. Heck, if we just do a linear search and find the last element such that R(n)<=S, problem is easily solved. This certainly won’t work because S can go as large as 10^25.

Binary search doesn’t work either because the sequence is not monotonously increasing. However, here comes the key observation: the odd and even sub-sequences are monotonously increasing, respectively, which means that we can do binary search on each of them separately.

Now that we reduced the outer loop (searching) to O(logn), we turn to the inner loop. In each iteration of the binary search, we have to call the recursive formulas many times in order to evaluate R(n), and the upper bound of the number of recursive calls is not O(logn). Since each R(2n) or R(2n+1) depends on two previous terms, the recursion might lead to as many as O(n) calls.

As we state above, O(n) is not acceptable because S can be extremely large.

My solution to this is hashing. For each n for which R(n) is calculated, we stash the result in a hash map (“dict” in the attached code). Note that this only reduces the time complexity of the evaluation of R(n) to approximately O(logn), but it works fairly well in practice.

The final time complexity is approximately O(logn*logn).

## Shuyang Sheng

PhD student at USC working on computer vision.