Find the K-or of an Array — Easy Problem & Solution

Problem statement

The K-or of an array is the number whose bit i is set exactly when at least k elements of nums have bit i set.

Return the K-or of nums.

Example 1

Input: nums = [7,12,9,8,9,15], k = 4
Output: 9
Explanation: Bit 0 is set in 7, 9, 9 and 15 — four elements — and bit 3 is set in 12, 9, 8, 9 and 15. No other bit reaches four.

Example 2

Input: nums = [2,12,1,11,4,5], k = 6
Output: 0
Explanation: No bit is set in all six numbers.

Example 3

Input: nums = [10,8,5,9,11,6,8], k = 1
Output: 15
Explanation: With k = 1 the K-or is the plain OR of everything.

Constraints

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

How to solve Find the K-or of an Array

The definition is per-bit, so handle one bit at a time: count the elements that have it, and set it in the answer when the count reaches k.

Approach

1. Loop b from 0 to 30.
2. Count the elements whose bit b is set.
3. If that count is at least k, add 2^b to the answer.

Why it works

Bits of the answer are defined independently of one another, so no interaction or carry logic is needed — the loop is a direct transcription of the definition.

Complexity

• Time — O(31 · n)
• Space — O(1)

Pitfalls

• Values reach 2^31 - 1, so bit 30 matters and bit 31 does not exist for a signed int.
• In JavaScript 1 << 31 is negative — build the answer by adding powers of two instead of shifting into the sign bit.
• k = 1 reduces to the ordinary OR, which is a useful sanity check.

Reference solution

Python

from typing import List

def findKOr(nums: List[int], k: int) -> int:
    out = 0
    for b in range(31):
        if sum(1 for x in nums if (x >> b) & 1) >= k:
            out |= 1 << b
    return out

JavaScript

var findKOr = function(nums, k) {
    var out = 0;
    for (var b = 0; b < 31; b++) {
        var c = 0;
        for (var i = 0; i < nums.length; i++) {
            if (Math.floor(nums[i] / Math.pow(2, b)) % 2 === 1) c++;
        }
        if (c >= k) out += Math.pow(2, b);
    }
    return out;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Number of Bit Changes to Make Two Integers Equal Easy
• Find the XOR of Numbers Which Appear Twice Easy
• Binary Watch Easy
• Smallest Number With All Set Bits Easy
• Shortest Subarray With OR at Least K I Easy
• Maximum Strong Pair XOR I Easy