Find the element that appears once in a sorted array, where all elements appear twice(one after one) except one element appears only once.

Find the element that appears only once in a sorted array.
Given a sorted array in which all elements appear twice (one after one) and one element appears only once.
Find that element in O(Log n) complexity.

Input: arr[] = {1, 1, 2, 2, 3, 4, 4} Output: 3

Input: arr[] = {1, 1, 2, 2, 3, 3, 4}
 Output: 4

Input: arr[] = {1}
Output: 1 

Algorithm

---

Approach 1.

1. Simple approach to solve this problem is to traverse the array from i to array length 
2. Compare (arr[i]) with (arr[i]+ 1),
3. If it is same then continue and if not same then that element appeared once.

Above approach complexity is O(n). We can solve the same problem with O(Log N) complexity by using the sorted property.

Approach 2:

In this sample sequence [1, 1, 2, 2, 3, 3], we can see elements in pair. 
First pair, first element is at Even index(0), Second repeated element is at odd index(1). 
Second pair, first element is again at Even index(2), repeated element is at odd index(3). so on. 

We will use same property to find element that appear once.

1. We will do a binary search and find the middle index.


2. If mid index is Odd, it means Mid is pointing to second element of some pair and if we check (mid-1), we can get first element of that pair to see both are same or not.
   
   If both are same, it means till this point there is no discrepancy in series and element that appeared only once is at Right side of mid index, so check on Right side of mid.
   
   If both are not same, it means there is some discrepancy in series before mid and we will get the element that appeared only once at left side of mid index, so check on Left side of mid.
   


3. If mid index is Even, it means mid is pointing to first element of some pair and if we check (mid+1), we can get second element of that pair to see both are same or not.
   
   If both are same, it means till this point there is no discrepancy in series and element that appeared only once is at Right side of mid index, so check on Right side of mid.
   
   If both are not same, it means there is some discrepancy in series before mid and we will get the element that appeared only once at left side of mid index, so check on Left side of mid.

Java Program to find element that appears only once in a sorted array.

---

package javabypatel;

public class ElementThatAppearsOnceInSortedArray { 

 public static void main(String[] args) {
  new ElementThatAppearsOnceInSortedArray();
 }
 
 public ElementThatAppearsOnceInSortedArray() {
  int arr[] = {1, 1, 2, 2, 3, 3, 4};
  int value = getElementAppearedOnce(arr, 0, arr.length-1);
  if(value==-1){
   System.out.println("There is no element that appeared once in given sorted array.");
  }else{
   System.out.println("Element that appeared once in given sorted array is :"+value);
  }
 }

 private int getElementAppearedOnce(int arr[], int start, int end) {

  if(start>end){
   return -1;
  }
  
  //This case is will appear when input is {1, 1, 2}  
  if(start==end){
   return arr[start];
  }
  
  int mid = (start + end)/2;
  
  if(mid%2==0){
   //EVEN
   if(arr[mid] == arr[mid+1]){
    return getElementAppearedOnce(arr, mid+2, end);
   }else{
    return getElementAppearedOnce(arr, start, mid);
   }
   
  }else{
   //ODD
   if(arr[mid] == arr[mid-1]){
    return getElementAppearedOnce(arr, mid+1, end);
   }else{
    return getElementAppearedOnce(arr, start, mid);
   }
  }  
 }

}

---

Find the element that appears once others appears THRICE.

Merge two sorted arrays in Java

Union and Intersection of Two Sorted Arrays

Find all pairs of elements from array whose sum equals to given number K.

Find Minimum length Unsorted Subarray, Sorting which makes the complete array sorted.

Find Largest and Second Largest number in array

How Binary search Algorithm works in Java

 

Enjoy !!!! 

If you find any issue in post or face any error while implementing, Please comment.