fork(14) download
copy 
  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
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
test1 passed.
test2 passed.
test3 passed.
test4 passed.
test5 passed.
test6 passed.
test7 passed.
https://ideone.com/lhV22m
language:
Java (HotSpot 12)
created:
8 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!