Statistics

Problem Statement for "MinimizeAbsoluteDifferenceDiv1"

Problem Statement

You are given a int[] x that contains exactly five positive integers. You want to put four of them instead of the question marks into the following expression: | (?/?) - (?/?) |. Which numbers should you put there and in what order, if your goal is to make the value of the expression as small as possible?

More formally, you have the following expression: | (xa / xb) - (xc / xd) |. Here, "/" denotes real division (e.g., 7/2 = 3.5) and "||" denotes absolute value. You want to find the four distinct subscripts a, b, c, d for which the value of the expression is minimized.

Return a int[] with four elements: the optimal subscripts {a, b, c, d}. If there are multiple optimal answers, return the lexicographically smallest one among them.

Definition

Class:
MinimizeAbsoluteDifferenceDiv1
Method:
findTuple
Parameters:
int[]
Returns:
int[]
Method signature:
int[] findTuple(int[] x)
(be sure your method is public)

Notes

  • Given two distinct arrays A and B with the same number of elements, we say that A is lexicographically smaller than B if A has a smaller value at the first index at which they differ.

Constraints

  • x will contain exactly five elements.
  • Each element of x will be between 1 and 10,000, inclusive.

Examples

  1. {1,1,1,1,1}

    Returns: {0, 1, 2, 3 }

    Regardless of our choice of subscripts, the expression always evaluates to | (1/1) - (1/1) | = |1-1| = 0. The lexicographically smallest optimal solution is {0, 1, 2, 3}.

  2. {2,3,5,7,11}

    Returns: {0, 3, 1, 4 }

    Both {0, 3, 1, 4} ans {1, 4, 0, 3} would minimize the given expression, but {0, 3, 1, 4} comes lexicographically first, so that is the only correct answer. The corresponding expression is |(2/7) - (3/11)| = 0.012987

  3. {8, 2, 4, 2, 6}

    Returns: {1, 0, 3, 4 }

    There are four sets of subscripts that minimize the given expression: {1, 0, 3, 4}, {1, 4, 3, 0}, {3, 0, 1, 4}, and {3, 4, 1, 0}.

  4. {124, 182, 9, 33, 70}

    Returns: {2, 4, 3, 1 }

  5. {9947, 3, 7, 11, 13}

    Returns: {1, 4, 3, 0 }

  6. {10000, 4, 10, 4, 10}

    Returns: {1, 2, 3, 4 }

    The smallest possible value of our expression is |(4/10) - (4/10)| = 0.

  7. {34, 90, 4, 53, 86}

    Returns: {0, 4, 3, 1 }

  8. {99, 35, 22, 77, 50}

    Returns: {1, 3, 2, 4 }

  9. {93, 97, 36, 96, 29}

    Returns: {2, 1, 4, 0 }

  10. {61, 70, 82, 93, 11}

    Returns: {0, 2, 1, 3 }

  11. {34, 34, 27, 44, 41}

    Returns: {0, 3, 2, 1 }

  12. {19, 72, 14, 75, 48}

    Returns: {0, 1, 2, 4 }

  13. {67, 88, 45, 25, 23}

    Returns: {3, 1, 4, 0 }

  14. {73, 43, 1, 20, 54}

    Returns: {1, 0, 3, 4 }

  15. {24, 51, 93, 42, 88}

    Returns: {0, 1, 3, 4 }

  16. {15, 21, 45, 45, 91}

    Returns: {1, 2, 3, 4 }

  17. {31, 89, 14, 7, 70}

    Returns: {2, 4, 3, 0 }

  18. {19, 27, 94, 41, 63}

    Returns: {1, 4, 3, 2 }

  19. {18, 50, 28, 13, 20}

    Returns: {0, 2, 3, 4 }

  20. {8, 45, 37, 65, 40}

    Returns: {2, 1, 4, 3 }

  21. {93, 25, 95, 36, 39}

    Returns: {3, 0, 4, 2 }

  22. {94, 53, 48, 16, 88}

    Returns: {1, 0, 2, 4 }

  23. {8, 68, 18, 48, 20}

    Returns: {0, 4, 2, 3 }

  24. {35, 28, 14, 24, 43}

    Returns: {1, 4, 3, 0 }

  25. {63, 40, 90, 43, 3}

    Returns: {1, 0, 3, 2 }

  26. {55, 57, 86, 69, 54}

    Returns: {1, 2, 4, 3 }

  27. {906, 883, 621, 242, 358}

    Returns: {3, 2, 4, 0 }

  28. {286, 878, 582, 761, 348}

    Returns: {0, 3, 4, 1 }

  29. {487, 323, 614, 165, 824}

    Returns: {1, 4, 3, 0 }

  30. {345, 277, 435, 535, 934}

    Returns: {0, 3, 1, 2 }

  31. {478, 701, 299, 564, 920}

    Returns: {0, 4, 2, 3 }

  32. {64, 838, 91, 883, 929}

    Returns: {0, 1, 2, 4 }

  33. {773, 461, 548, 987, 465}

    Returns: {1, 0, 2, 3 }

  34. {150, 483, 106, 199, 767}

    Returns: {0, 4, 2, 1 }

  35. {672, 505, 740, 14, 540}

    Returns: {1, 0, 4, 2 }

  36. {751, 114, 255, 387, 144}

    Returns: {2, 0, 4, 3 }

  37. {543, 202, 640, 561, 136}

    Returns: {1, 2, 4, 0 }

  38. {314, 279, 613, 542, 862}

    Returns: {0, 2, 1, 3 }

  39. {441, 643, 504, 295, 843}

    Returns: {0, 4, 3, 2 }

  40. {874, 746, 590, 787, 193}

    Returns: {1, 0, 2, 3 }

  41. {353, 455, 988, 413, 937}

    Returns: {1, 2, 3, 4 }

  42. {65, 178, 45, 221, 832}

    Returns: {1, 4, 2, 3 }

  43. {51, 197, 860, 508, 666}

    Returns: {0, 3, 1, 2 }

  44. {981, 117, 833, 1000, 994}

    Returns: {0, 3, 2, 4 }

  45. {141, 694, 369, 866, 292}

    Returns: {2, 3, 4, 1 }

  46. {962, 796, 251, 421, 699}

    Returns: {2, 4, 3, 0 }

  47. {118, 194, 943, 887, 20}

    Returns: {0, 2, 4, 1 }

  48. {216, 216, 165, 850, 555}

    Returns: {0, 3, 2, 4 }

  49. {462, 973, 948, 346, 628}

    Returns: {0, 2, 3, 4 }

  50. {705, 561, 670, 216, 407}

    Returns: {1, 0, 4, 2 }

  51. {87, 325, 827, 621, 610}

    Returns: {1, 3, 4, 2 }

  52. {571, 498, 41, 864, 20}

    Returns: {2, 3, 4, 1 }

  53. {853, 127, 550, 838, 913}

    Returns: {2, 0, 3, 4 }

  54. {851, 199, 382, 12, 902}

    Returns: {1, 4, 3, 2 }

  55. {171, 565, 285, 847, 352}

    Returns: {0, 4, 2, 1 }

  56. {239, 446, 854, 914, 212}

    Returns: {0, 3, 4, 2 }

  57. {637, 4676, 5794, 2040, 7326}

    Returns: {0, 1, 3, 4 }

  58. {1708, 2762, 2935, 6213, 6525}

    Returns: {1, 3, 2, 4 }

  59. {4327, 8501, 2074, 6016, 7904}

    Returns: {0, 4, 3, 1 }

  60. {4667, 7586, 5900, 399, 2859}

    Returns: {0, 1, 4, 2 }

  61. {5727, 6408, 3010, 6111, 7963}

    Returns: {0, 1, 3, 4 }

  62. {7403, 4519, 6513, 898, 9051}

    Returns: {1, 0, 2, 4 }

  63. {1020, 5277, 6143, 1379, 1315}

    Returns: {0, 1, 4, 2 }

  64. {1179, 3542, 8328, 139, 3132}

    Returns: {0, 1, 4, 2 }

  65. {3347, 4771, 7261, 2870, 7137}

    Returns: {0, 2, 3, 4 }

  66. {2166, 2671, 9619, 9207, 4576}

    Returns: {0, 3, 1, 2 }

  67. {5619, 5861, 5321, 4349, 841}

    Returns: {2, 1, 3, 0 }

  68. {7381, 5697, 5972, 8234, 5861}

    Returns: {1, 0, 2, 3 }

  69. {5892, 7066, 8842, 9747, 6434}

    Returns: {1, 3, 4, 2 }

  70. {3396, 2890, 2747, 9747, 1927}

    Returns: {2, 0, 4, 1 }

  71. {9524, 9674, 3672, 4774, 8457}

    Returns: {2, 4, 3, 1 }

  72. {8029, 7548, 1946, 7445, 8056}

    Returns: {1, 4, 3, 0 }

  73. {7343, 113, 5085, 2179, 7278}

    Returns: {1, 2, 3, 0 }

  74. {6951, 9215, 9424, 3358, 7874}

    Returns: {0, 1, 4, 2 }

  75. {530, 1398, 7483, 3424, 7600}

    Returns: {0, 3, 1, 4 }

  76. {9743, 8510, 4897, 1634, 593}

    Returns: {3, 0, 4, 2 }

  77. {6097, 881, 3678, 7068, 2174}

    Returns: {1, 2, 4, 3 }

  78. {8332, 6934, 2027, 556, 7859}

    Returns: {2, 0, 3, 1 }

  79. {4026, 2152, 2541, 354, 2784}

    Returns: {1, 4, 2, 0 }

  80. {1780, 4428, 8440, 9056, 1499}

    Returns: {0, 3, 4, 2 }

  81. {8540, 1196, 3540, 9259, 7187}

    Returns: {1, 4, 2, 3 }

  82. {381, 9527, 9178, 7835, 4607}

    Returns: {3, 1, 4, 2 }

  83. {3006, 7069, 2632, 9838, 2477}

    Returns: {0, 3, 4, 1 }

  84. {908, 9280, 5947, 1644, 2074}

    Returns: {0, 2, 3, 1 }

  85. {2511, 2930, 9765, 2069, 4688}

    Returns: {1, 2, 3, 4 }

  86. {1802, 6003, 6465, 2818, 6525}

    Returns: {0, 1, 3, 4 }

  87. {6061, 6739, 4463, 1944, 9605}

    Returns: {0, 4, 2, 1 }

  88. {2281, 6585, 3947, 2276, 8308}

    Returns: {0, 4, 3, 1 }

  89. {6922, 5946, 7001, 2118, 2745}

    Returns: {3, 1, 4, 2 }

  90. {5695, 4586, 5052, 7729, 5392}

    Returns: {1, 4, 2, 0 }

  91. {6221, 2704, 3323, 9156, 2581}

    Returns: {2, 3, 4, 0 }

  92. {9148, 9055, 7538, 7154, 5696}

    Returns: {3, 0, 4, 2 }

  93. {3308, 5562, 4500, 3398, 4118}

    Returns: {0, 2, 4, 1 }

  94. {9562, 1843, 4147, 4424, 8830}

    Returns: {2, 4, 3, 0 }

  95. {3801, 8063, 6116, 7657, 6962}

    Returns: {2, 3, 4, 1 }

  96. {9759, 8524, 8983, 6105, 6615}

    Returns: {3, 2, 4, 0 }

  97. {9520, 2198, 5536, 3218, 1630}

    Returns: {3, 0, 4, 2 }

  98. {9936, 9369, 4343, 2587, 6357}

    Returns: {2, 0, 3, 4 }

  99. {1025, 8328, 3594, 8310, 6539}

    Returns: {0, 4, 2, 1 }

  100. {2282, 3269, 5624, 1863, 1700}

    Returns: {0, 2, 4, 1 }

  101. {6460, 5024, 3134, 7905, 6925}

    Returns: {0, 3, 1, 4 }

  102. {6702, 4438, 1209, 9183, 8680}

    Returns: {0, 3, 1, 4 }

  103. {5598, 3589, 7101, 7478, 8983}

    Returns: {0, 3, 2, 4 }

  104. {2899, 2413, 3622, 5839, 8509}

    Returns: {1, 3, 2, 4 }

  105. {8371, 7424, 8254, 1259, 2352}

    Returns: {3, 1, 4, 0 }

  106. {9779, 8616, 9036, 5874, 2576}

    Returns: {1, 0, 3, 2 }

  107. {6718, 8946, 7223, 5809, 7191}

    Returns: {3, 2, 4, 1 }

  108. {5365, 9819, 8689, 5638, 7664}

    Returns: {0, 2, 3, 1 }

  109. {9221, 8232, 7862, 5382, 5125}

    Returns: {3, 1, 4, 2 }

  110. {8788, 9501, 5581, 9069, 6748}

    Returns: {2, 0, 4, 1 }

  111. {6516, 5788, 9800, 7683, 6007}

    Returns: {0, 2, 1, 3 }

  112. {7361, 5876, 6703, 8169, 7969}

    Returns: {1, 0, 2, 3 }

  113. {9998, 9116, 7607, 5761, 5782}

    Returns: {3, 1, 4, 0 }

  114. {5776, 7478, 6910, 7488, 9969}

    Returns: {0, 3, 1, 4 }

  115. {5298, 5796, 8573, 5099, 8632}

    Returns: {0, 4, 3, 2 }

  116. {7065, 6433, 7722, 6556, 6112}

    Returns: {3, 2, 4, 0 }

  117. {6162, 9626, 9467, 8401, 8269}

    Returns: {3, 1, 4, 2 }

  118. {9047, 6479, 9485, 8591, 7146}

    Returns: {1, 3, 4, 2 }

  119. {5411, 7681, 6028, 7121, 7825}

    Returns: {0, 3, 2, 4 }

  120. {6907, 6379, 9466, 8290, 8518}

    Returns: {0, 2, 1, 4 }

  121. {9917, 7183, 6570, 9257, 9395}

    Returns: {1, 0, 2, 3 }

  122. {7096, 8549, 6851, 9919, 7576}

    Returns: {2, 1, 4, 3 }

  123. {7782, 6733, 8975, 8530, 5871}

    Returns: {1, 2, 4, 0 }

  124. {6961, 9088, 5554, 6966, 10000}

    Returns: {0, 1, 2, 3 }

  125. {5333, 8917, 8959, 5669, 8089}

    Returns: {0, 4, 3, 1 }

  126. {7297, 8770, 7200, 6499, 7851}

    Returns: {0, 1, 3, 4 }

  127. {9739, 9129, 9146, 9529, 9364}

    Returns: {2, 3, 4, 0 }

  128. {9463, 9981, 9491, 9843, 9611}

    Returns: {2, 3, 4, 1 }

  129. {9339, 9340, 9036, 9421, 9047}

    Returns: {2, 0, 4, 1 }

  130. {9828, 9695, 9814, 9284, 9258}

    Returns: {3, 0, 4, 2 }

  131. {9978, 9484, 9844, 9964, 9841}

    Returns: {2, 0, 4, 3 }

  132. {9671, 9736, 9019, 9692, 9754}

    Returns: {0, 1, 3, 4 }

  133. {9298, 9515, 9126, 9231, 9480}

    Returns: {0, 1, 3, 4 }

  134. {9685, 9158, 9463, 9977, 9835}

    Returns: {1, 0, 2, 3 }

  135. {9554, 9446, 9700, 9823, 9615}

    Returns: {0, 3, 1, 2 }

  136. {9438, 9530, 9387, 9941, 9782}

    Returns: {1, 3, 2, 4 }

  137. {9045, 9242, 9679, 9613, 9999}

    Returns: {1, 2, 3, 4 }

  138. {9755, 9716, 9453, 9271, 9171}

    Returns: {3, 0, 4, 1 }

  139. {9510, 9352, 9857, 9736, 9969}

    Returns: {0, 2, 1, 3 }

  140. {9718, 9698, 9973, 9885, 9615}

    Returns: {1, 2, 4, 3 }

  141. {9376, 9324, 9737, 9500, 9533}

    Returns: {0, 4, 1, 3 }

  142. {9491, 9373, 9470, 9616, 9606}

    Returns: {0, 3, 2, 4 }

  143. {9033, 9150, 9144, 9974, 9493}

    Returns: {0, 1, 2, 4 }

  144. {9658, 9995, 9610, 9799, 9683}

    Returns: {0, 3, 2, 4 }

  145. {9800, 9211, 9826, 9439, 9691}

    Returns: {1, 4, 3, 2 }

  146. {9555, 9043, 9176, 9269, 9564}

    Returns: {2, 0, 3, 4 }

  147. {9344, 9527, 9211, 9795, 9562}

    Returns: {0, 4, 1, 3 }

  148. {9562, 9963, 9828, 9382, 9341}

    Returns: {0, 1, 3, 2 }

  149. {9081, 9756, 9371, 9754, 9852}

    Returns: {0, 3, 2, 4 }

  150. {9178, 9238, 9119, 9726, 9277}

    Returns: {0, 4, 2, 1 }

  151. {9257, 9885, 9295, 9080, 9596}

    Returns: {2, 1, 3, 4 }

  152. {9661, 9632, 9674, 9585, 9180}

    Returns: {1, 2, 3, 0 }

  153. {9848, 9631, 9725, 9021, 9751}

    Returns: {1, 4, 2, 0 }

  154. {9084, 9077, 9579, 9613, 9297}

    Returns: {0, 3, 1, 2 }

  155. {9792, 9422, 9243, 9881, 9968}

    Returns: {1, 4, 2, 0 }

  156. {9840, 9523, 9297, 9480, 9022}

    Returns: {2, 0, 4, 1 }

  157. {9995, 10000, 9994, 9996, 10000 }

    Returns: {0, 1, 2, 4 }

  158. {4999, 9999, 4000, 8000, 5000 }

    Returns: {0, 1, 2, 3 }

  159. {3, 20, 10, 4, 14 }

    Returns: {0, 2, 3, 4 }

  160. {1, 9998, 1, 10000, 9999 }

    Returns: {0, 3, 2, 4 }

  161. {6450, 1941, 2889, 4300, 2934 }

    Returns: {1, 3, 2, 0 }

  162. {1, 2, 4, 8, 15 }

    Returns: {0, 1, 2, 3 }

  163. {10000, 9999, 9998, 9997, 9996 }

    Returns: {2, 0, 3, 1 }

  164. {1, 1, 9997, 9998, 9999 }

    Returns: {0, 3, 1, 4 }

  165. {9994, 10000, 10000, 10000, 9997 }

    Returns: {0, 1, 4, 2 }

  166. {4999, 9999, 4500, 9000, 5000 }

    Returns: {0, 1, 2, 3 }

  167. {1273, 7545, 879, 7924, 7710 }

    Returns: {0, 3, 2, 1 }

  168. {4, 3, 2, 10000, 10000 }

    Returns: {0, 3, 1, 4 }

  169. {9916, 9954, 9954, 9914, 9915 }

    Returns: {0, 1, 4, 2 }

  170. {1573, 4716, 785, 6740, 1797 }

    Returns: {0, 1, 4, 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: