Find the K-or of an Array

Difficulty: Easy | Acceptance: 72.80% | Paid: No Topics: Array, Bit Manipulation

You are given a 0-indexed integer array nums and an integer k.

The K-or of nums is a non-negative integer that satisfies the following:

• The ith bit is set in the K-or if and only if there are at least k elements in nums where the ith bit is set.

Return the K-or of nums.

Note that for any integer x, the ith bit is the bit at the ith position from the right in the binary representation of x.

• Examples
• Constraints
• Bit-by-Bit Analysis
• Pre-counting All Bits

Examples

Input: nums = [7,12,9,8,9,15], k = 4
Output: 9
Explanation:
- 0th bit: 7, 9, 9, 15 have the 0th bit set (4 numbers >= k)
- 1st bit: 7, 9, 9, 15 have the 1st bit set (4 numbers >= k)
- 2nd bit: 7, 12, 9, 8, 9, 15 have the 2nd bit set (6 numbers >= k)
- 3rd bit: 12, 8, 15 have the 3rd bit set (3 numbers < k)
So the K-or is 9 (binary 1001).

Input: nums = [2,12,1,11,4,5], k = 6
Output: 0
Explanation: No bit has at least 6 numbers with that bit set.

Input: nums = [10,8,5,9,11,6,8], k = 1
Output: 15
Explanation: Every bit has at least 1 number with that bit set.

Constraints

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

Bit-by-Bit Analysis

Intuition For each bit position from 0 to 30, count how many numbers have that bit set. If the count is at least k, include that bit in the result.

Steps

• Iterate through each bit position (0 to 30 since nums[i] ≤ 10⁹ < 2³⁰)
• For each bit, count how many numbers in the array have that bit set
• If count ≥ k, set that bit in the result using bitwise OR
• Return the final result

from typing import List

class Solution:
    def findKOr(self, nums: List[int], k: int) -> int:
        result = 0
        for i in range(31):
            count = 0
            for num in nums:
                if num & (1 << i):
                    count += 1
            if count >= k:
                result |= (1 << i)
        return result

Complexity

• Time: O(31 × n) where n is the length of nums
• Space: O(1)
• Notes: Simple and efficient approach with constant space overhead

Pre-counting All Bits

Intuition First, count all set bits across all numbers in a single array, then construct the result by checking which bit positions meet the threshold.

Steps

• Create an array of size 31 to store bit counts
• Iterate through all numbers and increment the count for each set bit
• After counting, construct the result by setting bits where count ≥ k
• Return the final result

from typing import List

class Solution:
    def findKOr(self, nums: List[int], k: int) -> int:
        bit_counts = [0] * 31
        for num in nums:
            for i in range(31):
                if num & (1 << i):
                    bit_counts[i] += 1
        
        result = 0
        for i in range(31):
            if bit_counts[i] >= k:
                result |= (1 << i)
        return result

Complexity

• Time: O(31 × n) where n is the length of nums
• Space: O(31) for the bit counts array
• Notes: Uses extra space but separates counting and result construction phases