Statistics

Problem Statement for "BestApproximationDiv1"

Problem Statement

Elly is not a big fan of mathematical constants. Most of them are infinite, and therefore hard to memorize. Fractions, on the other hand, are often easier to remember and can provide good approximations. For example, 22/7 = 3.1428... is one way to approximate Pi. Unfortunately, it's only accurate to 2 places after the decimal point, so it doesn't help at all. A slightly better example is 355/113 = 3.14159292... which is correct up to 6 digits after the decimal point.

Elly understands that working with infinite decimal fractions is going to be very difficult, so she first wants to find a good way to approximate floating point numbers with decimal representations that are finite. Your task is to help her in this mission. You will be given a String number containing the decimal representation of a non-negative fraction strictly less than 1. There will be exactly 6 digits after the decimal point in number (trailing zeros are possible and significant). More precisely, number will be formatted "0.dddddd" (quotes for clarity) where each d is a decimal digit ('0'-'9').

Given a fraction F = A/B, where 0 <= A < B, its quality of approximation with respect to number is calculated as follows:
  • Let S be the decimal fraction (infinite or finite) representation of F.
  • If S is infinite or the number of digits after the decimal point in S is greater than 6, only consider the first 6 decimals after the decimal point in S. Truncate the rest of the digits without performing any kind of rounding.
  • If the number of digits after the decimal point in S is less than 6, append trailing zeroes to the right side until there are exactly 6 digits after the decimal point.
  • The quality of approximation is the number of digits in the longest common prefix of S and number. The longest common prefix of two numbers is the longest string which is a prefix of the decimal representations of both numbers with no extra leading zeroes. For example, "3.14" is the longest common prefix of 3.1428 and 3.1415.
Elly doesn't like long approximations either, so you are only allowed to use fractions where the denominator is less than or equal to maxDen. Find an approximation F = A/B of number such that 1 <= B <= maxDen, 0 <= A < B, and the quality of approximation is maximized. Return a String formatted "A/B has X exact digits" (quotes for clarity) where A/B is the approximation you have found and X is its quality. If there are several such approximations, choose the one with the smallest denominator among all of them. If there is still a tie, choose the one among those with the smallest numerator.

Definition

Class:
BestApproximationDiv1
Method:
findFraction
Parameters:
int, String
Returns:
String
Method signature:
String findFraction(int maxDen, String number)
(be sure your method is public)

Constraints

  • maxDen will be between 1 and 1000, inclusive.
  • number will contain exactly 8 characters.
  • number will consist of a digit '0', followed by a period ('.'), followed by exactly six digits ('0'-'9').

