Practice › Bit Manipulation
Single Number II
Medium · Bit Manipulation · Asked at Amazon, Google, Microsoft, Adobe
Every value appears exactly three times except one value that appears once. Print that value, using O(1) extra space.
Input
First line: n. Second line: n space-separated integers.
Output
The single value.
Constraints
- 1 ≤ n ≤ 3 · 10^4
- -2^31 ≤ a[i] ≤ 2^31 − 1
For each of the 32 bit positions, count how many numbers have that bit set. Counts that are not a multiple of 3 come from the single number.
Example 1
Input
4 2 2 3 2
Output
3
Example 2
Input
7 0 1 0 1 0 1 99
Output
99
Hints
- Look at one bit position at a time: the numbers that appear three times contribute a multiple of 3 to the count of 1s at that position.
- So the single number has bit i set exactly when the count of 1s at bit i is not divisible by 3.
Approach
For each of the 32 bit positions, count how many array elements have that bit set; take the count modulo 3 and set that bit of the answer if the remainder is 1. Work with 32-bit two's-complement so negative numbers come out correctly (in Python, convert bit 31 back to a negative value at the end).
Complexity: O(32 · n) time · O(1) space
Solution
C++ solution
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
vector<long long> a(n);
for (auto &x : a) cin >> x;
uint32_t ans = 0;
for (int b = 0; b < 32; b++) {
int cnt = 0;
for (long long x : a) cnt += ((uint32_t)x >> b) & 1;
if (cnt % 3) ans |= 1u << b;
}
cout << (int32_t)ans << "\n";
return 0;
}Python solution
import sys
data = list(map(int, sys.stdin.read().split()))
a = data[1 : 1 + data[0]]
ans = 0
for b in range(32):
cnt = sum((x >> b) & 1 for x in a) # works for negatives: Python shifts keep the sign bits
if cnt % 3:
ans |= 1 << b
if ans >= 2**31:
ans -= 2**32
print(ans)Java solution
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] a = new int[n];
for (int i = 0; i < n; i++) a[i] = (int) sc.nextLong();
int ans = 0;
for (int b = 0; b < 32; b++) {
int cnt = 0;
for (int x : a) cnt += (x >>> b) & 1;
if (cnt % 3 != 0) ans |= 1 << b;
}
System.out.println(ans);
}
}