Find the K-or of an Array - Solution & Explanation

Problem Overview: You receive an integer array nums and an integer k. The K-or value is constructed bit by bit: a bit i is set in the result if at least k numbers in the array have that bit set. The task is to efficiently compute this resulting integer.

Approach 1: Bit Counting (O(n * 32) time, O(1) space)

This method scans each bit position independently. For every bit from 0 to 31, iterate through the array and count how many numbers have that bit set using (num >> bit) & 1. If the count reaches at least k, set that bit in the final result using result |= (1 << bit). The key insight is that the K-or condition depends only on how many elements contain a bit, not their order or magnitude. Since integers typically have 32 bits, the outer loop runs 32 times and the inner loop scans n elements, giving O(n * 32) time with constant space.

This technique is common in problems involving bit manipulation because it decomposes the integer into independent bit positions. It works well when the bit width is small and fixed, which keeps the complexity effectively linear in the size of the array.

Approach 2: Frequency Array for Bit Counting (O(n * 32) time, O(32) space)

This variation separates counting from result construction. First create a frequency array of size 32 where freq[i] stores how many numbers contain bit i. Iterate through each element in nums, check all 32 bits, and increment the corresponding counter when a bit is set. After processing the array, build the final integer by checking each frequency entry. If freq[i] >= k, set bit i in the result.

The advantage of this structure is clarity and reuse. If additional queries depend on bit frequencies, the counts are already available. The memory cost is still tiny because the frequency array has a fixed size of 32. This pattern often appears in array problems that combine counting with bitwise operations.

Recommended for interviews: The direct bit counting approach is what most interviewers expect. It shows you understand how to inspect and manipulate bits efficiently and avoids unnecessary data structures. The frequency array version demonstrates the same idea but organizes the computation differently. Both achieve the optimal O(n) effective complexity since the bit width is constant.