#2917

Easy

LeetCode Problem Workspace

Find the K-or of an Array

Given an integer array nums and an integer k, find the K-or of nums where bits qualify based on the occurrence of 1s.

Problem Statement

You are given an integer array nums, and an integer k. The task is to calculate the K-or of nums. 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. The goal is to compute the K-or value using this rule for all bit positions from 0 to 31.

Return the K-or of nums. The result must be computed efficiently, and the length of the array can range from 1 to 50 with each element having a value less than 2^31.

Examples

Example 1

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

Output: 9

Represent numbers in binary: 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

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

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 Approach

Bit Counting

Iterate over all 32 bit positions (since nums[i] < 2^31) and count how many numbers in nums have a 1 in each bit position. If the count of 1s is greater than or equal to k, set that bit in the result.

Efficient Traversal

Instead of checking each element for every bit, fix one bit and count its occurrences in all elements of nums. This way, you can minimize redundant operations and ensure that the solution scales well with the input size.

Bitwise OR Operation

After counting the qualifying bits for all positions, combine them using a bitwise OR operation to form the final K-or result.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity is O(32 * n) where n is the length of the nums array. This is because we need to check each bit (32 bits) for each number in the array. The space complexity is O(1) since we only store a few counters and the result.

What Interviewers Usually Probe

Look for the candidate's ability to optimize the bit counting process.
Watch for efficient traversal strategies, avoiding repeated work.
Assess understanding of bitwise operations and how to combine results.

Common Pitfalls or Variants

Common pitfalls

Misunderstanding the problem's rule for setting bits based on k occurrences.
Failing to consider all bit positions, especially in larger numbers.
Overcomplicating the solution when a simple bit-counting approach works.

Follow-up variants

Solve the problem for a larger array (nums.length > 50).
Optimize the solution to handle numbers with a bit length greater than 31.
Modify the problem to find the K-or for a dynamic range of k values.

FAQ

What is the K-or operation in this problem?

K-or sets a bit in the result to 1 if at least k numbers in nums have a 1 in that bit position.

How do I efficiently count bits in an array?

You can loop through each bit position (0-31) and count how many numbers have a 1 in that position.

What is the time complexity of this problem?

The time complexity is O(32 * n), where n is the length of the array, as we check 32 bits for each element.

Why do we consider only 32 bit positions?

Since the maximum number in nums is less than 2^31, we only need to check the lower 32 bit positions.

How can I optimize this problem?

You can optimize the traversal by fixing a bit and counting its occurrences efficiently instead of repeatedly checking each number for every bit.

terminal

Solution

Solution 1: Enumeration

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.

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

Continue Practicing

#2920 maximum points after collecting coins from all nodes #2932 maximum strong pair xor i #2935 maximum strong pair xor ii