Find the K-or of an Array - Practice Coding Problems

Find the K-or of an Array - 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.

Input & Output

Example 1 — Basic Case

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

› Output: 9

💡 Note: Binary: 7=0111, 12=1100, 9=1001, 8=1000, 9=1001, 15=1111. Bit 0 appears in 4 numbers (7,9,9,15), bit 3 appears in 4 numbers (8,9,9,12). Result = 1001₂ = 9

Example 2 — Higher Threshold

$ Input: nums = [2,12,1,3,4,5], k = 3

› Output: 0

💡 Note: No bit position appears in 3 or more numbers, so K-or result is 0

Example 3 — Low Threshold

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

› Output: 15

💡 Note: Multiple bit positions have count ≥ 2. Result combines all qualifying bits to get 15

Constraints

1 ≤ nums.length ≤ 50
0 ≤ nums[i] < 2³¹
1 ≤ k ≤ nums.length

Visualization

Tap to expand

Understanding the Visualization

Input

Array [7,12,9,8,9,15] and threshold k=4

Count Bits

Count occurrences of each bit position

Apply Threshold

Include only bits with count ≥ k

Key Takeaway

🎯 Key Insight: K-or is like democratic voting - each bit position needs at least k votes to win

Asked in

a Amazon 15 M Microsoft 12

The key insight is that K-or treats each bit position independently - we count how many numbers have each bit set, then include bits that appear at least k times. Best approach uses single pass counting with O(32×n) = O(n) time and O(1) space.

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force Bit Counting	O(32 × n)	O(1)	Check each bit position individually and count occurrences
Single Pass Bit Accumulation	O(n)	O(1)	Count all bit positions in one pass through the array

Brute Force Bit Counting — Algorithm Steps

Iterate through each bit position (0 to 31)
For each position, count numbers with bit set
If count >= k, set bit in result

Visualization

Tap to expand

Step-by-Step Walkthrough

Check Bit 0

Count numbers with bit 0 set

Check Bit 1

Count numbers with bit 1 set

Build Result

Set bits where count >= k

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int solution(int* nums, int numsSize, int k) {
    int result = 0;
    // Check each bit position (0 to 31 for 32-bit integers)
    for (int bitPos = 0; bitPos < 32; bitPos++) {
        int count = 0;
        // Count how many numbers have this bit set
        for (int i = 0; i < numsSize; i++) {
            if (nums[i] & (1 << bitPos)) {
                count++;
            }
        }
        // If at least k numbers have this bit set, include it in result
        if (count >= k) {
            result |= (1 << bitPos);
        }
    }
    return result;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    // Parse array
    int nums[1000];
    int numsSize = 0;
    char* token = strtok(line, "[,]");
    while (token != NULL) {
        if (strlen(token) > 0 && token[0] != '\n' && token[0] != ']') {
            nums[numsSize++] = atoi(token);
        }
        token = strtok(NULL, "[,]");
    }
    
    int k;
    scanf("%d", &k);
    
    int result = solution(nums, numsSize, k);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(32 × n)

Check 32 bit positions, for each position scan n numbers

✓ Linear Growth

Space Complexity

O(1)

Only using a few variables for counting and result

✓ Linear Space

8.9K Views

Medium Frequency

~15 min Avg. Time

245 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force Bit Counting — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler