# C++ Program to find the element that occurs once

Write a program to find the element in the array that occurs once. Given that all the numbers in the array are present two times and the array is sorted, find the single occurring element.

For example

Input

arr[] = {10, 10, 20, 30, 30, 40, 40, 50, 50} N = 9

Output

20

Explanation

Among all the elements 20 is occurring once.

Input

arr[] = {1, 1,  2,  5, 5} N = 5

Output

2

Explanation

Among all the elements 2 is occurring once.

### Naive approach

As we can see the array given is in sorted manner. Run a loop from begin to end and increment the i by 2. Inside the for loop if arr[i] != arr[i+1], store the arr[i] as ans.

C++ Code

`#include <bits/stdc++.h>using namespace std;void search_single(int arr[], int n) // function to check the single occurring element{    int ans = -1; // initially it is -1    for (int i = 0; i < n; i += 2) { // run for and increment i by 2        if (arr[i] != arr[i + 1]) { // check the duplicity            ans = arr[i]; // update ans if found            break;        }    }    if (arr[n - 2] != arr[n - 1]) // check if last element is unique or not            ans = arr[n-1];    cout << "The single occurring element is " << ans << "\n"; // print ans}// Driver codeint main(){    int arr[] = { 1, 1, 2, 4, 4, 5, 5, 6, 6 };    int n = sizeof(arr) / sizeof(arr); // find size of the array    search_single(arr, n);    return 0;}`

Output

`The single occurring element is 2`

C code

`#include <stdio.h>void search_single(int arr[], int n) // function to check the single occuring element{    int ans = -1; // initially it is -1    for (int i = 0; i < n; i += 2) { // run for and increment i by 2        if (arr[i] != arr[i + 1]) { // check the duplicacy            ans = arr[i]; // update ans if found            break;        }    }    if (arr[n - 2] != arr[n - 1]) // check if last element is unique or not            ans = arr[n-1];    printf( "The single occurring element is %d",ans); // print ans}/int main(){    int arr[] = { 1, 1, 2, 4, 4, 5, 5, 6, 6 };    int n = sizeof(arr) / sizeof(arr); // find size of the array    search_single(arr, n);    return 0;}`

Output

`The single occurring element is 2`

Time complexity - O(n)

Space complexity - O(1)

### Using XOR

To find the singly occurring element, we can use the idea of XOR operation.

a^a = 0 and a^0 = a

It means whenever we will encounter two same elements the output will be 0 and if an element and zero goes under XOR operation the result will be a.

For example

arr[]= {1, 1, 2}

Let ans be the output variable

ans = 1^0= 1

ans = 1^1 = 0

ans = 0^2 = 2

Operations at bit level are extremely fast. So, this operation is faster than the naive approach.

Approach

• Run a loop from 0 to n.
• Declare a variable ans.
• Under the loop run ans = ans ^ arr[i]
• Print ans

C++ code

`#include <bits/stdc++.h>using namespace std;void search_single(int arr[], int n) // function to check the single occuring element{     int ans = 0;    for (int i = 0; i < n; i++) {        ans = ans ^ arr[i];    }    cout << "The single occurring element is " << ans << "\n"; // print ans}int main(){    int arr[] = { 1, 1, 2, 4, 4, 5, 5, 6, 6 };    int n = sizeof(arr) / sizeof(arr); // find size of the array    search_single(arr, n);    return 0;}`

Output

`The single occurring element is 2`

C code

`#include <stdio.h>void search_single(int arr[], int n) // function to check the single occuring element{    int ans = 0;    for (int i = 0; i < n; i++) {        ans = ans ^ arr[i];    } printf( "The single occurring element is %d",ans); // print ans}int main(){    int arr[] = { 1, 1, 2, 4, 4, 5, 5, 6, 6 };    int n = sizeof(arr) / sizeof(arr); // find size of the array    search_single(arr, n);    return 0;}`

Output

`The single occurring element is 2`

TIme complexity - O(n)

Space complexity - O(1)

### Efficient approach

The use of binary search makes the solution more optimised.

Approach

All elements before the required have the first occurrence at even index (0, 2, ..) and the next occurrence at odd index (1, 3, ...). And all elements after the required elements have the first occurrence at an odd index and the next occurrence at an even index.

1) Find the middle index, say 'mid'.

2) If 'mid' is even, then compare arr[mid] and arr[mid + 1]. If both are the same, then put required element after 'mid' else before mid.

3) If 'mid' is odd, then compare arr[mid] and arr[mid - 1]. If both are the same, then put the required element after 'mid' and else before mid.

C++ code

`#include <iostream>using namespace std;void search(int arr[], int low, int high) // binary serach implementation{          // Base cases          if (low > high)                   return;          if (low == high) {                   cout << "The element occuring once is  " << arr[low]; // if the element is found that is occuring once                   return;          }          int mid = (low + high) / 2; // find the mid range          // If mid is even and element next to mid is          // same as mid, then output element lies on          // right side, else on left side          if (mid % 2 == 0) {                   if (arr[mid] == arr[mid + 1])                             search(arr, mid + 2, high);                   else                             search(arr, low, mid);          }          // If mid is odd          else {                   if (arr[mid] == arr[mid - 1])                             search(arr, mid + 1, high);                   else                             search(arr, low, mid - 1);          }}int main(){          int arr[] = { 1, 1, 2, 4, 4, 5, 5, 6, 6 };          int len = sizeof(arr) / sizeof(arr);          search(arr, 0, len - 1);          return 0;}`

Output

`The element occurring once is 2`

C code

`#include <stdio.h>void search(int arr[], int low, int high) // binary search implementation{          // Base cases          if (low > high)                   return;          if (low == high) {                   printf( "The element occurring once is  %d", arr[low]); // if the element is found that is occurring once                   return;          }          int mid = (low + high) / 2; // find the mid range          // If mid is even and element next to mid is          // same as mid, then output element lies on          // right side, else on left side          if (mid % 2 == 0) {                   if (arr[mid] == arr[mid + 1])                             search(arr, mid + 2, high);                   else                             search(arr, low, mid);          }          // If mid is odd          else {                   if (arr[mid] == arr[mid - 1])                             search(arr, mid + 1, high);                   else                             search(arr, low, mid - 1);          }}int main(){          int arr[] = { 1, 1, 2, 4, 4, 5, 5, 6, 6 };          int len = sizeof(arr) / sizeof(arr);          search(arr, 0, len - 1);          return 0;}`

Output

`The element occurring once is 2`

Time complexity - (log n)