Statistics

Problem Statement for "AgeEncoding"

Problem Statement

NOTE: This problem statement contains superscripts that may not display properly if viewed outside of the applet.

Your friend's birthday is approaching, and he wants his age to be written in candles on his cake. In fact, he has already placed several candles on the cake. The candles are arranged in a single row, and there are two different colors of candles. One color represents the digit '0' and the other color represents the digit '1'. You don't want to relayout the candles from scratch, so you have to determine if there's a base for which the existing candles spell out your friend's age. To simplify the task, you can choose any strictly positive base, not necessarily an integer one.

For example, if the candles are "00010" and your friend's age is 10, then the candles spell out 10 in base 10 (decimal). If the candles are "10101" and your friend's age is 21, then you can say that "10101" is 21 in base 2 (binary). If the candles are "10100" and your friend's age is 6, then the candles spell out 6 in base sqrt(2)=1.41421356237.... Note that you are not allowed to rotate the cake, so "10" cannot be read as "01".

You are given a String candlesLine, where the i-th character is the digit ('0' or '1') represented by the i-th candle in the row of candles on the cake. You are also given an int age, which is your friend's age. Return the positive base for which the candles represent your friend's age. If there is no such base, return -1, and if there are multiple such bases, return -2.

Definition

Class:
AgeEncoding
Method:
getRadix
Parameters:
int, String
Returns:
double
Method signature:
double getRadix(int age, String candlesLine)
(be sure your method is public)

Notes

  • The number anan-1...a1a0 in base B is equal to an*Bn + an-1*Bn-1 + ... + a1*B + a0.
  • The returned value must have an absolute or relative error less than 1e-9.

Constraints

  • age will be between 1 and 100, inclusive.
  • candlesLine will contain between 1 and 50 characters, inclusive.
  • Each character in candlesLine will be '0' (zero) or '1' (one).

