FastPrep

Description

Solutions

Reach a Given Number

📚RELATED PROBLEMS

You are given three integers: A, B, and N. Your task is to determine whether it is possible to reach the value N starting from either A or B using one of the following operations:

Replace A with A + B.
Replace B with A + B.

If it is possible to reach N, print the minimum number of operations required. If it is not possible print NOT POSSIBLE.

Example 1:

Input:  A = 1, B = 2, N = 5
Output: 2 
Explanation:
      
      (1, 2) -> (2, 3) -> (3, 5)

Example 2:

Input:  A = -1, B = 0, N = 5
Output: "NOT POSSIBLE" 
Explanation:
      
      (-1, 0) -> (-1, 0)
      
      
      States are either remain unchanged or produce negative value for both A and B.

Constraints:

-10000000000 <= A, B, N <= 10000000000