BinaryDistance | Topcoder Archive

Problem Statement

There is a binary tree with N vertices, numbered 1 through N. For each x from 2 to N, there is an edge between vertex x and vertex x/2 (rounded down). For example, this is what the tree looks like for N = 6:

         1
     ___/ \___
    /         \
   2           3
  / \         /
 /   \       /
4     5     6

The distance between two vertices is defined as the number of edges on the unique simple path between them. Given some vertex V, your task is to find the maximum distance between V and some other vertex.

Definition

Class:: BinaryDistance
Method:: maxDist
Parameters:: int, int
Returns:: int
Method signature:: int maxDist(int N, int V)
(be sure your method is public)

Constraints

N will be between 2 and 10^9, inclusive.
V will be between 1 and N, inclusive.

Examples

```
6
```
```
2
```
```
Returns: 3
```
In the tree with N = 6 vertices, the farthest we can get from vertex 2 is vertex 6 and the distance is 3.
```
6
```
```
6
```
```
Returns: 4
```
In the tree with N = 6 vertices, the farthest we can get from vertex 6 is vertex 4 (or vertex 5) and the distance is 4.
```
5
```
```
4
```
```
Returns: 3
```
```
2
```
```
2
```
```
Returns: 1
```
```
1000000000
```
```
1
```
```
Returns: 29
```
```
20
```
```
7
```
```
Returns: 6
```
```
12
```
```
4
```
```
Returns: 5
```

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.