fork(11) download
  1. /* package whatever; // don't place package name! */
  2.  
  3. import java.util.*;
  4. import java.lang.*;
  5. import java.io.*;
  6.  
  7. /* Name of the class has to be "Main" only if the class is public. */
  8. class Ideone
  9. {
  10. private static int countRange(int[] numbers, int start, int end)
  11. {
  12. int count = 0;
  13. for(int i = 0; i < numbers.length; i++)
  14. if(numbers[i] >= start && numbers[i] <= end)
  15. ++count;
  16. return count;
  17. }
  18.  
  19. public static int getDuplication(int[] numbers)
  20. {
  21. int start = 1;
  22. int end = numbers.length;
  23. while(end >= start) {
  24. int middle = ((end - start) >> 1) + start;
  25. int count = countRange(numbers, start, middle);
  26. if(end == start) {
  27. if(count > 1)
  28. return start;
  29. else
  30. break;
  31. }
  32.  
  33. if(count > (middle - start + 1))
  34. end = middle;
  35. else
  36. start = middle + 1;
  37. }
  38. return -1;
  39. }
  40.  
  41. private static void test(String testName, int[] numbers, int[] duplications)
  42. {
  43. int result = getDuplication(numbers);
  44. for(int i = 0; i < duplications.length;++i)
  45. {
  46. if(result == duplications[i])
  47. {
  48. System.out.println(testName + " passed.");
  49. return;
  50. }
  51. }
  52. System.out.println(testName + " FAILED.");
  53. }
  54.  
  55. private static void test1()
  56. {
  57. int[] numbers = {2, 3, 5, 4, 3, 2, 6, 7};
  58. int[] duplications = {2, 3};
  59. test("test1", numbers, duplications);
  60. }
  61.  
  62. private static void test2()
  63. {
  64. int[] numbers = {3, 2, 1, 4, 4, 5, 6, 7};
  65. int[] duplications = {4};
  66. test("test2", numbers, duplications);
  67. }
  68.  
  69. private static void test3()
  70. {
  71. int[] numbers = {1, 2, 3, 4, 5, 6, 7, 1, 8};
  72. int[] duplications = {1};
  73. test("test3", numbers, duplications);
  74. }
  75.  
  76. private static void test4()
  77. {
  78. int[] numbers = {1, 7, 3, 4, 5, 6, 8, 2, 8};
  79. int[] duplications = {8};
  80. test("test4", numbers, duplications);
  81. }
  82.  
  83. private static void test5()
  84. {
  85. int[] numbers = {1, 1};
  86. int[] duplications = {1};
  87. test("test5", numbers, duplications);
  88. }
  89.  
  90. private static void test6()
  91. {
  92. int[] numbers = {3, 2, 1, 3, 4, 5, 6, 7};
  93. int[] duplications = {3};
  94. test("test6", numbers, duplications);
  95. }
  96.  
  97. private static void test7()
  98. {
  99. int[] numbers = {1, 2, 2, 6, 4, 5, 6};
  100. int[] duplications = {2, 6};
  101. test("test7", numbers, duplications);
  102. }
  103.  
  104. public static void main (String[] args) throws java.lang.Exception
  105. {
  106. test1();
  107. test2();
  108. test3();
  109. test4();
  110. test5();
  111. test6();
  112. test7();
  113. }
  114. }
Success #stdin #stdout 0.12s 320576KB
stdin
Standard input is empty
stdout
test1 passed.
test2 passed.
test3 passed.
test4 passed.
test5 passed.
test6 passed.
test7 passed.