Find the K-or of an Array
EasyPrompt
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
Approaches
3 approaches with complexity analysis and trade-offs.
This approach involves converting each integer into its binary string representation. After ensuring all binary strings have a uniform length by padding with leading zeros, we can iterate through each bit position (column) and count the number of '1's. If the count for a specific bit position meets the k threshold, the corresponding bit is set in the final result. This method is conceptually straightforward but less efficient in terms of memory usage.
Algorithm
- Create an array of strings to store the binary representations of the numbers in
nums. - For each number in
nums, convert it to a 31-bit binary string, padding with leading zeros to ensure a uniform length of 31. Add this string to the array. - Initialize an integer
result = 0. - Iterate from
i = 0to 30. This loop represents the bit positions, withi=0being the least significant bit. - Inside this loop, initialize a
count = 0. - Iterate through each binary string in the array.
- Check the character at index
30 - i(since bit 0 is the rightmost character). If it's '1', incrementcount. - After iterating through all strings, if
count >= k, set thei-th bit in theresultusing the bitwise OR operation:result |= (1 << i). - After the outer loop finishes,
resultwill hold the K-or value. Returnresult.
Walkthrough
This approach works by translating the numbers into a more visual, string-based format. We first convert every number into a 31-bit binary string, padding with leading zeros as necessary. This creates a grid of characters (0s and 1s) where rows are numbers and columns are bit positions. We then iterate through each column (bit position), count the number of '1's, and if this count is at least k, we set the corresponding bit in our final integer result.
class Solution { public int findKOr(int[] nums, int k) { int n = nums.length; String[] binaryStrings = new String[n]; for (int i = 0; i < n; i++) { String binary = Integer.toBinaryString(nums[i]); StringBuilder sb = new StringBuilder(); for(int j = 0; j < 31 - binary.length(); j++) { sb.append('0'); } sb.append(binary); binaryStrings[i] = sb.toString(); } int result = 0; for (int i = 0; i < 31; i++) { // i represents the bit position from the right (0 to 30) int count = 0; for (int j = 0; j < n; j++) { // Character at index (30 - i) corresponds to bit i if (binaryStrings[j].charAt(30 - i) == '1') { count++; } } if (count >= k) { result |= (1 << i); } } return result; }}Complexity
Time
O(N * B), where N is the number of elements in `nums` and B is the number of bits in an integer (31). Converting N numbers to B-bit strings takes O(N*B). The nested loops for counting also take O(N*B).
Space
O(N * B), where N is the number of elements in `nums` and B is the number of bits in an integer (31). We need to store N binary strings, each of length B.
Trade-offs
Pros
Conceptually simple for those more comfortable with strings than bitwise operations.
Cons
High space usage due to storing intermediate binary strings.
String manipulations are generally slower in practice than direct bitwise operations.
This approach avoids string conversion and uses direct bitwise operations. We use an auxiliary array to keep track of the counts of set bits for each bit position across all numbers in the input array. After populating this count array, we construct the final result by checking which bit positions have a count greater than or equal to k. This method improves upon the string-based approach by reducing space complexity.
Algorithm
- Create an integer array
bitCountsof size 31, initialized to all zeros. - Iterate through each
numin thenumsarray. - For each
num, iterate through its bits fromi = 0to 30. - If the
i-th bit is set innum, incrementbitCounts[i]. - Initialize an integer
result = 0. - Iterate from
i = 0to 30 through thebitCountsarray. - If
bitCounts[i] >= k, set thei-th bit in theresult:result |= (1 << i). - Return
result.
Walkthrough
This method is a significant improvement over the string-based approach. It directly manipulates the bits of the integers. The core idea is to first aggregate the counts for each bit position into an array. We iterate through each number in the input, and for each number, we update the counts in a bitCounts array for each of its set bits. After this single pass to gather statistics, we build the final result by iterating through our bitCounts array and setting a bit in the result if its count is k or more.
class Solution { public int findKOr(int[] nums, int k) { int[] bitCounts = new int[31]; for (int num : nums) { for (int i = 0; i < 31; i++) { if (((num >> i) & 1) == 1) { bitCounts[i]++; } } } int result = 0; for (int i = 0; i < 31; i++) { if (bitCounts[i] >= k) { result |= (1 << i); } } return result; }}Complexity
Time
O(N * B), where N is the length of `nums` and B is the number of bits (31). The first nested loop to populate the `bitCounts` array runs N * B times. The second loop to construct the result runs B times. The total complexity is O(N*B).
Space
O(B), where B is the number of bits (31). We use an extra array of size B to store the bit counts. Since B is a constant, this is effectively O(1) constant space.
Trade-offs
Pros
Efficient in terms of time.
Avoids the overhead of string conversions and high memory usage of the string approach.
Cons
Requires an auxiliary array for counts, which uses slightly more space than the most optimal approach.
This is the most efficient approach in terms of space. Instead of using an intermediate data structure to store counts, we iterate through each bit position from 0 to 30. For each bit position, we perform a full pass over the input array to count how many numbers have that bit set. If the count meets the k threshold, we set the corresponding bit in our result. This approach builds the result bit by bit with minimal memory overhead.
Algorithm
- Initialize an integer
result = 0. - Iterate through each bit position
ifrom 0 to 30. - For each bit
i, initialize a temporarycount = 0. - Iterate through each
numin thenumsarray. - Check if the
i-th bit is set innumand if so, incrementcount. - After iterating through all numbers, if
count >= k, set thei-th bit in theresult. - After iterating through all 31 bit positions, return
result.
Walkthrough
This approach refines the bit manipulation technique by changing the order of iteration. Instead of processing number by number, we process bit by bit. For each bit position from 0 to 30, we iterate through the entire nums array to count how many numbers have this specific bit set. If the count is sufficient (at least k), we immediately set that bit in our result. This avoids the need for an auxiliary array to store all bit counts simultaneously, making it the most space-efficient solution.
class Solution { public int findKOr(int[] nums, int k) { int result = 0; // Iterate over each bit position from 0 to 30 for (int i = 0; i < 31; i++) { int count = 0; // For each bit, count how many numbers have it set for (int num : nums) { if (((num >> i) & 1) == 1) { count++; } } // If the count is at least k, set the i-th bit in the result if (count >= k) { result |= (1 << i); } } return result; }}Complexity
Time
O(N * B), where N is the length of `nums` and B is the number of bits (31). We have a nested loop structure. The outer loop runs B times, and the inner loop runs N times.
Space
O(1). We only use a few variables (`result`, `i`, `count`, `num`) to store intermediate values. The space required does not depend on the size of the input, making it the most space-efficient solution.
Trade-offs
Pros
Most space-efficient solution with O(1) complexity.
Clear and direct implementation of the problem definition.
Efficient time complexity.
Cons
The memory access pattern (iterating through the whole
numsarray for each bit) might be slightly less cache-friendly than the count array approach, but this is a micro-optimization and unlikely to be significant given the problem constraints.
Solutions
Solution
public class Solution { public int FindKOr(int[] nums, int k) { int ans = 0; for (int i = 0; i < 32; ++i) { int cnt = 0; foreach(int x in nums) { cnt += (x >> i & 1); } if (cnt >= k) { ans |= 1 << i; } } return ans; }}class Solution {public int findKOr(int[] nums, int k) { int ans = 0; for (int i = 0; i < 32; ++i) { int cnt = 0; for (int x : nums) { cnt += (x >> i & 1); } if (cnt >= k) { ans |= 1 << i; } } return ans; }}class Solution {public: int findKOr(vector<int> &nums, int k) { int ans = 0; for (int i = 0; i < 32; ++i) { int cnt = 0; for (int x : nums) { cnt += (x >> i & 1); } if (cnt >= k) { ans |= 1 << i; } } return ans; }};class Solution: def findKOr(self, nums: List[int], k: int) -> int: ans = 0 for i in range(32): cnt = sum(x >> i & 1 for x in nums) if cnt >= k: ans |= 1 << i return ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.