Statistics

Problem Statement for "BinaryDistance"

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

  1. 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.

  2. 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.

  3. 5

    4

    Returns: 3

  4. 2

    2

    Returns: 1

  5. 1000000000

    1

    Returns: 29

  6. 20

    7

    Returns: 6

  7. 12

    4

    Returns: 5

  8. 2

    1

    Returns: 1

  9. 2

    2

    Returns: 1

  10. 3

    1

    Returns: 1

  11. 3

    2

    Returns: 2

  12. 3

    3

    Returns: 2

  13. 4

    1

    Returns: 2

  14. 4

    2

    Returns: 2

  15. 4

    3

    Returns: 3

  16. 4

    4

    Returns: 3

  17. 5

    1

    Returns: 2

  18. 5

    2

    Returns: 2

  19. 5

    3

    Returns: 3

  20. 5

    4

    Returns: 3

  21. 5

    5

    Returns: 3

  22. 6

    1

    Returns: 2

  23. 6

    3

    Returns: 3

  24. 6

    4

    Returns: 4

  25. 6

    5

    Returns: 4

  26. 6

    6

    Returns: 4

  27. 7

    1

    Returns: 2

  28. 7

    2

    Returns: 3

  29. 7

    3

    Returns: 3

  30. 7

    4

    Returns: 4

  31. 7

    5

    Returns: 4

  32. 7

    6

    Returns: 4

  33. 7

    7

    Returns: 4

  34. 8

    1

    Returns: 3

  35. 8

    2

    Returns: 3

  36. 8

    3

    Returns: 4

  37. 8

    4

    Returns: 4

  38. 8

    5

    Returns: 4

  39. 8

    6

    Returns: 5

  40. 8

    7

    Returns: 5

  41. 8

    8

    Returns: 5

  42. 28

    19

    Returns: 8

  43. 50

    45

    Returns: 10

  44. 42

    21

    Returns: 8

  45. 39

    39

    Returns: 9

  46. 33

    16

    Returns: 8

  47. 39

    19

    Returns: 8

  48. 30

    24

    Returns: 8

  49. 29

    29

    Returns: 8

  50. 14

    8

    Returns: 6

  51. 24

    9

    Returns: 7

  52. 185

    179

    Returns: 13

  53. 974

    391

    Returns: 17

  54. 839

    783

    Returns: 18

  55. 948

    852

    Returns: 18

  56. 180

    16

    Returns: 10

  57. 647043724

    274782219

    Returns: 56

  58. 871069689

    527261577

    Returns: 57

  59. 403272055

    222559640

    Returns: 55

  60. 908823243

    329278497

    Returns: 57

  61. 944675799

    132908325

    Returns: 55

  62. 861768453

    380092536

    Returns: 57

  63. 912883806

    394569988

    Returns: 57

  64. 461605628

    304044119

    Returns: 56

  65. 486120389

    395099087

    Returns: 56

  66. 321641978

    265309197

    Returns: 55

  67. 536870911

    1

    Returns: 28

  68. 536870911

    2

    Returns: 29

  69. 536870911

    3

    Returns: 29

  70. 536870911

    4

    Returns: 30

  71. 536870911

    5

    Returns: 30

  72. 536870911

    6

    Returns: 30

  73. 536870911

    536870910

    Returns: 56

  74. 536870911

    536870911

    Returns: 56

  75. 536870911

    135691656

    Returns: 55

  76. 536870911

    247806061

    Returns: 55

  77. 536870911

    349502163

    Returns: 56

  78. 536870912

    1

    Returns: 29

  79. 536870912

    2

    Returns: 29

  80. 536870912

    3

    Returns: 30

  81. 536870912

    4

    Returns: 30

  82. 536870912

    5

    Returns: 30

  83. 536870912

    6

    Returns: 31

  84. 536870912

    536870911

    Returns: 57

  85. 536870912

    536870912

    Returns: 57

  86. 536870912

    42244722

    Returns: 53

  87. 536870912

    41647635

    Returns: 53

  88. 536870912

    264919016

    Returns: 56

  89. 805306367

    1

    Returns: 29

  90. 805306367

    2

    Returns: 29

  91. 805306367

    3

    Returns: 30

  92. 805306367

    4

    Returns: 30

  93. 805306367

    5

    Returns: 30

  94. 805306367

    6

    Returns: 31

  95. 805306367

    805306366

    Returns: 57

  96. 805306367

    805306367

    Returns: 57

  97. 805306367

    747767800

    Returns: 57

  98. 805306367

    253931627

    Returns: 56

  99. 805306367

    610781806

    Returns: 57

  100. 805306368

    1

    Returns: 29

  101. 805306368

    2

    Returns: 30

  102. 805306368

    3

    Returns: 30

  103. 805306368

    4

    Returns: 31

  104. 805306368

    5

    Returns: 31

  105. 805306368

    6

    Returns: 31

  106. 805306368

    805306367

    Returns: 58

  107. 805306368

    805306368

    Returns: 58

  108. 805306368

    679509804

    Returns: 58

  109. 805306368

    395132901

    Returns: 57

  110. 805306368

    491585735

    Returns: 57

  111. 1000000000

    1

    Returns: 29

  112. 1000000000

    2

    Returns: 30

  113. 1000000000

    3

    Returns: 30

  114. 1000000000

    4

    Returns: 31

  115. 1000000000

    5

    Returns: 31

  116. 1000000000

    6

    Returns: 31

  117. 1000000000

    999999999

    Returns: 58

  118. 1000000000

    1000000000

    Returns: 58

  119. 1000000000

    208032501

    Returns: 56

  120. 1000000000

    346948152

    Returns: 57

  121. 1000000000

    973708325

    Returns: 58

  122. 16777215

    3

    Returns: 24

  123. 16777216

    3

    Returns: 25

  124. 25165823

    2

    Returns: 24

  125. 25165824

    2

    Returns: 25

  126. 33554431

    3

    Returns: 25

  127. 33554432

    3

    Returns: 26

  128. 50331647

    2

    Returns: 25

  129. 50331648

    2

    Returns: 26

  130. 67108863

    3

    Returns: 26

  131. 67108864

    3

    Returns: 27

  132. 100663295

    2

    Returns: 26

  133. 100663296

    2

    Returns: 27

  134. 134217727

    3

    Returns: 27

  135. 134217728

    3

    Returns: 28

  136. 201326591

    2

    Returns: 27

  137. 201326592

    2

    Returns: 28

  138. 268435455

    3

    Returns: 28

  139. 268435456

    3

    Returns: 29

  140. 402653183

    2

    Returns: 28

  141. 402653184

    2

    Returns: 29

  142. 1000000000

    4194304

    Returns: 51

  143. 20

    20

    Returns: 7

  144. 20

    16

    Returns: 7

  145. 11

    2

    Returns: 3

  146. 1000000000

    1000000

    Returns: 48

  147. 89999999

    1234

    Returns: 35

  148. 100

    28

    Returns: 10

  149. 10

    10

    Returns: 5

  150. 32

    5

    Returns: 6

  151. 9

    6

    Returns: 5

  152. 35

    1

    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.
This problem was used for: