QUESTION
Input a sorted array of n elements containing elements in range from 1 to n-1 i.e. one element occurs twice, the task is to find the repeating element in an array.
“TESTCASE_1”: “6\n1 2 3 3 4 5\n###—###SEPERATOR—###—\n3”, “TESTCASE_2”: “5\n 1 2 3 4 4\n###—###SEPERATOR—###—\n4”, “TESTCASE_3”: “5\n1 1 2 3 4\n###—###SEPERATOR—###—\n1”, “TESTCASE_4”: “0\n###—###SEPERATOR—###—\n0”, “TESTCASE_5”: “0\n###—###SEPERATOR—###—\n0
ANSWER
import java.io.*;
import java.util.*;
class TestClass
{
// Returns index of second appearance of a repeating element
// The function assumes that array elements are in range from
// 1 to n-1.
static int findRepeatingElement(int arr[], int low, int high)
{
// low = 0 , high = n-1;
if (low > high)
return -1;
int mid = (low + high) / 2;
// Check if the mid element is the repeating one
if (arr[mid] != mid + 1)
{
if (mid > 0 && arr[mid]==arr[mid-1])
return mid;
// If mid element is not at its position that means
// the repeated element is in left
return findRepeatingElement(arr, low, mid-1);
}
// If mid is at proper position then repeated one is in
// right.
return findRepeatingElement(arr, mid+1, high);
}
// Driver method
public static void main(String[] args)
{
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
int arr[]=new int[n];
for(int i=0;i<n;i++)
arr[i]=sc.nextInt();
int index = findRepeatingElement(arr, 0, n-1);
if (index != -1)
System.out.println(arr[index]);
}
}