Ciekawy problem (test) z Codility, Problem dla ambitnych do rozwiązania : ) Opcje

[Fantazyn]

Ostatnio podczas zmiany pracy natrafiłem na rekrutację, gdzie firma pierwszym etapem rekrutacji uczyniła test na Codility.

Problem z jakim miałem się zmierzyć:

Two integer variables L and R are given. Their initial content is 0 and 1, respectively, and it can be manipulated using the following unfold operations:
operation 'L' is the assignment of value 2*L-R to variable L;
operation 'R' is the assignment of value 2*R-L to variable R.

An integer N is given. An unfold sequence for N is a sequence of unfold operations such that, after performing these operations, either L = N or R = N.

For example, consider N = 21 and the following sequence of unfold operations: ['L', 'L', 'R', 'L', 'R']. This is an unfold sequence for N, because:
after the first operation L becomes -1 (R remains 1);
after the second operation L becomes -3 (R remains 1);
after the third operation R becomes 5 (L remains -3);
after the fourth operation L becomes -11 (R remains 5);
after the fifth operation R becomes 21 (L remains -11).

After the last operation, R = N. The sequence consists of five operations, and no shorter unfold sequence for N exists.

Write a function

class Solution { public int interval_unfold_count(int N); }

that, given an integer N, returns the length of the shortest unfold sequence for N. The function should return -1 if no unfold sequence for N exists.

For example, given N = 21, the function should return 5, as explained above.

Assume that:
N is an integer within the range [-2,147,483,648..2,147,483,647].

Complexity:
expected worst-case time complexity is O(log(N));
expected worst-case space complexity is O(1).

Rozwiązanie może być w dowolnym języku, standardowo czas na problemy z Codility trwają 30 minut : ).
Problem próbowałem rozwiązać za pomocą rekurencji, ale problem pojawił się jak ropatrywać dwie ścieżki jednocześnie...

Jak ktoś zna rozwiązanie, to prosiłbym o wskazówki : )