Find the K-or of an Array

Find the K-or of an Array

What is this problem about?

The Find the K-or of an Array interview question is a bit manipulation challenge. You are given an array of non-negative integers and a threshold k. The "K-or" of an array is a value whose $i^{th}$ bit is set if and only if at least k elements in the array have their $i^{th}$ bit set. Your goal is to compute this K-or value.

Why is this asked in interviews?

Amazon and other tech firms use the Find the K-or of an Array coding problem to assess a candidate's understanding of Bit Manipulation interview patterns. It tests whether you can process numbers at the bit level and if you can use bitwise operators (like shifts and masks) to extract information. It’s a test of efficiency and low-level data handling.

Algorithmic pattern used

This problem follows the Bit Counting pattern.

1. Iterate Bits: Iterate through all possible bit positions (usually 0 to 30 for non-negative integers).
2. Count Set Bits: For each bit position $i$, iterate through the array and count how many numbers have the $i^{th}$ bit set ((num >> i) & 1).
3. Construct Result: If the count is $\geq k$, set the $i^{th}$ bit in the result variable (result |= (1 << i)).
4. Efficiency: The time complexity is $O(N imes 31)$, which is effectively linear relative to the number of elements.

Example explanation

Array: [7, 12, 9, 8, 9, 15], $k = 4$

• Bit 0: 7 (yes), 12 (no), 9 (yes), 8 (no), 9 (yes), 15 (yes). Count = 4. Set bit 0.
• Bit 1: 7 (yes), 12 (no), 9 (no), 8 (no), 9 (no), 15 (yes). Count = 2. Skip.
• Bit 2: 7 (yes), 12 (yes), 9 (no), 8 (no), 9 (no), 15 (yes). Count = 3. Skip.
• Bit 3: 7 (no), 12 (yes), 9 (yes), 8 (yes), 9 (yes), 15 (yes). Count = 5. Set bit 3. Result: $2^3 + 2^0 = 9$.

Common mistakes candidates make

• Wrong Bit Range: Forgetting to check up to 31 bits, which might miss larger values.
• Inefficient Counting: Using string conversion to check bits instead of bitwise shifts.
• Operator Confusion: Confusing bitwise OR (|) with the custom "K-or" logic.

Interview preparation tip

Practice using (1 << i) to create bitmasks and >> to inspect specific bits. These two operations are the building blocks for almost every bitwise problem you'll encounter in a technical interview.