We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Find the K-or of an Array

Number: 3183

Difficulty: Easy

Paid? No

Companies: Amazon

Problem Description

Given an integer array nums and an integer k, the task is to compute the "K-or" of the array. Instead of the normal bitwise OR (which sets a bit if at least one number has that bit set), the K-or operation sets a bit to 1 only if at least k numbers in nums have that bit set. Return the resulting integer.

Key Insights

  • The solution involves examining each bit position (typically 0 to 31, since nums[i] < 2^31).
  • Count how many numbers in the array have a 1 in the current bit position.
  • If the count for that bit is greater than or equal to k, set that bit in the result.
  • If k equals 1, the answer is simply the bitwise OR of all numbers.

Space and Time Complexity

Time Complexity: O(n * 32) which simplifies to O(n)
Space Complexity: O(1)

Solution

The approach iterates over each of the possible bit positions (0 through 31). For each bit:

  1. Count the number of array elements that have a 1 at that bit.
  2. If the count is at least k, set that bit in the final result. The data structures used are simple counters and integer variables; no extra space beyond a few variables is required. This method leverages bit manipulation to efficiently aggregate data from the array into the final result.

Code Solutions

# Python solution
def k_or(nums, k):
    result = 0  # Initialize the result variable
    # Iterate over all 32 bit positions (0-indexed)
    for bit in range(32):
        count = 0  # Count of numbers with the current bit set
        for num in nums:
            # Check if the bit at 'bit' is set in num
            if num & (1 << bit):
                count += 1
        # If at least k numbers have the bit set, update the result
        if count >= k:
            result |= (1 << bit)
    return result

# Example usage:
# nums = [7,12,9,8,9,15] and k = 4, output should be 9
print(k_or([7, 12, 9, 8, 9, 15], 4))
← Back to All Questions