Watch 10 video solutions for Find the K-or of an Array, a easy level problem involving Array, Bit Manipulation. This walkthrough by Ayush Rao has 1,219 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.lengthProblem 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 | 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 |