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

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.

###

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.**- Simple approach to solve this problem is to traverse the array from i to array length
- Compare (arr[i]) with (arr[i]+ 1),
- If it is same then continue and if not same then that element appeared once.

**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.We will use same property to find element that appear once.

- We will do a binary search and find the middle index.
**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.**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 array; 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); } } } }

### You may also like to see

#### 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.**

## Post a Comment