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 : )

[irmidjusz]

Możesz powiedzieć, co to za firma?

[solr]

Zakładając, że prawdą jest:

"Dla n = 21 problem rozwiazany w iteracji = 5, gdy: L = -11 R = 21"

to prawdą jest też:

"Dla n = 1234 problem rozwiazany w iteracji = 11, gdy: L = -814 R = 1234"
"Dla n = -13742 problem rozwiazany w iteracji = 14, gdy: L = -13742 R = 2642"

Ale rozwiązać to w 30 minut, hmm, chyba stary się robię ;-)

Ok, porada (mnie pomogło): zrób sobie drzewo pokazujące, jakie wartości mają R i L dla powiedzmy, do 3 iteracji.

[Crozin]

Dosłownie <10 sekund szukania: http://stackoverflow.com/questions/9600218...fold-operations