Statistics

Problem Statement for "CalkinWilf"

Problem Statement

The Calkin-Wilf tree is a rooted tree that contains each positive rational number exactly once. The definition of the tree is really simple:

  • The root of the tree contains the value 1/1.
  • Each node in the tree has one left child and one right child.
  • If a node contains the fraction a/b, its left child contains the fraction a/(a+b) and its right child contains the fraction (a+b)/b.

Here is an ASCII art drawing of the first few levels of the tree: 

                ____________1/1____________
               /                           \
        ____1/2____                     ____2/1____
       /           \                   /           \
    1/3             3/2             2/3             3/1
   /   \           /   \           /   \           /   \
1/4     4/3     3/5     5/2     2/5     5/3     3/4     4/1

You are given the String path that describes a path down the tree. We start in the root and we read the characters of path one at a time. Here, 'L' means "go to the left child" and 'R' means "go to the right child".

Find the fraction a/b that will be written in the last node we visit. Return the int[] {a, b}.

Definition

Class:
CalkinWilf
Method:
findRational
Parameters:
String
Returns:
int[]
Method signature:
int[] findRational(String path)
(be sure your method is public)

Notes

  • The return value should be a int[] with two elements. Element 0 should be the numerator and element 1 should be the denominator of the fraction.

Constraints

  • path will contain between 0 and 30 characters, inclusive.
  • Each character in path will be either 'L' or 'R'.

