Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

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

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

  1. 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.
  2. 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);
    }
}

Solve Single Number II online · All practice problems