Examples

  1. 1

    "0000000001"

    Returns: -2.0

    Same as previous, but with prefix of zeroes.

  2. 10

    "00010"

    Returns: 10.0

    This is the first example from the statement: simply a decimal notation of the given age. Note that notation can have leading zeroes.

  3. 21

    "10101"

    Returns: 2.0

    This is the second example from the statement: "10101" is a binary notation of the given age.

  4. 6

    "10100"

    Returns: 1.414213562373095

    This is the third example from the statement.

  5. 21

    "10111111110111101111111100111111110111111111111100"

    Returns: 0.9685012944510603

  6. 16

    "1"

    Returns: -1.0

    In any base, "1" represents the age of 1, so it's impossible to get the age of 16.

  7. 100

    "00000000000000000000000000000000000000000000000001"

    Returns: -1.0

    Tests #7..#10 give -1 in answer as 1 with prefix of zeroes.

  8. 2

    "00000000000001"

    Returns: -1.0

  9. 67

    "000001"

    Returns: -1.0

  10. 45

    "0000000000000000000000000001"

    Returns: -1.0

  11. 12

    "000000000000000000"

    Returns: -1.0

    Tests #11..#15 give -1 in answer as a string of zeroes.

  12. 1

    "0"

    Returns: -1.0

  13. 89

    "0000000000000"

    Returns: -1.0

  14. 30

    "00000000000000000000000"

    Returns: -1.0

  15. 92

    "00000000000000000000000000000000000000"

    Returns: -1.0

  16. 1

    "11"

    Returns: -1.0

    Tests #16..#20 give -1 in answer as age = 1, last candle = 1 and one more candle = 1 (radix must be positive).

  17. 1

    "00000101010111100101"

    Returns: -1.0

  18. 1

    "1000000000000000001"

    Returns: -1.0

  19. 1

    "00000000000000000000000011"

    Returns: -1.0

  20. 1

    "11111111111111111111111111111111111111111111111111"

    Returns: -1.0

  21. 2

    "11111111111111111111111111111111111111111111111111"

    Returns: 0.5000000000000004

    Tests #21..#35 have answers < 1; this one is the smallest positive answer.

  22. 9

    "11010100000110110011010011110000001010001100"

    Returns: 0.9644794251470961

  23. 5

    "0010111100011100100011100111110010100100000"

    Returns: 0.9309717675171341

  24. 16

    "101100101001010001000100001100010100101010011"

    Returns: 0.9944695714404173

  25. 18

    "1111111111111111111111001110111110101011010"

    Returns: 0.9693534692411785

  26. 8

    "11011011000101100100001110110011011110"

    Returns: 0.9311630570557434

  27. 9

    "10110100100000000000001111000010111101001100100"

    Returns: 0.9627071967682421

  28. 22

    "1111110110111001110001111110000011011111"

    Returns: 0.9895933446048641

  29. 23

    "0010111110011000110000110001001110111111011"

    Returns: 0.9977234441488432

  30. 2

    "1110111101100011000001111100001011010111111111"

    Returns: 0.5006397696081122

  31. 2

    "1110"

    Returns: 0.8105357137661366

  32. 13

    "000100101100100001010000100010011000101011110101"

    Returns: 0.9784654171063285

  33. 12

    "10101000100110100100001111101"

    Returns: 0.9872784768442795

  34. 5

    "00101100000011010000111100101100011111111"

    Returns: 0.8290109440147917

  35. 10

    "011100111001110010111110101110100100011011"

    Returns: 0.9477260512129781

  36. 2

    "10000000000000000000000000000000000001"

    Returns: 1.0

    Tests #36..#45 have answers = 1 (number of ones in candles = age).

  37. 50

    "11111111111111111111111111111111111111111111111111"

    Returns: 1.0

  38. 36

    "11011110111011101111011001110101011100001111111111"

    Returns: 1.0

  39. 10

    "00111111000111100"

    Returns: 1.0

  40. 3

    "10000000000000100000000000000010000000000"

    Returns: 1.0

  41. 18

    "111111111111111111"

    Returns: 1.0

  42. 4

    "10101010"

    Returns: 1.0

  43. 47

    "00011111111111111111111111111111111111111111111111"

    Returns: 1.0

  44. 25

    "01010101010101010101010101010101010101010101010101"

    Returns: 1.0

  45. 6

    "00001000000000000011000000010000001000000000010000"

    Returns: 1.0

  46. 100

    "10"

    Returns: 100.0

    Tests #46..#60 have answers > 1; this one is the greatest positive answer.

  47. 51

    "01000011101101111"

    Returns: 1.2236414744554485

  48. 60

    "100100001000011000000011"

    Returns: 1.1509288756564846

  49. 54

    "001111101110001111111100000101000010011011001000"

    Returns: 1.028016867065817

  50. 23

    "00100111001"

    Returns: 1.3571025593119632

  51. 29

    "010"

    Returns: 29.0

  52. 100

    "111"

    Returns: 9.462429422585636

  53. 34

    "1110"

    Returns: 2.846080416586016

  54. 43

    "000001100"

    Returns: 3.1997844694936415

  55. 28

    "0110"

    Returns: 4.815072906367325

  56. 46

    "00101001"

    Returns: 2.05177896477014

  57. 86

    "0111001"

    Returns: 2.196489503489521

  58. 97

    "100"

    Returns: 9.848857801796104

  59. 32

    "01100"

    Returns: 2.8740406307399775

  60. 94

    "00000011100"

    Returns: 2.823192803157676

  61. 42

    "0101010"

    Returns: 2.0

    Finally, tests #61..#65 have integer answers > 1.

  62. 40

    "00001111"

    Returns: 3.0

  63. 100

    "11"

    Returns: 99.0

  64. 31

    "000111"

    Returns: 5.0

  65. 82

    "10001"

    Returns: 3.0

  66. 1

    "1"

    Returns: -2.0

    In any base, "1" represents the age of 1.

  67. 1

    "001000"

    Returns: 1.0

  68. 1

    "0100101000100001100110000110000010011011000001100"

    Returns: 0.7156223647008804

  69. 1

    "1001011101111110"

    Returns: 0.5021889649688411

  70. 1

    "01"

    Returns: -2.0

  71. 12

    "000"

    Returns: -1.0

  72. 99

    "0001010"

    Returns: 4.55401544737385

  73. 1

    "1000001"

    Returns: -1.0

  74. 1

    "00001"

    Returns: -2.0

  75. 1

    "111"

    Returns: -1.0

  76. 1

    "10000000000000000000000000000000000000"

    Returns: 1.0

  77. 1

    "001"

    Returns: -2.0

  78. 40

    "0001010101"

    Returns: 1.7320508075688772

  79. 1

    "001001"

    Returns: -1.0

  80. 1

    "000000001"

    Returns: -2.0

  81. 1

    "10001"

    Returns: -1.0

  82. 1

    "00000000001"

    Returns: -2.0

  83. 79

    "10011110000000000000000"

    Returns: 1.158750849464906

  84. 1

    "0001"

    Returns: -2.0

  85. 1

    "000"

    Returns: -1.0

  86. 17

    "000001"

    Returns: -1.0

  87. 1

    "0101"

    Returns: -1.0

  88. 1

    "101"

    Returns: -1.0

  89. 22

    "000"

    Returns: -1.0

  90. 1

    "01000000000001"

    Returns: -1.0

  91. 12

    "1001000"

    Returns: 1.4422495703074083

  92. 1

    "1000000001"

    Returns: -1.0

  93. 100

    "00000000000000000000000000000000000000000000000000"

    Returns: -1.0

  94. 1

    "10000000000000000000000000000000000000000000000001"

    Returns: -1.0

  95. 1

    "00000"

    Returns: -1.0

  96. 1

    "0000001"

    Returns: -2.0

  97. 1

    "000000"

    Returns: -1.0

  98. 100

    "00"

    Returns: -1.0

  99. 2

    "0000"

    Returns: -1.0

  100. 1

    "10000000001"

    Returns: -1.0

  101. 1

    "00000000000"

    Returns: -1.0

  102. 1

    "1000000000000000000000000000000000000000000000001"

    Returns: -1.0

  103. 2

    "0000000"

    Returns: -1.0

  104. 76

    "0000000000000101010000010101000000000010"

    Returns: 1.1303025599812826

  105. 1

    "1111111111111"

    Returns: -1.0

  106. 12

    "0"

    Returns: -1.0

  107. 2

    "00000"

    Returns: -1.0

  108. 1

    "00"

    Returns: -1.0

  109. 1

    "1111"

    Returns: -1.0

  110. 1

    "10111"

    Returns: -1.0

  111. 13

    "0000000000000000000000000000"

    Returns: -1.0

  112. 1

    "00000000000000000000000000000000000000000000000000"

    Returns: -1.0

  113. 1

    "1110"

    Returns: 0.5436890126920764

  114. 1

    "0000"

    Returns: -1.0

  115. 1

    "000001"

    Returns: -2.0

  116. 2

    "0000000001"

    Returns: -1.0

  117. 10

    "00000"

    Returns: -1.0

  118. 1

    "00000000011"

    Returns: -1.0

  119. 15

    "0000"

    Returns: -1.0

  120. 1

    "000000000001"

    Returns: -2.0

  121. 1

    "1000000000000000000000000001"

    Returns: -1.0

  122. 1

    "000010000000000000000000000000000001"

    Returns: -1.0

  123. 1

    "01001"

    Returns: -1.0

  124. 1

    "00101"

    Returns: -1.0

  125. 100

    "10010111100011111111111000011111111100001111111000"

    Returns: 1.039931700589173

  126. 97

    "10111111110111101111111100111111101111111111111001"

    Returns: 1.0307240644576114

  127. 99

    "1011111111011110111111110011111111011111111111110"

    Returns: 1.0324432710335931

  128. 1

    "110"

    Returns: 0.6180339887498949

  129. 99

    "0000000000000"

    Returns: -1.0

  130. 37

    "11111111111111111111111111111111111111111111111111"

    Returns: 0.9870777697927564

  131. 10

    "0"

    Returns: -1.0

  132. 1

    "101101101"

    Returns: -1.0

  133. 11

    "000"

    Returns: -1.0

  134. 12

    "00000"

    Returns: -1.0

  135. 4

    "00"

    Returns: -1.0

  136. 2

    "000"

    Returns: -1.0

  137. 1

    "11111111"

    Returns: -1.0

  138. 10

    "000"

    Returns: -1.0

  139. 1

    "1110111101111111100111111110111111111111101101011"

    Returns: -1.0

  140. 1

    "00100010"

    Returns: 0.7548776662466927

  141. 1

    "10000000000000000001"

    Returns: -1.0

  142. 1

    "011"

    Returns: -1.0

  143. 42

    "00000000000000000000000000000000000000000"

    Returns: -1.0

  144. 1

    "10"

    Returns: 1.0

  145. 5

    "00000"

    Returns: -1.0

  146. 26

    "111111111111111111111111111111111111111111111111"

    Returns: 0.9708225675355608

  147. 12

    "000000"

    Returns: -1.0

  148. 100

    "0"

    Returns: -1.0

  149. 20

    "0"

    Returns: -1.0

  150. 1

    "10000001"

    Returns: -1.0

  151. 5

    "10000000000000000000000000000000000000000000000000"

    Returns: 1.0333910454328783

  152. 1

    "1001"

    Returns: -1.0

  153. 2

    "00"

    Returns: -1.0

  154. 10

    "0000"

    Returns: -1.0

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: