Difficulty: 🟢 Easy
Topics: Array, Bit Manipulation

Solution

LeetCode 2917 - Find the K-or of an Array

Problem Understanding

This problem introduces a generalized version of the bitwise OR operation called the K-or.

In a normal bitwise OR, a bit in the result becomes 1 if at least one number has that bit set. The K-or operation changes this rule. Instead of requiring one occurrence, a bit position becomes 1 only if at least k numbers in the array have that bit set.

The input consists of:

An integer array nums
An integer k

For every bit position, we need to count how many numbers contain a 1 at that position. If that count is greater than or equal to k, then the corresponding bit in the answer should be set to 1.

The output is a single integer representing the K-or of the array.

The constraints are relatively small:

1 <= nums.length <= 50
0 <= nums[i] < 2^31
1 <= k <= nums.length

Since every number fits within 31 bits, there are only 31 possible bit positions that matter. Even if we inspect every bit of every number, the total work remains very small.

Several edge cases are worth noting:

When k = 1, every bit that appears in at least one number should be included, making the answer equivalent to the standard bitwise OR.
When k = nums.length, a bit must appear in every number to be included in the result.
Arrays containing only zeros should always produce 0.
A bit may appear many times across the array, but only counts matter, not which specific numbers contain it.

Approaches

Brute Force Approach

A straightforward approach is to examine every possible bit position and count how many numbers have that bit set.

For each bit from 0 to 30:

Iterate through the entire array.
Check whether the current bit is set in each number.
Count the occurrences.
If the count is at least k, set that bit in the answer.

This approach is guaranteed to be correct because the K-or definition is entirely based on the frequency of set bits at each position.

Although this is already efficient for the given constraints, it can still be viewed as a brute-force solution because it explicitly examines every bit of every number.

Key Insight

The K-or operation is completely independent for each bit position.

Whether bit 5 belongs in the answer has no effect on bit 10, and vice versa. Therefore, we can process each bit separately.

Since all values are less than 2^31, there are only 31 relevant bit positions. We simply count how many numbers contain each bit and reconstruct the result from the positions whose counts reach at least k.

This gives a very efficient solution whose running time is proportional to:

Number of bits (31)
Number of elements (n)

Since both are small, the solution is extremely fast.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(31 × n)	O(1)	Count occurrences of every bit position independently
Optimal	O(31 × n)	O(1)	Uses the independence of bit positions to build the result directly

Because the maximum bit width is fixed at 31, both approaches have the same asymptotic complexity. The optimal solution is essentially the cleanest direct implementation of the bit-counting observation.

Algorithm Walkthrough

Initialize answer = 0.
Iterate through every bit position from 0 to 30.
For the current bit position, initialize a counter to 0.
Traverse every number in nums.
Check whether the current bit is set using:

(num >> bit) & 1

If the result is 1, increment the counter. 6. After processing all numbers, determine whether the counter is at least k. 7. If the counter is greater than or equal to k, set that bit in the answer:

answer |= (1 << bit)

Continue until all 31 bit positions have been processed.
Return the final value of answer.

Why it works

The K-or definition treats each bit position independently. For any bit position b, the result should contain a 1 exactly when at least k numbers have bit b set. The algorithm explicitly counts these occurrences for every bit position and sets the corresponding bit in the answer if and only if the count reaches k. Therefore every bit in the constructed result matches the K-or definition, guaranteeing correctness.

Python Solution

from typing import List

class Solution:
    def findKOr(self, nums: List[int], k: int) -> int:
        answer = 0

        for bit in range(31):
            count = 0

            for num in nums:
                if (num >> bit) & 1:
                    count += 1

            if count >= k:
                answer |= (1 << bit)

        return answer

The implementation starts by creating an accumulator named answer.

The outer loop iterates through all 31 possible bit positions because every number is smaller than 2^31.

For each bit, the inner loop scans all numbers and counts how many contain that bit. The expression (num >> bit) & 1 isolates the desired bit and returns either 0 or 1.

After the count is computed, the algorithm checks whether it satisfies the K-or requirement. If at least k numbers contain that bit, the bit is added to the answer using bitwise OR.

After all bit positions have been processed, the completed result is returned.

Go Solution

func findKOr(nums []int, k int) int {
    answer := 0

    for bit := 0; bit < 31; bit++ {
        count := 0

        for _, num := range nums {
            if ((num >> bit) & 1) == 1 {
                count++
            }
        }

        if count >= k {
            answer |= (1 << bit)
        }
    }

    return answer
}

The Go implementation follows exactly the same logic as the Python version.

The primary difference is syntax. Go uses a range loop to iterate through the slice and integer bit operations work directly on the built-in int type. Since all values are below 2^31, there are no overflow concerns when checking bits 0 through 30.