Examples

  1. 42

    "0.141592"

    Returns: "1/7 has 3 exact digits"

    3 plus the current approximation yields an approximation of Pi.

  2. 3

    "0.133700"

    Returns: "0/1 has 1 exact digits"

    Not a lot of options here.

  3. 1000

    "0.123456"

    Returns: "10/81 has 7 exact digits"

  4. 1000

    "0.420000"

    Returns: "21/50 has 7 exact digits"

    This one can be represented in more than one way. Be sure to choose the one with the lowest denominator.

  5. 100

    "0.909999"

    Returns: "10/11 has 4 exact digits"

    Even though 91/100 is a much closer approximation, 10/11 matches up to 3 digits, and 91/100 only to one.

  6. 115

    "0.141592"

    Returns: "16/113 has 7 exact digits"

    A better approximation for the decimal part of Pi.

  7. 1000

    "0.272727"

    Returns: "3/11 has 7 exact digits"

  8. 42

    "0.409488"

    Returns: "9/22 has 4 exact digits"

  9. 300

    "0.431233"

    Returns: "69/160 has 5 exact digits"

  10. 85

    "0.606618"

    Returns: "20/33 has 4 exact digits"

  11. 656

    "0.120014"

    Returns: "3/25 has 5 exact digits"

  12. 423

    "0.603801"

    Returns: "93/154 has 5 exact digits"

  13. 901

    "0.778383"

    Returns: "425/546 has 6 exact digits"

  14. 449

    "0.880681"

    Returns: "155/176 has 7 exact digits"

  15. 10

    "0.228289"

    Returns: "2/9 has 3 exact digits"

  16. 689

    "0.953252"

    Returns: "469/492 has 7 exact digits"

  17. 618

    "0.229419"

    Returns: "39/170 has 6 exact digits"

  18. 264

    "0.553282"

    Returns: "109/197 has 5 exact digits"

  19. 959

    "0.257444"

    Returns: "121/470 has 6 exact digits"

  20. 594

    "0.122264"

    Returns: "67/548 has 6 exact digits"

  21. 236

    "0.106750"

    Returns: "11/103 has 5 exact digits"

  22. 87

    "0.774579"

    Returns: "24/31 has 4 exact digits"

  23. 738

    "0.554026"

    Returns: "241/435 has 6 exact digits"

  24. 201

    "0.930747"

    Returns: "121/130 has 5 exact digits"

  25. 217

    "0.767719"

    Returns: "119/155 has 5 exact digits"

  26. 484

    "0.578583"

    Returns: "254/439 has 6 exact digits"

  27. 143

    "0.174823"

    Returns: "25/143 has 6 exact digits"

  28. 652

    "0.485925"

    Returns: "259/533 has 6 exact digits"

  29. 214

    "0.412908"

    Returns: "64/155 has 6 exact digits"

  30. 585

    "0.143552"

    Returns: "59/411 has 7 exact digits"

  31. 246

    "0.801322"

    Returns: "121/151 has 6 exact digits"

  32. 147

    "0.930087"

    Returns: "93/100 has 5 exact digits"

  33. 258

    "0.458615"

    Returns: "61/133 has 5 exact digits"

  34. 76

    "0.268266"

    Returns: "11/41 has 5 exact digits"

  35. 453

    "0.234343"

    Returns: "15/64 has 5 exact digits"

  36. 859

    "0.514363"

    Returns: "376/731 has 7 exact digits"

  37. 370

    "0.989135"

    Returns: "91/92 has 6 exact digits"

  38. 816

    "0.159083"

    Returns: "7/44 has 5 exact digits"

  39. 117

    "0.789415"

    Returns: "15/19 has 5 exact digits"

  40. 663

    "0.495234"

    Returns: "52/105 has 6 exact digits"

  41. 424

    "0.688277"

    Returns: "223/324 has 6 exact digits"

  42. 346

    "0.812149"

    Returns: "134/165 has 5 exact digits"

  43. 601

    "0.928205"

    Returns: "181/195 has 7 exact digits"

  44. 571

    "0.472149"

    Returns: "161/341 has 6 exact digits"

  45. 282

    "0.232466"

    Returns: "43/185 has 5 exact digits"

  46. 612

    "0.995556"

    Returns: "224/225 has 6 exact digits"

  47. 911

    "0.215444"

    Returns: "53/246 has 6 exact digits"

  48. 946

    "0.607272"

    Returns: "167/275 has 7 exact digits"

  49. 584

    "0.328601"

    Returns: "139/423 has 6 exact digits"

  50. 444

    "0.108109"

    Returns: "4/37 has 6 exact digits"

  51. 529

    "0.830362"

    Returns: "93/112 has 5 exact digits"

  52. 615

    "0.813678"

    Returns: "345/424 has 6 exact digits"

  53. 813

    "0.314310"

    Returns: "83/264 has 5 exact digits"

  54. 900

    "0.382321"

    Returns: "13/34 has 5 exact digits"

  55. 806

    "0.209891"

    Returns: "123/586 has 6 exact digits"

  56. 164

    "0.622143"

    Returns: "28/45 has 4 exact digits"

  57. 600

    "0.082740"

    Returns: "35/423 has 6 exact digits"

  58. 751

    "0.428571"

    Returns: "3/7 has 7 exact digits"

  59. 996

    "0.919941"

    Returns: "632/687 has 7 exact digits"

  60. 900

    "0.129411"

    Returns: "11/85 has 7 exact digits"

  61. 609

    "0.469879"

    Returns: "39/83 has 7 exact digits"

  62. 515

    "0.166666"

    Returns: "1/6 has 7 exact digits"

  63. 974

    "0.987261"

    Returns: "155/157 has 7 exact digits"

  64. 987

    "0.181286"

    Returns: "31/171 has 7 exact digits"

  65. 518

    "0.436507"

    Returns: "55/126 has 7 exact digits"

  66. 792

    "0.296208"

    Returns: "125/422 has 7 exact digits"

  67. 694

    "0.228571"

    Returns: "8/35 has 7 exact digits"

  68. 858

    "0.693877"

    Returns: "34/49 has 7 exact digits"

  69. 552

    "0.259615"

    Returns: "27/104 has 7 exact digits"

  70. 956

    "0.979166"

    Returns: "47/48 has 7 exact digits"

  71. 98

    "0.642857"

    Returns: "9/14 has 7 exact digits"

  72. 262

    "0.333333"

    Returns: "1/3 has 7 exact digits"

  73. 141

    "0.480000"

    Returns: "12/25 has 7 exact digits"

  74. 171

    "0.509803"

    Returns: "26/51 has 7 exact digits"

  75. 150

    "0.823529"

    Returns: "14/17 has 7 exact digits"

  76. 283

    "0.032520"

    Returns: "4/123 has 7 exact digits"

  77. 368

    "0.112299"

    Returns: "21/187 has 7 exact digits"

  78. 642

    "0.870588"

    Returns: "74/85 has 7 exact digits"

  79. 480

    "0.743902"

    Returns: "61/82 has 7 exact digits"

  80. 448

    "0.470588"

    Returns: "8/17 has 7 exact digits"

  81. 760

    "0.314545"

    Returns: "173/550 has 7 exact digits"

  82. 487

    "0.170212"

    Returns: "8/47 has 7 exact digits"

  83. 861

    "0.004756"

    Returns: "4/841 has 7 exact digits"

  84. 504

    "0.690647"

    Returns: "96/139 has 7 exact digits"

  85. 456

    "0.564516"

    Returns: "35/62 has 7 exact digits"

  86. 822

    "0.914285"

    Returns: "32/35 has 7 exact digits"

  87. 456

    "0.092342"

    Returns: "41/444 has 7 exact digits"

  88. 136

    "0.943820"

    Returns: "84/89 has 7 exact digits"

  89. 999

    "0.367816"

    Returns: "32/87 has 7 exact digits"

  90. 636

    "0.658602"

    Returns: "245/372 has 7 exact digits"

  91. 233

    "0.920454"

    Returns: "81/88 has 7 exact digits"

  92. 679

    "0.535294"

    Returns: "91/170 has 7 exact digits"

  93. 200

    "0.785714"

    Returns: "11/14 has 7 exact digits"

  94. 574

    "0.070671"

    Returns: "20/283 has 7 exact digits"

  95. 275

    "0.375000"

    Returns: "3/8 has 7 exact digits"

  96. 288

    "0.694444"

    Returns: "25/36 has 7 exact digits"

  97. 466

    "0.825136"

    Returns: "151/183 has 7 exact digits"

  98. 113

    "0.066666"

    Returns: "1/15 has 7 exact digits"

  99. 891

    "0.889589"

    Returns: "282/317 has 7 exact digits"

  100. 33

    "0.700000"

    Returns: "7/10 has 7 exact digits"

  101. 432

    "0.864516"

    Returns: "134/155 has 7 exact digits"

  102. 579

    "0.968354"

    Returns: "153/158 has 7 exact digits"

  103. 167

    "0.947368"

    Returns: "18/19 has 7 exact digits"

  104. 695

    "0.620833"

    Returns: "149/240 has 7 exact digits"

  105. 985

    "0.193333"

    Returns: "29/150 has 7 exact digits"

  106. 16

    "0.333333"

    Returns: "1/3 has 7 exact digits"

  107. 907

    "0.697936"

    Returns: "372/533 has 7 exact digits"

  108. 42

    "0.000000"

    Returns: "0/1 has 7 exact digits"

    Zero

  109. 1000

    "0.128124"

    Returns: "41/320 has 6 exact digits"

  110. 1000

    "0.128125"

    Returns: "41/320 has 7 exact digits"

  111. 1000

    "0.251199"

    Returns: "105/418 has 6 exact digits"

  112. 888

    "0.253740"

    Returns: "220/867 has 6 exact digits"

  113. 945

    "0.253749"

    Returns: "220/867 has 6 exact digits"

  114. 999

    "0.256240"

    Returns: "195/761 has 6 exact digits"

  115. 1000

    "0.256250"

    Returns: "41/160 has 7 exact digits"

  116. 853

    "0.258749"

    Returns: "37/143 has 6 exact digits"

  117. 934

    "0.258750"

    Returns: "207/800 has 7 exact digits"

  118. 989

    "0.502399"

    Returns: "105/209 has 6 exact digits"

  119. 601

    "0.502491"

    Returns: "302/601 has 6 exact digits"

  120. 599

    "0.502503"

    Returns: "201/400 has 6 exact digits"

  121. 400

    "0.507500"

    Returns: "203/400 has 7 exact digits"

  122. 240

    "0.512490"

    Returns: "103/201 has 5 exact digits"

  123. 790

    "0.512499"

    Returns: "103/201 has 5 exact digits"

  124. 766

    "0.522505"

    Returns: "209/400 has 6 exact digits"

  125. 1000

    "0.000001"

    Returns: "0/1 has 6 exact digits"

  126. 1000

    "0.001001"

    Returns: "1/999 has 7 exact digits"

  127. 5

    "0.200000"

    Returns: "1/5 has 7 exact digits"

  128. 1000

    "0.999999"

    Returns: "999/1000 has 4 exact digits"

  129. 10

    "0.000000"

    Returns: "0/1 has 7 exact digits"

  130. 2

    "0.500000"

    Returns: "1/2 has 7 exact digits"

  131. 1000

    "0.000000"

    Returns: "0/1 has 7 exact digits"

  132. 113

    "0.141592"

    Returns: "16/113 has 7 exact digits"

  133. 1

    "0.500000"

    Returns: "0/1 has 1 exact digits"

  134. 13

    "0.923076"

    Returns: "12/13 has 7 exact digits"

  135. 3

    "0.333333"

    Returns: "1/3 has 7 exact digits"

  136. 1000

    "0.005922"

    Returns: "3/506 has 6 exact digits"

  137. 11

    "0.909999"

    Returns: "10/11 has 4 exact digits"

  138. 1

    "0.999999"

    Returns: "0/1 has 1 exact digits"

  139. 1000

    "0.812983"

    Returns: "313/385 has 6 exact digits"

  140. 323

    "0.334113"

    Returns: "68/203 has 4 exact digits"

  141. 10

    "0.700000"

    Returns: "7/10 has 7 exact digits"

  142. 999

    "0.990990"

    Returns: "110/111 has 7 exact digits"

  143. 1000

    "0.009900"

    Returns: "1/101 has 7 exact digits"

  144. 1000

    "0.998999"

    Returns: "990/991 has 6 exact digits"

  145. 1

    "0.000000"

    Returns: "0/1 has 7 exact digits"

  146. 100

    "0.972972"

    Returns: "36/37 has 7 exact digits"

  147. 1000

    "0.039800"

    Returns: "8/201 has 7 exact digits"

  148. 414

    "0.801250"

    Returns: "125/156 has 5 exact digits"

  149. 21

    "0.952380"

    Returns: "20/21 has 7 exact digits"

  150. 7

    "0.142857"

    Returns: "1/7 has 7 exact digits"

  151. 10

    "0.100000"

    Returns: "1/10 has 7 exact digits"

  152. 500

    "0.908070"

    Returns: "326/359 has 6 exact digits"

  153. 1

    "0.000345"

    Returns: "0/1 has 4 exact digits"

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: