Practice › Arrays
Single Number
Easy · Arrays · Asked at Amazon, Google, TCS
Every element appears twice except one. Find that single element.
Input
First line: n. Second line: n space-separated integers.
Output
The element that appears once.
Constraints
- 1 ≤ n < 10^5, n is odd
- -10^9 ≤ a[i] ≤ 10^9
XOR of all elements gives the answer in O(1) extra space (x ^ x = 0).
Example 1
Input
3 2 2 1
Output
1
Example 2
Input
5 4 1 2 1 2
Output
4
Hints
- What is x ^ x? And x ^ 0?
- XOR all the numbers: every pair cancels out, leaving the single one.
Approach
XOR is commutative and x ^ x = 0, x ^ 0 = x. XOR-ing the whole array cancels every value that appears twice and leaves only the unique value. This works for negative numbers too, since XOR acts on the bit pattern.
Complexity: O(n) time · O(1) space
Solution
C++ solution
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
long long result = 0, x;
for (int i = 0; i < n; i++) {
cin >> x;
result ^= x;
}
cout << result << "\n";
return 0;
}Python solution
import sys
data = list(map(int, sys.stdin.read().split()))
result = 0
for x in data[1 : data[0] + 1]:
result ^= x
print(result)Java solution
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
long result = 0;
for (int i = 0; i < n; i++) result ^= sc.nextLong();
System.out.println(result);
}
}