Worked Examples

Example 1

Input

nums = [7,12,9,8,9,15]
k = 4

Binary representations:

Number	Bit 3	Bit 2	Bit 1	Bit 0
7	0	1	1	1
12	1	1	0	0
9	1	0	0	1
8	1	0	0	0
9	1	0	0	1
15	1	1	1	1

Count each bit:

Bit	Count of 1s	Count ≥ 4?	Result Bit
0	4	Yes	1
1	2	No	0
2	3	No	0
3	5	Yes	1

Result bits:

1001₂

Decimal value:

Example 2

Input

nums = [2,12,1,11,4,5]
k = 6

Every bit position must appear in all six numbers.

Bit	Count
0	4
1	2
2	3
3	2

No count reaches 6.

Therefore:

answer = 0

Example 3

Input

nums = [10,8,5,9,11,6,8]
k = 1

Since k = 1, any bit appearing at least once qualifies.

Bit	Appears?	Result Bit
0	Yes	1
1	Yes	1
2	Yes	1
3	Yes	1

Result:

1111₂ = 15

Complexity Analysis

Measure	Complexity	Explanation
Time	O(31 × n)	For each of 31 bit positions, scan all n numbers
Space	O(1)	Only a few integer variables are used

Since 31 is a fixed constant, the running time can also be viewed as O(n). The algorithm requires no auxiliary data structures whose size depends on the input, so the space complexity remains constant.

Test Cases

from typing import List

s = Solution()

assert s.findKOr([7, 12, 9, 8, 9, 15], 4) == 9      # Example 1
assert s.findKOr([2, 12, 1, 11, 4, 5], 6) == 0      # Example 2
assert s.findKOr([10, 8, 5, 9, 11, 6, 8], 1) == 15  # Example 3

assert s.findKOr([0], 1) == 0                        # Single zero
assert s.findKOr([1], 1) == 1                        # Single nonzero value
assert s.findKOr([0, 0, 0], 2) == 0                  # All zeros

assert s.findKOr([7, 7, 7], 3) == 7                  # Every bit appears in all numbers
assert s.findKOr([7, 7, 7], 1) == 7                  # Equivalent to standard OR

assert s.findKOr([1, 2, 4, 8], 2) == 0              # No bit appears twice
assert s.findKOr([3, 3, 1], 2) == 3                 # Multiple qualifying bits

assert s.findKOr([1 << 30, 1 << 30], 2) == (1 << 30)  # Highest valid bit
assert s.findKOr([1 << 30, 0], 2) == 0                # Highest bit below threshold

assert s.findKOr([5, 5, 5, 1], 3) == 5              # Threshold met exactly
assert s.findKOr([15, 7, 3, 1], 4) == 1             # Only lowest bit appears in all

Test Summary

Test	Why
`[7,12,9,8,9,15], k=4`	Validates the first example
`[2,12,1,11,4,5], k=6`	Validates no qualifying bits
`[10,8,5,9,11,6,8], k=1`	Validates standard OR behavior
`[0], k=1`	Smallest possible zero input
`[1], k=1`	Smallest nonzero input
`[0,0,0], k=2`	All bits absent
`[7,7,7], k=3`	Every bit qualifies
`[7,7,7], k=1`	Standard OR on repeated values
`[1,2,4,8], k=2`	No bit reaches threshold
`[3,3,1], k=2`	Multiple qualifying bits
`[1<<30,1<<30], k=2`	Highest allowed bit position
`[1<<30,0], k=2`	Threshold failure at highest bit
`[5,5,5,1], k=3`	Count exactly equals threshold
`[15,7,3,1], k=4`	Only one bit survives

Edge Cases

k Equals 1

When k = 1, a bit only needs to appear in a single number to be included. This makes the K-or identical to the standard bitwise OR operation. An implementation that incorrectly uses > instead of >= when checking the threshold would fail in this situation. The presented solution correctly uses count >= k.

k Equals nums.length

When k equals the array length, a bit must appear in every number. This behaves similarly to checking common bits across the entire array. The algorithm naturally handles this because only counts equal to the full array size satisfy the threshold.

Highest Possible Bit Position

Numbers may contain bit 30 because values can be as large as 2^31 - 1. A common mistake is iterating only through bits 0 to 29. The solution explicitly checks all 31 positions, from 0 through 30, ensuring the highest valid bit is processed correctly.

Arrays Containing Only Zeros

If every element is zero, every bit count remains zero. No bit can satisfy a positive threshold, so the answer must be zero. The implementation handles this automatically because no counts ever reach k.

Threshold Met Exactly

A subtle bug can occur when a bit appears exactly k times. The problem states that a bit should be included when at least k numbers contain it. The algorithm uses count >= k, ensuring bits that meet the threshold exactly are correctly included in the result.