Find the K-or of an Array

Easy
719.

Find the K-or of an Array

Find the K-or of an Array is an easy coding problem on arrays and bit manipulation, asked in Amazon, TCS and Infosys interviews.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var findKOr = function(nums, k) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Find the K-or of an Array — Solution in Python, Java & C++

Find the K-or of an Array solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.

Find the K-or of an Array is an easy coding problem on arrays and bit manipulation, asked in Amazon, TCS and Infosys interviews.

  • Difficulty: Easy
  • Topics: Arrays, Bit Manipulation
  • Asked at: Amazon, TCS, Infosys
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

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

Hints for Find the K-or of an Array

  1. Hint 1

    Decide each bit independently — the bits never interact.

  2. Hint 2

    For bit i, count how many elements have it set and compare with k.

  3. Hint 3

    31 bits times 50 elements is a tiny amount of work.

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

Java

public static int findKOr(int[] nums, int k) {
    int out = 0;
    for (int b = 0; b < 31; b++) {
        int c = 0;
        for (int x : nums) {
            if (((x >> b) & 1) == 1) c++;
        }
        if (c >= k) out |= 1 << b;
    }
    return out;
}

C++

int findKOr(vector<int>& nums, int k) {
    int out = 0;
    for (int b = 0; b < 31; b++) {
        int c = 0;
        for (int x : nums) {
            if ((x >> b) & 1) c++;
        }
        if (c >= 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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Bit Manipulation