Introduction

A common interview variant says that every element in an array appears exactly k times except one element, which appears b times, where 0 < b < k. The efficient solution does not need a hash map if you are working with integers: you can count bits position by position and use modular arithmetic to reconstruct the special value.

Why Bit Counting Works

If every ordinary value appears k times, then for any fixed bit position its total contribution is a multiple of k. The exceptional element contributes that bit either:

• '0 * b if the bit is not set'
• '1 * b if the bit is set'

So after summing all bits at one position, taking the result modulo k reveals whether the exceptional element has that bit set.

For the simplest and most common case, where one element appears once and all others appear three times, the remainder is either 0 or 1. The generalized case uses b instead of 1.

Example

Suppose k = 3 and b = 1.

Array:

[6, 2, 2, 2, 6, 6, 13]

All values except 13 appear three times. If you count each bit column across the whole array and reduce modulo 3, the repeated values cancel out and the remaining pattern is the binary form of 13.

Python Implementation

1def find_special(nums, k, b, bits=32):
2    result = 0
3
4    for bit in range(bits):
5        count = 0
6        for num in nums:
7            if (num >> bit) & 1:
8                count += 1
9
10        remainder = count % k
11        if remainder == b:
12            result |= (1 << bit)
13
14    return result
15
16
17nums = [6, 2, 2, 2, 6, 6, 13]
18print(find_special(nums, k=3, b=1))

This prints 13.

How The Generalization Uses b

If the unique element appears b times rather than once, the remainder for a set bit becomes b modulo k. That is why the reconstruction step compares count % k with b.

This assumes:

• every other element appears exactly k times
• there is exactly one special element with multiplicity b
• '0 < b < k'

If those assumptions are broken, the bit trick no longer guarantees a correct answer.

Space And Time Complexity

The algorithm runs in O(bits * n) time, where bits is the integer width you inspect and n is the number of elements. For fixed-width integers such as 32-bit or 64-bit values, that is effectively linear in the array size. Extra space is O(1).

A hash map solution is also linear in time on average, but it uses extra memory proportional to the number of distinct elements.

Negative Numbers Need Care

With negative integers, the sign bit needs special handling because Python integers are not fixed-width in the same way as C integers. One practical approach is to choose a fixed width such as 32 bits and convert the result back if the sign bit is set.

1def find_special_32bit(nums, k, b):
2    result = find_special(nums, k, b, bits=32)
3    if result >= 2 ** 31:
4        result -= 2 ** 32
5    return result

That keeps the logic aligned with fixed-width two’s-complement arithmetic.

Common Pitfalls

The most common mistake is using the bit-count method when the problem statement does not actually guarantee that every other element appears exactly k times. The cancellation argument depends completely on that condition.

Another mistake is hard-coding the remainder check for the case b = 1 and then claiming the solution is general. For the generalized problem, compare the remainder with b.

A third issue is ignoring negative integers. If signed values are possible, define the bit width explicitly.

Summary

• Bit counting works because elements that appear k times cancel out modulo k.
• The special element is reconstructed from bit positions whose remainder equals b.
• The method runs in linear time with constant extra space for fixed-width integers.
• It is more memory-efficient than a hash map when the input meets the exact frequency constraint.
• Handle negative numbers carefully by choosing a fixed integer width.