Leetcode 2917: Find the K-or of an Array
You are given an integer array
nums and an integer k. We define the K-or operation as follows: for each bit position, the bit in the result will be set to 1 if at least k numbers in the array nums have a 1 in that position. Return the K-or of the array nums.Problem
Approach
Steps
Complexity
Input: The input consists of an integer array `nums` and an integer `k`.
Example: nums = [6, 15, 9, 8, 7, 14], k = 4
Constraints:
• 1 <= nums.length <= 50
• 0 <= nums[i] < 231
• 1 <= k <= nums.length
Output: Return the **K-or** of the array `nums`.
Example: Output: 14
Constraints:
• The result must be an integer.
Goal: We need to find the bitwise OR of all bits that appear in at least `k` numbers from `nums`.
Steps:
• Iterate through each bit position from 0 to 30 (since nums[i] < 2^31).
• For each bit position, count how many numbers have that bit set to 1.
• If the count is greater than or equal to `k`, set that bit in the result.
Goal: The input array length and numbers within it are constrained by the given limits.
Steps:
• 1 <= nums.length <= 50
• 0 <= nums[i] < 231
• 1 <= k <= nums.length
Assumptions:
• The array contains at least 1 element.
• k is always less than or equal to the number of elements in `nums`.
• Input: Input: nums = [6, 15, 9, 8, 7, 14], k = 4
• Explanation: For each bit position, we check how many numbers have that bit set to 1. In this example, the result is 14 because the 2nd, 3rd, and 4th bits appear in at least 4 numbers.
Approach: We use bitwise operations to determine which bits appear in at least `k` numbers in the array.
Observations:
• We are dealing with bitwise operations, and the solution involves counting the number of 1s in each bit position.
• This problem can be solved efficiently by iterating through each bit position and counting how many numbers have a 1 at that position.
Steps:
• Loop through each of the 31 bit positions (0 to 30).
• For each bit position, count how many numbers in `nums` have that bit set to 1.
• If the count of 1s for that bit position is greater than or equal to `k`, set the bit in the result.
Empty Inputs:
• The input array will always have at least one element.
Large Inputs:
• If `nums` contains the maximum number of elements (50), the solution will still perform efficiently.
Special Values:
• When `k == 1`, the result will be the bitwise OR of all elements.
Constraints:
• We assume that the constraints are within the range of the problem.
int findKOr(vector<int>& nums, int k) {
int ans = 0; // Initialize the answer to 0.
for (int i = 0; i < 31; i++) {
// Bit position represented by 2^i.
int rep = (1 << i);
int cnt = 0; // Initialize a counter to count set bits at this position.
// Iterate through the input vector 'nums'.
for (auto ele : nums) {
if (rep & ele) {
// If the i-th bit is set in 'ele', increment the count.
cnt++;
}
}
// If the count of set bits at this position is greater than or equal to 'k', set the corresponding bit in the answer.
if (cnt >= k) {
ans = ans | rep;
}
}
return ans; // Return the final answer, which is the result of the OR operation on selected bits.
}
1 : Function Definition
int findKOr(vector<int>& nums, int k) {
Defines the function 'findKOr' that takes a vector of integers and an integer k as input.
2 : Variable Initialization
int ans = 0; // Initialize the answer to 0.
Initializes the answer variable 'ans' to 0.
3 : Loop Setup
for (int i = 0; i < 31; i++) {
Begins a loop to iterate through 31 possible bit positions.
4 : Bitwise Shift
int rep = (1 << i);
Performs a left bitwise shift to calculate the value of 2^i and assigns it to 'rep'.
5 : Variable Initialization
int cnt = 0; // Initialize a counter to count set bits at this position.
Initializes a counter 'cnt' to track the number of set bits at the current position.
6 : Loop through Input
for (auto ele : nums) {
Begins a loop to iterate through each element in the 'nums' vector.
7 : Conditional Check
if (rep & ele) {
Checks if the i-th bit of the element 'ele' is set using a bitwise AND operation.
8 : Increment Counter
cnt++;
Increments the counter 'cnt' if the i-th bit of 'ele' is set.
9 : Conditional Check
if (cnt >= k) {
Checks if the count of set bits at the current bit position is greater than or equal to 'k'.
10 : Bitwise OR
ans = ans | rep;
Performs a bitwise OR operation to set the corresponding bit in 'ans'.
11 : Return Statement
return ans; // Return the final answer, which is the result of the OR operation on selected bits.
Returns the final result of the OR operation on selected bits.
Best Case: O(n * 31), where n is the number of elements in `nums`.
Average Case: O(n * 31)
Worst Case: O(n * 31)
Description: We iterate over each bit position (31 positions) for each element in the array.
Best Case: O(1)
Worst Case: O(1), since the space used is constant.
Description: We only use a few variables to track the result and bit counts.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus