Problem Statement: Given a sorted array of N integers, where every element except one appears exactly twice and one element appears only once. Search Single Element in a sorted array.
Example 1:
Input: N = 9, array[] = {1,1,2,3,3,4,4,8,8}
Output: 2
Explanation: Every element in this sorted array except 2
appears twice, therefore the answer returned will be 2.
Example 2:
Input: N = 7, array[] = {11,22,22,34,34,57,57}
Output: 11
Explanation: Every element in this sorted array except
11 appears twice, therefore the answer returned will be 11.
Solution
Disclaimer: Don’t jump directly to the solution, try it out yourself first.
Solution 1: Using XOR(^)
Approach: As every number in the array repeats twice and only one number occurs once, we can take advantage of the XOR(^) operator. These are two properties of the XOR operator which will be helpful.
If p is a number then,
p^p=0
p^0=p
If we find the XOR of every element of the array, we will get the answer.
Code:
C++ Code
#include<bits/stdc++.h>
using namespace std;
class Solution {
public:
int findSingleElement(vector < int > & nums) {
int n = nums.size();
int elem = 0;
for (int i = 0; i < n; i++) {
elem = elem ^ nums[i];
}
return elem;
}
};
int main() {
Solution obj;
vector < int > v {1,1,2,3,3,4,4,8,8};
int elem = obj.findSingleElement(v);
cout << "The single occurring element is "
<< elem << endl;
}Output:
The single occurring element is 2
Time Complexity: O(N)
Space Complexity: O(1)
Java Code
import java.util.*;
class TUF {
public static int findSingleElement(int nums[]) {
int n = nums.length;
int elem = 0;
for (int i = 0; i < n; i++) {
elem = elem ^ nums[i];
}
return elem;
}
public static void main(String args[]) {
int arr[] = {1,1,2,3,3,4,4,8,8};
int elem = findSingleElement(arr);
System.out.println("The single occurring"
+" element is " + elem);
}
}Output:
The single occurring element is 2
Time Complexity: O(N)
Space Complexity: O(1)
Python Code
from typing import List
class Solution:
def findSingleElement(self, nums: List[int]) -> int:
elem = 0
for num in nums:
elem = elem ^ num
return elem
if __name__ == "__main__":
v = [1, 1, 2, 3, 3, 4, 4, 8, 8]
obj = Solution()
elem = obj.findSingleElement(v)
print("The single occurring element is ", elem)Output:
The single occurring element is 2
Time Complexity: O(N)
Space Complexity: O(1)
Solution 2:
Approach: Using Binary Search
As the elements are sorted, twice-occurring elements will be placed together in the input array. Moreover, the input array has one element occurring once, therefore a general input can be thought of like this.
Now in this left array, the first instance of every element is occurring on the even index and the second instance on the odd index. Similarly in the right array, the first instance of every element is occurring on the odd index and the second index is occurring on the even index. This is summarized below.
So the algorithmic approach will be to use binary search. The intuition is that when we see an element, if we know its index and whether it is the first instance or the second instance, we can decide whether we are presently in the left array or right array. Moreover, we can decide which direction we need to move to find the breakpoint. We need to find this breakpoint between our left array and the right array.
We will check our mid element, if it is in the left array, we will shrink our left array to the right of this mid element, if it is in the right array, we will shrink the right array to the left of this mid element. This binary search process will continue till the right array surpasses our left one and the low is pointing towards the breakpoint.
Dry Run: In case you want to see the dry run of this approach, please watch the video at the bottom.
Code:
C++ Code
#include<bits/stdc++.h>
using namespace std;
class Solution {
public:
int findSingleElement(vector < int > & nums)
{
int low = 0;
int high = n - 2;
while (low <= high) {
int mid = (low + high) / 2;
if (mid % 2 == 0) {
if (nums[mid] != nums[mid + 1])
//Checking whether we are in right half
high = mid - 1; //Shrinking the right half
else
low = mid + 1; //Shrinking the left half
} else {
//Checking whether we are in right half
if (nums[mid] == nums[mid + 1])
high = mid - 1; //Shrinking the right half
else
low = mid + 1; //Shrinking the left half
}
}
return nums[low];
}
};
int main() {
Solution obj;
vector < int > v {1,1,2,3,3,4,4,8,8
};
int elem = obj.findSingleElement(v);
cout << "The single occurring element is " +
" << elem << endl;
}Output:
The single occurring element is 2
Time Complexity: O(log(N))
Space Complexity: O(1)
Java Code
import java.util.*;
class TUF {
static int findSingleElement(int nums[]) {
int low = 0;
int high = nums.length - 2;
while (low <= high) {
int mid = (low + high) / 2;
if (mid % 2 == 0) {
// Checking whether we are in right half
if (nums[mid] != nums[mid + 1])
//Shrinking the right half
high = mid - 1;
else
// Shrinking the left half
low = mid + 1;
} else {
// Checking whether we are in right half
if (nums[mid] == nums[mid + 1])
//Shrinking the right half
high = mid - 1;
else
// Shrinking the left half
low = mid + 1;
}
}
return nums[low];
}
public static void main(String args[]) {
int arr[] = {1,1,2,3,3,4,4,8,8};
int elem = findSingleElement(arr);
System.out.println("The single occurring" +
" element is " + elem);
}
}Output:
The single occurring element is 2
Time Complexity: O(log(N))
Space Complexity: O(1)
Python Code
from typing import List
class Solution:
def findSingleElement(self, nums: List[int]) -> int:
low = 0
high = len(nums) - 2
while low <= high:
mid = (low + high) // 2
if mid % 2 == 0:
if nums[mid] != nums[mid + 1]:
# Checking whether we are in right half
high = mid - 1 # Shrinking the right half
else:
low = mid + 1 # Shrinking the left half
else:
# Checking whether we are in right half
if nums[mid] == nums[mid + 1]:
high = mid - 1 # Shrinking the right half
else:
low = mid + 1 # Shrinking the left half
return nums[low]
if __name__ == "__main__":
nums = [1, 1, 2, 3, 3, 4, 4, 8, 8]
obj = Solution()
elem = obj.findSingleElement(nums)
print(f"The single occurring element is {elem}")Output:
The single occurring element is 2
Time Complexity: O(log(N))
Space Complexity: O(1)
Special thanks to Anshuman Sharma and Sudip Ghosh for contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam, please check out this article