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.lengthThis 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.
C++
Java
Python
C#
JavaScript
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.
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.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n * 31).
Space Complexity: O(31) = O(1) for the frequency array.
| Approach | Complexity |
|---|---|
| Approach 1: Bit Counting | Time Complexity: O(n * 31) where n is the number of elements in |
| Approach 2: Frequency Array for Bit Counting | Time Complexity: O(n * 31). |
Kth Largest Element in an Array - Quick Select - Leetcode 215 - Python • NeetCode • 331,616 views views
Watch 9 more video solutions →Practice Find the K-or of an Array with our built-in code editor and test cases.
Practice on FleetCode