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 code
int main()
{
int arr[] = { 1, 1, 2, 4, 4, 5, 5, 6, 6 };
int n = sizeof(arr) / sizeof(arr[0]); // 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[0]); // 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[0]); // 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[0]); // 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[0]);
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[0]);
search(arr, 0, len - 1);
return 0;
}
Output
The element occurring once is 2
Time complexity - (log n)