Non-Repeating Element Editorial

Practice Problem Link: Non-Repeating Element | Practice Problem

Please make sure to try solving the problem yourself before looking at the editorial.

Problem Statement

Given a sorted list of numbers in which all elements appear twice except one element that appears only once, find the number that appears only once.

Naive Approach

A simple way is to traverse the array, since it is sorted the element with a single occurrence can be found by comparing two consecutive elements.

Analysis

• Time Complexity : O(n)
• Space Complexity : O(1)

Implementation

C++

int findNonRepeatingElement(vector<int> arr) {
   int n = arr.size(), ans = -1;
   for (int i = 0; i < n - 1; i += 2) {
       if (arr[i] != arr[i + 1]) {
           ans = arr[i];
           break;
       }
   }
   if (ans == -1) {
       ans = arr[n - 1];
   }
   return ans;
}

Java

class Solution {
   int findNonRepeatingElement (int[] arr) {
       int n = arr.length, ans = -1;
       for (int i = 0; i < n - 1; i += 2) {
           if (arr[i] != arr[i + 1]) {
               ans = arr[i];
               break;
           }
       }
       if (ans == -1) {
           ans = arr[n - 1];
       }
       return ans;
   }
}

Efficient Approach

A simple way to find the answer is using the XOR operator. Since x^x=0 and x^0 = x. Taking XOR of all the values will give us the element with a single occurrence. Therefore, the XOR value of all the elements will be our answer.

Analysis

• Time Complexity : O(n)
• Space Complexity : O(1)

Implementation

C++

int findNonRepeatingElement(vector<int> arr) {
   int n = arr.size();
   int arrXor = 0;
   for (int i = 0; i < n; i++) {
       arrXor = arrXor ^ arr[i];
   }
   return arrXor;
}

Java

class Solution {
   int findNonRepeatingElement (int[] arr) {
       int n = arr.length;
       int arrXor = 0;
       for (int i=0; i < n; i++) {
           arrXor = arrXor ^ arr[i];
       }
       return arrXor;
   }
}

Optimal Approach

Since the array is sorted and all elements are occurring twice except one.

So the first occurrence of a particular element will be on even positions (i.e. 0, 2, 4…) and the second occurrence will be on odd positions ( i.e. 1, 3, 5…).

But after encountering the element with a single occurrence this property will change and the first occurrence will be on odd positions and the second occurrence will be on even positions.

This observation can be used to find the answer efficiently using binary search.

• Declare three variable low=0, high = n-1 and mid;
• While (low<=high) assign mid=(high+low)/2.
• If mid is even then check if arr[mid] and arr[mid+1] are equal. If yes, then the element must be in the second half otherwise the element must be in the first half.
• If mid is odd then check if arr[mid] and arr[mid-1] are equal. If yes, then the element must be in the second half otherwise the element must be in the first half.
• When low and high are equal, return the value of arr[low] as it is the only element that is not equal to its previous or next element.

Analysis

• Time Complexity : O(log(n))
• Space Complexity : O (1)

Implementation

C++ (Iterative)

int findNonRepeatingElement(vector<int> &arr) {
   int n = arr.size();
   int low = 0, high = n-1, mid;
   while (low <= high) {
       mid = (high + low) / 2;
       if (low == high) {
           return arr[mid];
       }
       if (mid % 2 == 0) {
           if (arr[mid] == arr[mid + 1]) {
               low = mid + 1;
           } else {
               high = mid;
           }
       } else {
           if (arr[mid] == arr[mid - 1]) {
               low = mid + 1;
           } else {
               high = mid;
           }
       }
   }
}

C++ (Recursive)

int binarySearch (vector<int> arr, int low, int high) {
   if (high >= low) {
       int mid = (high + low) / 2;
       if (low == high) {
           return arr[mid];
       }
       if (mid % 2 ==0) {
           if (arr[mid] == arr[mid + 1]) {
               return binarySearch (arr, mid + 1, high);
           } else {
               return binarySearch (arr, low, mid);
           }
       } else {
           if (arr[mid] == arr[mid - 1]) {
               return binarySearch (arr, mid + 1, high);
           } else {
               return binarySearch (arr, low, mid);
           }
       }
   }
}
int findNonRepeatingElement(vector<int> arr) {
   int n = arr.size();
   return binarySearch (arr, 0, n-1);
}

Java (Iterative)

class Solution {
   int findNonRepeatingElement (int[] arr) {
       int n = arr.length;
       int low = 0, high = n-1, mid;
       while (low <= high) {
           mid = (high + low) / 2;
           if (low == high) {
               return arr[mid];
           }
           if (mid % 2 == 0) {
               if (arr[mid] == arr[mid + 1]) {
                   low = mid + 1;
               } else {
                   high = mid;
               }
           } else {
               if (arr[mid] == arr[mid - 1]) {
                   low = mid + 1;
               } else {
                   high = mid;
               }
           }
       }
       return 0;
   }
}

Java (Recursive)

class Solution {
   int findNonRepeatingElement (int[] arr) {
       int n = arr.length;
       return binarySearch (arr, 0, n-1);
   }
   int binarySearch (int[] arr, int low, int high) {
       if (high >= low) {
           int mid = (high + low) / 2;
           if (low == high) {
               return arr[mid];
           }
           if (mid % 2 ==0) {
               if (arr[mid] == arr[mid + 1]) {
                   return binarySearch (arr, mid + 1, high);
               } else {
                   return binarySearch (arr, low, mid);
               }
           } else {
               if (arr[mid] == arr[mid - 1]) {
                   return binarySearch (arr, mid + 1, high);
               } else {
                   return binarySearch (arr, low, mid);
               }
           }
       }
       return 0;
   }
}