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]);
    }
}