WackyNumberTree | Topcoder Archive

Problem Statement

Suppose you have an infinite binary tree B, whose nodes contain ordered pairs of positive integers. Let B be defined as follows:

	Root = (1,1) ,
	Left Child of Node (p,q) = (p,p+q) , and
	Right Child of Node (p,q) = (p+q,q) ,

where (x,y) denotes an ordered pair of positive integers. Given the pair (a,b), return the number of steps in a path from the Root to the node containing the given pair. For example, suppose a = 3 and b = 2. The first 3 levels of the tree look like

			(1,1)
                       /     \
                      /       \
                 (1,2)         (2,1)
                /     \       /     \
	       /       \     /       \         
           (1,3)     (3,2) (2,3)     (3,1)

To get from the Root to (3,2) you must go left then right, so you would return 2. If no path exists, return -1.

Definition

Class:: WackyNumberTree
Method:: numSteps
Parameters:: int, int
Returns:: int
Method signature:: int numSteps(int a, int b)
(be sure your method is public)

Constraints

a must be between 1 and 2000000000 inclusive.
b must be between 1 and 2000000000 inclusive.

Examples

```
3
```
```
2
```
```
Returns: 2
```
The example above.
```
4
```
```
7
```
```
Returns: 4
```
```
8
```
```
8
```
```
Returns: -1
```

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.