Finding the element that appears only once in an array where all other elements appear twice is a common problem in coding interviews and programming challenges. In this article, we'll discuss four approaches to solve this problem: one using a brute force approach, another using hashing, a third using a map, and the optimal approach using XOR.
Solution 1: Brute Force Approach (using Nested Loop)
This method involves using a nested loop to find the element that appears only once.
Implementation:
int getSingleElement(vector<int> &arr, int n)
{
for (int i = 0; i < n; i++)
{
int num = arr[i];
int counter = 0;
for (int j = 0; j < n; j++)
{
if (arr[j] == num)
{
counter++;
}
}
if (counter == 1)
{
return num;
}
}
return -1;
}
Logic:
Nested Loop:
Check for Single Occurrence:
- If the count of the selected element is
1, return that element.
Time Complexity: O(n*n)
- Explanation: Each element in the array is compared with every other element, resulting in a nested loop.
Space Complexity: O(1)
- Explanation: No additional space is used apart from variables for counting.
Example:
Input: arr = [4, 3, 2, 4, 1, 3, 2]
Output: 1
Explanation: The element 1 appears only once in the array.
Solution 2: Better Approach (using Hashing)
This method uses hashing to find the element that appears only once.
Implementation:
int getSingleElement(vector<int> &arr, int n)
{
int maxElement = arr[0];
for (int i = 0; i < n; i++)
{
if (arr[i] > maxElement)
{
maxElement = arr[i];
}
}
vector<int> hash(maxElement + 1, 0);
for (int i = 0; i < n; i++)
{
hash[arr[i]]++;
}
for (int i = 0; i < n; i++)
{
if (hash[arr[i]] == 1)
{
return arr[i];
}
}
return -1;
}
Logic:
Find Maximum Element:
- Traverse the array to find the maximum element.
Hash the Array:
- Create a hash array of size
maxElement + 1 and count the occurrences of each element. maxElement is the maximum element in the array.
Check for Single Occurrence:
- Traverse the hash array to find the element with a count of
1.
Time Complexity: O(3n) ~ O(n)
- Explanation: The array is traversed three times (to find the maximum element, hash the array, and find the single element).
Space Complexity: O(maxElement+1)
- Explanation: Additional space is used for the hash array. Here,
maxElement is the maximum element in the array.
Example:
Input: arr = [4, 3, 2, 4, 1, 3, 2]
Output: 1
Explanation: The element 1 appears only once in the array.
Solution 3: Better Approach (using Map for Hashing)
This method uses a map to find the element that appears only once.
Implementation:
int getSingleElement(vector<int> &arr, int n)
{
map<int, int> track;
for (int i = 0; i < n; i++)
{
track[arr[i]]++;
}
for (auto it : track)
{
if (it.second == 1)
{
return it.first;
}
}
return -1;
}
Logic:
Hash the Array:
- Use a map to count the occurrences of each element.
Check for Single Occurrence:
- Traverse the map to find the element with a count of
1.
Time Complexity: O(n * log M) + O(M)
- Explanation: The array is hashed in O(n * log M) time and then traversed in O(M) time. Here, M is the size of the map (in this case, M = (n/2)+1) and n = size of the array. Note: [ It takes O(log M) time to access an element in the map ]
Space Complexity: O(M)
- Explanation: Additional space is used for the map. Here, M is the size of the map (in this case, M = (n/2)+1) and n = size of the array.
Example:
Input: arr = [4, 3, 2, 4, 1, 3, 2]
Output: 1
Explanation: The element 1 appears only once in the array.
Solution 4: Optimal Approach (using XOR)
This method uses XOR to find the element that appears only once.
Implementation:
int getSingleElement(vector<int> &arr, int n)
{
int appearsOnce = 0;
for (int i = 0; i < n; i++)
{
appearsOnce ^= arr[i];
}
return appearsOnce;
}
Logic:
XOR All Elements:
XOR all the elements of the array. The elements appearing twice will cancel out, leaving the element that appears once.
This approach leverages the property a ^ a = 0 and a ^ 0 = a.
Time Complexity: O(n)
- Explanation: The array is traversed once.
Space Complexity: O(1)
- Explanation: No additional space is used.
Example:
Input: arr = [4, 3, 2, 4, 1, 3, 2]
Output: 1
Explanation: The element 1 appears only once in the array.
Comparison
Brute Force Approach:
Better Approach (using Hashing):
Better Approach (using Map for Hashing):
Optimal Approach (using XOR):
Edge Cases
Empty Array: Returns -1 as there are no elements to check.
No Single Element: Returns -1 if no element appears exactly once.
All Elements are the Same: Returns -1 if no unique element exists.
Additional Notes
Efficiency: The XOR technique is the most time-efficient and space-efficient, making it preferable for large arrays.
Practicality: The choice of approach depends on the specific constraints and requirements of the problem, such as array size and available memory.
Conclusion
Finding the element that appears once in an array where all other elements appear twice can be efficiently achieved using various approaches. The optimal choice depends on the specific constraints and requirements of the problem, with the XOR method being the most efficient in terms of both time and space.
