Skip to content

2917. Find the K-or of an Array

Description

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.

 

Example 1:

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:

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:

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

Solutions

Solution 1: Enumeration

Thinking

Bit \(i\) of the K-or is \(1\) iff at least \(k\) numbers have that bit set; bits are independent. Values are below \(2^{31}\), so \(32\) bits suffice.

Count ones on each bit and OR \(2^i\) into the answer when the count is at least \(k\). \(n \le 50\) needs no extra structure.

We can enumerate each bit \(i\) in the range \([0, 32)\), and count the number of numbers in the array \(nums\) whose \(i\)-th bit is \(1\), denoted as \(cnt\). If \(cnt \ge k\), we add \(2^i\) to the answer.

After the enumeration, we return the answer.

The time complexity is \(O(n \times \log M)\), where \(n\) and \(M\) are the length of the array \(nums\) and the maximum value in \(nums\), respectively. The space complexity is \(O(1)\).

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

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

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

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
function findKOr(nums: number[], k: number): number {
    let ans = 0;
    for (let i = 0; i < 32; ++i) {
        let cnt = 0;
        for (const x of nums) {
            cnt += (x >> i) & 1;
        }
        if (cnt >= k) {
            ans |= 1 << i;
        }
    }
    return ans;
}

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

Comments