Problem

You are given an integer array nums, and an integer k. Let’s introduce K-or operation by extending the standard bitwise OR. In K-or, a bit position in the result is set to 1 if at least k numbers in nums have a 1 in that position.

Return the K-or of nums.

Examples

Example 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21


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

Output: 9

Explanation:

Represent numbers in binary:

**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  
**Result = 9** | 1 | 0 | 0 | 1  
  
Bit 0 is set in 7, 9, 9, and 15. Bit 3 is set in 12, 9, 8, 9, and 15.  
Only bits 0 and 3 qualify. The result is `(1001)2 = 9`.

Example 2

1
2
3
4
5
6
7


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

Output: 0

**Explanation:  **No bit appears as 1 in all six array numbers, as required
for K-or with `k = 6`. Thus, the result is 0.

Example 3

1
2
3
4
5
6
7
8


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

Output: 15

Explanation: Since `k == 1`, the 1-or of the array is equal to the bitwise
OR of all its elements. Hence, the answer is `10 OR 8 OR 5 OR 9 OR 11 OR 6 OR
8 = 15`.

Constraints

  • 1 <= nums.length <= 50
  • 0 <= nums[i] < 231
  • 1 <= k <= nums.length

Solution

Method 1 – Bit Counting

Intuition

For each bit position, count how many numbers in the array have that bit set. If at least k numbers have a 1 at that position, set that bit in the result. This is a direct application of bit manipulation and counting.

Approach

  1. Initialize an array cnt to count set bits for each bit position (up to 32 bits for 32-bit integers).
  2. For each number in nums, for each bit position, increment the count if the bit is set.
  3. For each bit position, if the count is at least k, set that bit in the answer.
  4. Return the answer.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
public:
    int findKOr(vector<int>& nums, int k) {
        int ans = 0;
        for (int b = 0; b < 32; ++b) {
            int cnt = 0;
            for (int x : nums) {
                if (x & (1 << b)) ++cnt;
            }
            if (cnt >= k) ans |= (1 << b);
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

func findKOr(nums []int, k int) int {
    ans := 0
    for b := 0; b < 32; b++ {
        cnt := 0
        for _, x := range nums {
            if x&(1<<b) != 0 {
                cnt++
            }
        }
        if cnt >= k {
            ans |= 1 << b
        }
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
    public int findKOr(int[] nums, int k) {
        int ans = 0;
        for (int b = 0; b < 32; ++b) {
            int cnt = 0;
            for (int x : nums) {
                if ((x & (1 << b)) != 0) ++cnt;
            }
            if (cnt >= k) ans |= (1 << b);
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
    fun findKOr(nums: IntArray, k: Int): Int {
        var ans = 0
        for (b in 0 until 32) {
            var cnt = 0
            for (x in nums) {
                if ((x shr b) and 1 == 1) cnt++
            }
            if (cnt >= k) ans = ans or (1 shl b)
        }
        return ans
    }
}
1
2
3
4
5
6
7
8

class Solution:
    def findKOr(self, nums: list[int], k: int) -> int:
        ans = 0
        for b in range(32):
            cnt = sum((x >> b) & 1 for x in nums)
            if cnt >= k:
                ans |= (1 << b)
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

impl Solution {
    pub fn find_k_or(nums: Vec<i32>, k: i32) -> i32 {
        let mut ans = 0;
        for b in 0..32 {
            let cnt = nums.iter().filter(|&&x| (x >> b) & 1 == 1).count();
            if cnt as i32 >= k {
                ans |= 1 << b;
            }
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
    findKOr(nums: number[], k: number): number {
        let ans = 0;
        for (let b = 0; b < 32; ++b) {
            let cnt = 0;
            for (const x of nums) {
                if ((x & (1 << b)) !== 0) cnt++;
            }
            if (cnt >= k) ans |= (1 << b);
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n * 32), where n is the length of nums, since we check each bit for each number.
  • 🧺 Space complexity: O(1), as only a constant amount of space is used for counters and the result.