Skip to main content
Talentd

Find the K-or of an Array - Solution & Explanation

EasyArrayBit Manipulation16 min readAsked at: Amazon
Practice this problem

Problem Statement

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

Approach Overview

Problem Overview: You receive an integer array nums and an integer k. The K-or value is constructed bit by bit: a bit i is set in the result if at least k numbers in the array have that bit set. The task is to efficiently compute this resulting integer.

Approach 1: Bit Counting (O(n * 32) time, O(1) space)

This method scans each bit position independently. For every bit from 0 to 31, iterate through the array and count how many numbers have that bit set using (num >> bit) & 1. If the count reaches at least k, set that bit in the final result using result |= (1 << bit). The key insight is that the K-or condition depends only on how many elements contain a bit, not their order or magnitude. Since integers typically have 32 bits, the outer loop runs 32 times and the inner loop scans n elements, giving O(n * 32) time with constant space.

This technique is common in problems involving bit manipulation because it decomposes the integer into independent bit positions. It works well when the bit width is small and fixed, which keeps the complexity effectively linear in the size of the array.

Approach 2: Frequency Array for Bit Counting (O(n * 32) time, O(32) space)

This variation separates counting from result construction. First create a frequency array of size 32 where freq[i] stores how many numbers contain bit i. Iterate through each element in nums, check all 32 bits, and increment the corresponding counter when a bit is set. After processing the array, build the final integer by checking each frequency entry. If freq[i] >= k, set bit i in the result.

The advantage of this structure is clarity and reuse. If additional queries depend on bit frequencies, the counts are already available. The memory cost is still tiny because the frequency array has a fixed size of 32. This pattern often appears in array problems that combine counting with bitwise operations.

Recommended for interviews: The direct bit counting approach is what most interviewers expect. It shows you understand how to inspect and manipulate bits efficiently and avoids unnecessary data structures. The frequency array version demonstrates the same idea but organizes the computation differently. Both achieve the optimal O(n) effective complexity since the bit width is constant.

Approach 1: Approach 1: Bit Counting

This approach involves iterating through all the bit positions of the numbers. For each bit position, we count how many numbers have a '1' in that position. If this count is greater than or equal to k, we set the result's bit at this position to '1'. This approach efficiently determines the K-or by focusing directly on the bit counts.

This C solution defines the function kOr which calculates the K-or of the array nums. It iterates over 31 possible bit positions, counting how many times each bit position contains '1' across all numbers. If the count for any bit position meets or exceeds k, that bit is set in the result using bitwise OR.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n * 31) where n is the number of elements in nums.
Space Complexity: O(1) as no additional space is used that scales with the input size.

Try this approach in the editor →

Approach 2: Approach 2: Frequency Array for Bit Counting

This approach optimizes counting by using a frequency array where each index represents a bit position. We traverse the numbers, and for each number, update the frequency array for each bit that is '1'. After filling the frequency array, the K-or result is derived by checking if the frequency count meets or exceeds k at each position.

The C function kOr first initializes a frequency array to track how many numbers have a '1' in each bit position. After processing the entire nums array to fill this frequency array, it constructs the result using only bit positions with a frequency equal to or exceeding k.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n * 31).
Space Complexity: O(31) = O(1) for the frequency array.

Try this approach in the editor →

Approach 3: 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.

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).

Code

PythonJavaC++GoTypeScriptC#

Python

Java

C++

Go

TypeScript

C#

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Approach 1: Bit Counting

Time Complexity: O(n * 31) where n is the number of elements in nums.
Space Complexity: O(1) as no additional space is used that scales with the input size.

Approach 2: Frequency Array for Bit Counting

Time Complexity: O(n * 31).
Space Complexity: O(31) = O(1) for the frequency array.

Enumeration—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Bit CountingO(n * 32)O(1)Best general solution when computing the K-or once with minimal memory
Frequency Array for Bit CountingO(n * 32)O(32)Useful when bit frequencies may be reused or when separating counting and result construction improves readability

Video Solution

2917. Find the K-or of an Array || Easy Explanation 🔥|| Bitwise operations 🔥 • Ayush Rao • 1,228 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Find the K-or of an Array easy or hard?
LeetCode classifies this problem as Easy. The challenge mainly tests familiarity with bit manipulation and counting set bits across multiple integers. Once you recognize that each bit position can be processed independently, the implementation becomes straightforward.
How to solve Find the K-or of an Array in O(n)?
Count how many numbers contain each bit. Loop over bit positions from 0 to 31 and check every element using bit shifting and masking. When the count for a bit is at least k, set that bit in the result using a bitwise OR operation. Because the number of bits is constant, the algorithm behaves like O(n).
Find the K-or of an Array Python or Java solution?
The logic is identical across languages. Iterate over 32 bits, count how many numbers satisfy (num >> bit) & 1, and set the bit in the result when the count is at least k. This approach is easy to implement in Python, Java, C++, JavaScript, and C# using basic bitwise operators.
What is the best approach for Find the K-or of an Array?
The most efficient approach is bit counting. Iterate through all 32 bit positions and count how many numbers in the array have each bit set. If at least k numbers contain that bit, set it in the result. This runs in O(n * 32) time and O(1) space, which is effectively linear for typical integer sizes.
Is Find the K-or of an Array asked at Google/Amazon/Meta?
Problems involving bit counting and bitwise aggregation appear frequently in interviews at companies like Google, Amazon, and Meta. While this exact problem may vary, the technique of counting set bits across an array is a common interview pattern in bit manipulation questions.
What data structure is used in Find the K-or of an Array?
The solution mainly relies on bitwise operations rather than complex data structures. Some implementations use a small frequency array of size 32 to track how many numbers contain each bit. Otherwise, the algorithm works directly on the input array while checking bits with shifts and masks.
What is the time complexity of Find the K-or of an Array?
The standard solution runs in O(n * 32) time because each of the 32 bit positions is checked across all n elements. Since 32 is constant for standard integers, the effective complexity is O(n). Space complexity is O(1) or O(32) depending on whether a frequency array is used.

Ready to solve this problem?

Practice Find the K-or of an Array with our built-in code editor and test cases.

Practice on FleetCode
Previous

Counting Bits

Next

Sum of Values at Indices With K Set Bits