Find the K-or of an Array solution and explanation
9 more videos on this problem
2917. Find the K-or of an Array || Easy Explanation 🔥|| Bitwise operations 🔥Ayush Rao · 3:22 · 1K views
100111 Find the K or of an Array|| leetcode || contest369 || weekly contest || solutionSsquare · 0:30 · 629 views
Find the K-or of an Array | Leetcode Weekly 369 | DCC NIT-ADCC NITA · 4:21 · 441 views
2917. Find the K-or of an Array (Leetcode Easy)Programming Live with Larry · 2:35 · 321 views
Leetcode Weekly Contest 369 || Problems A, B, C, D || 2917, 2918, 2919, 2920 || CodeaticCode-a-tic · 44:13 · 266 views
Leetcode 2917 K-or of an Array Leetcode 2917Brain Box · 6:28 · 189 views
Cracking the 'K-or of an Array' LeetCode 2917 Problem | Bitwise Magic Explained!vanAmsen · 6:32 · 170 views
Find the K-or of an Array | Leetcode 2917 | Approach + Code with explanation.Pirai's Academy · 8:43 · 102 views
leetcode 2917 Find the K or of An Array Bit OpsCode-Yao · 11:08 · 37 views
Leetcode easy problem 2917. Find the K-or of an Array | devops python practiceADevOpsEngineer · 3:12 · 13 views
The 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.
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 <= 500 <= nums[i] < 2311 <= 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.
def k_or(nums, k):
result = 0
for i in range(31):
count = sum(1 for num in nums if (num & (1 << i)))
if count >= k:
result |= (1 << i)
return result
nums = [7, 12, 9, 8, 9, 15]
k = 4
print(k_or(nums, k))public class Main {
public static int kOr(int[] nums, int k) {
int result = 0;
for (int i = 0; i < 31; i++) {
int count = 0;
for (int num : nums) {
if ((num & (1 << i)) != 0) count++;
}
if (count >= k) result |= (1 << i);
}
return result;
}
public static void main(String[] args) {
int[] nums = {7, 12, 9, 8, 9, 15};
int k = 4;
System.out.println(kOr(nums, k));
}
}#include <iostream>
#include <vector>
using namespace std;
int kOr(vector<int>& nums, int k) {
int result = 0;
for (int i = 0; i < 31; i++) {
int count = 0;
for (int num : nums) {
if (num & (1 << i)) count++;
}
if (count >= k) result |= (1 << i);
}
return result;
}
int main() {
vector<int> nums = {7, 12, 9, 8, 9, 15};
int k = 4;
cout << kOr(nums, k) << endl;
return 0;
}function kOr(nums, k) {
let result = 0;
for (let i = 0; i < 31; i++) {
let count = 0;
for (let num of nums) {
if ((num & (1 << i)) !== 0) count++;
}
if (count >= k) result |= (1 << i);
}
return result;
}
let nums = [7, 12, 9, 8, 9, 15];
let k = 4;
console.log(kOr(nums, k));#include <stdio.h>
int kOr(int* nums, int numsSize, int k) {
int result = 0;
for (int i = 0; i < 31; i++) {
int count = 0;
for (int j = 0; j < numsSize; j++) {
if (nums[j] & (1 << i)) count++;
}
if (count >= k) result |= (1 << i);
}
return result;
}
int main() {
int nums[] = {7, 12, 9, 8, 9, 15};
int k = 4;
printf("%d\n", kOr(nums, 6, k));
return 0;
}using System;
public class Program
{
public static int KOr(int[] nums, int k)
{
int result = 0;
for (int i = 0; i < 31; i++)
{
int count = 0;
foreach (int num in nums)
{
if ((num & (1 << i)) != 0) count++;
}
if (count >= k) result |= (1 << i);
}
return result;
}
public static void Main()
{
int[] nums = {7, 12, 9, 8, 9, 15};
int k = 4;
Console.WriteLine(KOr(nums, k));
}
}This Python function, k_or, iterates through 31 bit positions, using a sum generator expression to count set bits in each position for the array nums. It then updates the result based on these counts.
Time Complexity: O(n * 31).
Space Complexity: O(1) as the variables used for storage don't scale with input size.
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.
def k_or(nums, k):
result = 0
freq = [0] * 31
for num in nums:
for i in range(31):
if num & (1 << i):
freq[i] += 1
for i in range(31):
if freq[i] >= k:
result |= (1 << i)
return result
nums = [7, 12, 9, 8, 9, 15]
k = 4
print(k_or(nums, k))public class Main {
public static int kOr(int[] nums, int k) {
int result = 0;
int[] freq = new int[31];
for (int num : nums) {
for (int i = 0; i < 31; i++) {
if ((num & (1 << i)) != 0) freq[i]++;
}
}
for (int i = 0; i < 31; i++) {
if (freq[i] >= k) result |= (1 << i);
}
return result;
}
public static void main(String[] args) {
int[] nums = {7, 12, 9, 8, 9, 15};
int k = 4;
System.out.println(kOr(nums, k));
}
}#include <iostream>
#include <vector>
using namespace std;
int kOr(vector<int>& nums, int k) {
int result = 0;
vector<int> freq(31, 0);
for (int num : nums) {
for (int i = 0; i < 31; i++) {
if (num & (1 << i)) freq[i]++;
}
}
for (int i = 0; i < 31; i++) {
if (freq[i] >= k) result |= (1 << i);
}
return result;
}
int main() {
vector<int> nums = {7, 12, 9, 8, 9, 15};
int k = 4;
cout << kOr(nums, k) << endl;
return 0;
}function kOr(nums, k) {
let result = 0;
let freq = new Array(31).fill(0);
nums.forEach(num => {
for (let i = 0; i < 31; i++) {
if ((num & (1 << i)) !== 0) freq[i]++;
}
});
for (let i = 0; i < 31; i++) {
if (freq[i] >= k) result |= (1 << i);
}
return result;
}
let nums = [7, 12, 9, 8, 9, 15];
let k = 4;
console.log(kOr(nums, k));#include <stdio.h>
#include <string.h>
int kOr(int* nums, int numsSize, int k) {
int result = 0;
int freq[31];
memset(freq, 0, sizeof(freq));
for (int j = 0; j < numsSize; j++) {
for (int i = 0; i < 31; i++) {
if (nums[j] & (1 << i)) freq[i]++;
}
}
for (int i = 0; i < 31; i++) {
if (freq[i] >= k) result |= (1 << i);
}
return result;
}
int main() {
int nums[] = {7, 12, 9, 8, 9, 15};
int k = 4;
printf("%d\n", kOr(nums, 6, k));
return 0;
}using System;
public class Program
{
public static int KOr(int[] nums, int k)
{
int result = 0;
int[] freq = new int[31];
foreach (int num in nums)
{
for (int i = 0; i < 31; i++)
{
if ((num & (1 << i)) != 0) freq[i]++;
}
}
for (int i = 0; i < 31; i++)
{
if (freq[i] >= k) result |= (1 << i);
}
return result;
}
public static void Main()
{
int[] nums = {7, 12, 9, 8, 9, 15};
int k = 4;
Console.WriteLine(KOr(nums, k));
}
}The Python solution applies the frequency approach using a list of size 31. Each element in nums is inspected to populate the frequency list, eventually producing the K-or result.
Time Complexity: O(n * 31).
Space Complexity: O(31).
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).
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;
}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
}Complexity comparison
| Approach | Complexity |
|---|---|
| Approach 1: Bit Counting | Time Complexity: O(n * 31). |
| Approach 2: Frequency Array for Bit Counting | Time Complexity: O(n * 31). |
| Enumeration | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Bit Counting | O(n * 32) | O(1) | Best general solution when computing the K-or once with minimal memory |
| Frequency Array for Bit Counting | O(n * 32) | O(32) | Useful when bit frequencies may be reused or when separating counting and result construction improves readability |
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.