Unique Element Finder — Problem Statement & Solution Guide
Problem Description
You are given an integer array nums that may be empty. Exactly one value in the array can appear a single time while every other value appears an even number of times (including zero). Return that solitary value. If the array contains no such value, return -1. Your solution must run in linear time and use only constant extra space.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Unique Element Finder"
WHY DOES IT MATTER?
This pattern is essential for understanding how bitwise operations can replace data structures to solve counting problems. It demonstrates that not all 'counting' problems require storage; algebraic properties of operations can achieve the same result with minimal resources, a critical skill for optimizing memory in high-frequency trading or embedded systems.
OPTIMIZATION CHALLENGE
The key insight is recognizing that 'finding the element that appears once while others appear twice' is mathematically equivalent to summing all elements in a field where addition is XOR. This transforms a search/counting problem into a reduction problem, eliminating the need for state storage (hash maps).
REAL-WORLD CONNECTION
This is analogous to error detection in data transmission. In networking protocols like Ethernet or Wi-Fi, XOR-based checksums (like CRC) are used to detect if data has been corrupted. If a bit flips, the XOR sum changes. Similarly, here we use XOR to 'cancel out' known noise (pairs of numbers) to isolate the signal (the unique number).
In an interview, do not just write the code. Explicitly state the three properties of XOR (commutativity, associativity, and self-inverse) that make this solution valid. This shows deep theoretical understanding rather than just pattern matching.
COMPLEXITY AT A GLANCE
O(n)O(1)Core Theory — Why This Approach?
The problem constraints of linear time O(n) and constant extra space O(1) immediately rule out standard hashing approaches, which require O(n) space to store frequency counts. The theoretical foundation for this problem relies on the properties of the bitwise XOR (exclusive OR) operation. XOR is commutative and associative, meaning the order of operations does not matter (a ^ b = b ^ a) and grouping does not change the result ((a ^ b) ^ c = a ^ (b ^ c)). Most critically, any number XORed with itself results in zero (a ^ a = 0), and any number XORed with zero remains unchanged (a ^ 0 = a). These properties allow us to cancel out pairs of identical numbers, leaving only the unique element.
Interview Questions on This Problem
Q1How would you adapt this solution if there were two unique elements instead of one, while maintaining O(1) space?
First, XOR all numbers to get the combined XOR of the two unique elements (let's call it x). Find the rightmost set bit in x (this bit differs between the two unique numbers). Partition the array into two groups based on this bit: numbers with the bit set and numbers with the bit unset. XOR each group separately; the results will be the two unique numbers.
Q2Why can't we use a frequency map (hash map) for this specific problem statement?
While a frequency map solves the problem in O(n) time, it requires O(n) auxiliary space to store the counts for each distinct element. The problem explicitly demands constant extra space, making the XOR approach the only viable optimal solution for large datasets where memory is a constraint.
Q3What happens if the array is empty or contains only one element? How does your solution handle these edge cases?
If the array is empty, the XOR of an empty set is 0. However, the problem states 'exactly one value... appears a single time' or return -1 if no such value exists. If the array is empty, there is no unique value, so we return -1. If the array has one element, XORing it with 0 yields the element itself, which is correct. The logic must explicitly check for the empty array case to return -1 as per the problem statement.
Examples
Input
[4,1,2,1,2]
Output
4
Explanation: The frequencies are: 4→1, 1→2, 2→2. Only 4 occurs once, so the answer is 4.
Input
[]
Output
-1
Explanation: The array is empty, therefore there is no element that occurs exactly once; the prescribed sentinel value is -1.
Input
[7,7,3,7,7]
Output
3
Explanation: Counts: 7 appears four times (an even count) and 3 appears once. Hence the unique element is 3.
Constraints
- 1 <= nums.length <= 100000
- -1000000000 <= nums[i] <= 1000000000
- All numbers except possibly one occur an even number of times
Optimal Approach & Strategy
Initialize a variable to 0 and iterate through the array, XORing each element with the variable. After the loop, the variable holds the unique element, or 0 if the array was empty (which we handle by returning -1). This approach runs in O(n) time and O(1) space.
Brute Force Approach
Iterate through the array and for each element, count its occurrences by scanning the rest of the array. Return the element with a count of 1, or -1 if none exists. This approach takes O(n^2) time due to the nested loops.
Verified Code Solutions
function findUnique(nums) {
let xor = 0;
for (const v of nums) xor ^= v;
if (xor === 0) {
const freq = new Map();
for (const v of nums) freq.set(v, (freq.get(v) || 0) + 1);
for (const [k, v] of freq) if (v === 1) return k;
return -1;
}
return xor;
}
function main() {
const fs = require('fs');
const data = fs.readFileSync(0, 'utf8').trim().split(/\s+/).map(Number);
if (data.length === 0) return;
const n = data[0];
const nums = data.slice(1, 1 + n);
console.log(findUnique(nums));
}
main();#include <bits/stdc++.h>
using namespace std;
int findUnique(const vector<int>& nums) {
int xorSum = 0;
for (int v : nums) xorSum ^= v;
// If xorSum is 0, either no unique element or the unique element is 0 with even count.
// According to problem, return -1 when no solitary value exists.
// We need to verify that xorSum actually appears once.
if (xorSum == 0) {
// Check if there is any element that appears once.
unordered_map<int,int> freq;
for (int v : nums) ++freq[v];
for (auto &p : freq) if (p.second == 1) return p.first;
return -1;
}
return xorSum;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
if(!(cin>>n)) return 0;
vector<int> nums(n);
for(int i=0;i<n;++i) cin>>nums[i];
cout<<findUnique(nums);
return 0;
}import java.io.*;
import java.util.*;
public class Main {
public static int findUnique(int[] nums) {
int xor = 0;
for (int v : nums) xor ^= v;
if (xor == 0) {
Map<Integer, Integer> freq = new HashMap<>();
for (int v : nums) freq.put(v, freq.getOrDefault(v, 0) + 1);
for (Map.Entry<Integer, Integer> e : freq.entrySet()) {
if (e.getValue() == 1) return e.getKey();
}
return -1;
}
return xor;
}
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String line = br.readLine();
if (line == null || line.isEmpty()) return;
int n = Integer.parseInt(line.trim());
int[] nums = new int[n];
StringTokenizer st = new StringTokenizer(br.readLine());
for (int i = 0; i < n; i++) {
nums[i] = Integer.parseInt(st.nextToken());
}
System.out.println(findUnique(nums));
}
}def find_unique(nums):
xor = 0
for v in nums:
xor ^= v
if xor == 0:
from collections import Counter
cnt = Counter(nums)
for k, v in cnt.items():
if v == 1:
return k
return -1
return xor
if __name__ == "__main__":
import sys
data = list(map(int, sys.stdin.read().strip().split()))
if not data:
sys.exit()
n = data[0]
nums = data[1:1+n]
print(find_unique(nums))function findUnique(nums) {
let xor = 0;
for (const v of nums) xor ^= v;
if (xor === 0) {
const freq = new Map();
for (const v of nums) freq.set(v, (freq.get(v) || 0) + 1);
for (const [k, v] of freq) if (v === 1) return k;
return -1;
}
return xor;
}
function main() {
const fs = require('fs');
const data = fs.readFileSync(0, 'utf8').trim().split(/\s+/).map(Number);
if (data.length === 0) return;
const n = data[0];
const nums = data.slice(1, 1 + n);
console.log(findUnique(nums));
}
main();Asked in Top Tech Interviews
Solve in Interative Editor
Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.