Examples

  1. ""

    Returns: {1, 1 }

    If the path is empty, we end where we started: in the root.

  2. "R"

    Returns: {2, 1 }

    Taking a single step right takes us to the node with the value 2/1.

  3. "LRR"

    Returns: {5, 2 }

    This time we go 1/1 -> left to 1/2 -> right to 3/2 -> right to 5/2.

  4. "LRLRLRLRLRLRLRLRLRLRLRLRLRLRLR"

    Returns: {2178309, 1346269 }

    This is one possible longest valid input.

  5. "RLLRRRLLRRLRRR"

    Returns: {497, 134 }

  6. "LLLLLLLLLLRLLLLLLLLLLLLLLLLLLL"

    Returns: {12, 239 }

  7. "LLRRLLLRRLLRR"

    Returns: {323, 134 }

  8. "LLRRLRLLLRRLRLLLLLRRR"

    Returns: {6024, 1895 }

  9. "RRRRRRRRRRRRRRRRRRRRRRRRRRRRRR"

    Returns: {31, 1 }

  10. "LLLLLLLLLLLLLLLLLLLLLLRLLLLLLL"

    Returns: {24, 191 }

  11. "LLLLLLLLLLLLLLLLLLLLLLLLRLLLLL"

    Returns: {26, 155 }

  12. "LRRLRRLRRLRRRLLRRRLLLRRRLRLLR"

    Returns: {252175, 181453 }

  13. "LLLLLRLLLLLLLLLLLLLLLLLLLLLLLL"

    Returns: {7, 174 }

  14. "RRRRRRRRRRRRRRRRRLRRRRRRRRRRRR"

    Returns: {246, 19 }

  15. "LRLLRRR"

    Returns: {27, 8 }

  16. "LRRRLLRRLLLLRRLRLL"

    Returns: {938, 2431 }

  17. "LRLLLLLLLLLLLLLLLLLLLLLLLLLLLL"

    Returns: {3, 86 }

  18. "RRRRLLRRLRLRRRLRLR"

    Returns: {2179, 1328 }

  19. "LLLLLLLLLLLLLLLLLLLLLLLLLRLLLL"

    Returns: {27, 134 }

  20. "RRLRRRRRRRRRRRRRRRRRRRRRRRRRRR"

    Returns: {111, 4 }

  21. "RRRRRRRRRRRRRRRRRRRRRRRRRRRRRL"

    Returns: {30, 31 }

  22. "LLLLLLLLLLLLLLLLLLLLLLLLLLRLLL"

    Returns: {28, 111 }

  23. "RRRRRLRRRRRRRRRRRRRRRRRRRRRRRR"

    Returns: {174, 7 }

  24. "RRRRRRRRRRRRRRRLRRRRRRRRRRRRRR"

    Returns: {254, 17 }

  25. "RRLRRL"

    Returns: {11, 15 }

  26. "LLLLLLLLLLLLLLLLLRLLLLLLLLLLLL"

    Returns: {19, 246 }

  27. "RRRRRRRLRLRRLLLRRLLRRLLRR"

    Returns: {18311, 7585 }

  28. "LRLRLRRLLLLL"

    Returns: {34, 183 }

  29. "RLRRRRLLLLRLRRLRLLLLRLLL"

    Returns: {4499, 17190 }

  30. "LRRRRRRLRLLLR"

    Returns: {127, 99 }

  31. "LLLLRLLLLLLLLLLLLLLLLLLLLLLLLL"

    Returns: {6, 155 }

  32. "LLLLLLLLLLLLLLLRLLLLLLLLLLLLLL"

    Returns: {17, 254 }

  33. "LLLLLLLLRLLLLLLLLLLLLLLLLLLLLL"

    Returns: {10, 219 }

  34. "RLLRLLLLRL"

    Returns: {40, 73 }

  35. "RLRRRLRRLRLLLLLLLRRRRLLRR"

    Returns: {15794, 6457 }

  36. "LLLLLLLLLLLLLRLLLLLLLLLLLLLLLL"

    Returns: {15, 254 }

  37. "RRLLRLLRLLRRLLRRLLR"

    Returns: {4770, 3373 }

  38. "LLLLLLLLLLLLLLLLLLRLLLLLLLLLLL"

    Returns: {20, 239 }

  39. "LLLLLLLLLLLLLLLLLLLLLLLLLLLLLL"

    Returns: {1, 31 }

  40. "LLRLR"

    Returns: {11, 7 }

  41. "LRRRLRRRRRLRLRRLLRLRR"

    Returns: {6863, 2653 }

  42. "RRRRRRRRRRRRRRLRRRRRRRRRRRRRRR"

    Returns: {255, 16 }

  43. "RLRLLRLRRLRLL"

    Returns: {191, 493 }

  44. "LRRLLLRRLLLRRLLRRLLLRRLRRR"

    Returns: {74939, 20274 }

  45. "RRRRRRRRRRRRRRRRRRRLRRRRRRRRRR"

    Returns: {230, 21 }

  46. "RRRLRRRLLLRRLLRLLL"

    Returns: {491, 1821 }

  47. "RRRRRRRRRRRRRRRRRRRRLRRRRRRRRR"

    Returns: {219, 22 }

  48. "LLLLLLLLLLLLLLRLLLLLLLLLLLLLLL"

    Returns: {16, 255 }

  49. "RLLLRLRLLRLRLRRR"

    Returns: {1463, 405 }

  50. "RRLLRLRLRLLRRLRLRRRLLLL"

    Returns: {6175, 26401 }

  51. "LLLLLLLLLLLLLLLLLLLLLLLLLLLLRL"

    Returns: {30, 59 }

  52. "RRRRRRRRRRRRRRRRRRRRRRRRRLRRRR"

    Returns: {134, 27 }

  53. "RRRRLRRRRRRRRRRRRRRRRRRRRRRRRR"

    Returns: {155, 6 }

  54. "RRRRRRRRRRRRRRRRRRRRRLRRRRRRRR"

    Returns: {206, 23 }

  55. "LLLLLLLRLLLLLLLLLLLLLLLLLLLLLL"

    Returns: {9, 206 }

  56. "LLLLLLLLLLLLLLLLLLLLLRLLLLLLLL"

    Returns: {23, 206 }

  57. "LRRLL"

    Returns: {5, 12 }

  58. "RLLLLLLLLLLLLLLLLLLLLLLLLLLLLL"

    Returns: {2, 59 }

  59. "RRRRRRRRRRRLRRRRRRRRRRRRRRRRRR"

    Returns: {246, 13 }

  60. "LRRLRLRLRLLLLLLLL"

    Returns: {81, 698 }

  61. "LRRRRLRLRRR"

    Returns: {113, 31 }

  62. "LLRLLLLLLLLLLLLLLLLLLLLLLLLLLL"

    Returns: {4, 111 }

  63. "RRRLRRRRRRRRRRRRRRRRRRRRRRRRRR"

    Returns: {134, 5 }

  64. "LLRLRLLRRLRLRLLLLRRRLRLLRLRRL"

    Returns: {234615, 325498 }

  65. "RLRRLLRRLLRRRLLLLRLRRRLLRLR"

    Returns: {114139, 71791 }

  66. "RRRRRRRRRRRRRRRRLRRRRRRRRRRRRR"

    Returns: {251, 18 }

  67. "LRLRRLLRR"

    Returns: {75, 31 }

  68. "RRRRRRRRRRRRRLRRRRRRRRRRRRRRRR"

    Returns: {254, 15 }

  69. "LLLLLLLLLLLLLLLLLLLLLLLLLLLRLL"

    Returns: {29, 86 }

  70. "LLLLLLLLLLLLLLLLLLLLLLLLLLLLLR"

    Returns: {31, 30 }

  71. "RRRRRRRRRRRRRRRRRRRRRRRLRRRRRR"

    Returns: {174, 25 }

  72. "RLRRRRRRRRRRRRRRRRRRRRRRRRRRRR"

    Returns: {86, 3 }

  73. "RRRLRRRLRRLLRRLRRLRLRLLLRRLLRL"

    Returns: {253091, 432592 }

  74. "LLLLRRLRRLRLRLLLLRLRRRRRR"

    Returns: {17610, 2689 }

  75. "RRLLLRRLRLRRL"

    Returns: {234, 323 }

  76. "LRRRRRRRRRRRRRRRRRRRRRRRRRRRRR"

    Returns: {59, 2 }

  77. "RRRRRRRRRRRRLRRRRRRRRRRRRRRRRR"

    Returns: {251, 14 }

  78. "LLLLLLLLLLLLLLLLRLLLLLLLLLLLLL"

    Returns: {18, 251 }

  79. "LLLLLLLLLLLLRLLLLLLLLLLLLLLLLL"

    Returns: {14, 251 }

  80. "RRRRRRRRLRRRRRRRRRRRRRRRRRRRRR"

    Returns: {219, 10 }

  81. "RRLLRRLRRRRLRLLLLLLRRLRRLRR"

    Returns: {51860, 19007 }

  82. "RRRRLLRLLRRRRRLRLLRRRRLRRLRRL"

    Returns: {72323, 98739 }

  83. "RLLLLRRLLRLRLLLRLRRRRLR"

    Returns: {15637, 8591 }

  84. "LLLLLLLLLL"

    Returns: {1, 11 }

  85. "LRLRRLRRLRRRLLLRLLLLL"

    Returns: {1067, 6152 }

  86. "RRRRRRRRRRRRRRRRRRLRRRRRRRRRRR"

    Returns: {239, 20 }

  87. "LLLLLLLLLLLLLLLLLLLLLLLRLLLLLL"

    Returns: {25, 174 }

  88. "LLLLLLLLLLLRLLLLLLLLLLLLLLLLLL"

    Returns: {13, 246 }

  89. "LLLLLLLLLRLLLLLLLLLLLLLLLLLLLL"

    Returns: {11, 230 }

  90. "RRRLLLLLLRRRRRRRLLRRR"

    Returns: {1328, 383 }

  91. "LLLLLLLLLLLLLLLLLLLLRLLLLLLLLL"

    Returns: {22, 219 }

  92. "LLLRLLLLLLLLLLLLLLLLLLLLLLLLLL"

    Returns: {5, 134 }

  93. "RRRRRRRRRRRRRRRRRRRRRRRRRRLRRR"

    Returns: {111, 28 }

  94. "RRRRRRRLRRRRRRRRRRRRRRRRRRRRRR"

    Returns: {206, 9 }

  95. "LLLLLLRLLLLLLLLLLLLLLLLLLLLLLL"

    Returns: {8, 191 }

  96. "RRRRRRRRRRRRRRRRRRRRRRRRLRRRRR"

    Returns: {155, 26 }

  97. "RRRRRRRRRLRRRRRRRRRRRRRRRRRRRR"

    Returns: {230, 11 }

  98. "RRRRRRRRRRRRRRRRRRRRRRLRRRRRRR"

    Returns: {191, 24 }

  99. "LLLLLLLLLLLLLLLLLLLRLLLLLLLLLL"

    Returns: {21, 230 }

  100. "RRRRRRRRRRRRRRRRRRRRRRRRRRRLRR"

    Returns: {86, 29 }

  101. "RRRRRRRRRRRRRRRRRRRRRRRRRRRRLR"

    Returns: {59, 30 }

  102. "RRRRRRRRRRLRRRRRRRRRRRRRRRRRRR"

    Returns: {239, 12 }

  103. "RRRRRRLRRRRRRRRRRRRRRRRRRRRRRR"

    Returns: {191, 8 }

  104. "LRLRLRLLLRLRRLLLLRLLLR"

    Returns: {11497, 9109 }

  105. "LRRLRLLRRRLLRLRRRLLRRRRLLL"

    Returns: {21311, 68734 }

  106. "LRRRLRRLRRRRLLLRRRLRLLLLR"

    Returns: {21934, 17993 }

  107. "LLLRRRLLRRLLRRRLRRLRRLLL"

    Returns: {8019, 26989 }

  108. "LL"

    Returns: {1, 3 }

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: