algoadvance

Leetcode 2917. Find the K

Problem Statement

We are given an array of integers, arr, and an integer k. The task is to find the K-or of the array. The K-or of the array is defined as the maximum bitwise OR value of any k elements from the array.

Clarifying Questions

1. What is the size range for the input array arr?
   • Let’s assume the size of the array is reasonably large, potentially up to 10^5 elements.
2. What is the range of the values in the array?
   • The values in the array can range from 0 to 10^9.
3. What is the range for k?
   • k is an integer where (1 \leq k \leq \text{size of the array}).
4. What should be returned if k is 1?
   • If k is 1, the function should return the maximum value of the array since picking one element will yield its own value as the OR result.

Strategy

• To solve this problem, we need to evaluate the K-or efficiently.
• Starting from the highest bit position, we will try to build the maximum possible bitwise OR.
• This can be achieved by considering each bit position from the most significant to the least significant bit and checking if selecting elements that have this bit set can form a valid OR.

Code

#include <iostream>
#include <vector>
#include <algorithm>

int findKOrOfArray(const std::vector<int>& arr, int k) {
    int n = arr.size();
    if (k == 1) {
        return *std::max_element(arr.begin(), arr.end());
    }
    
    int max_or = 0;
    for (int bit = 31; bit >= 0; --bit) {
        std::vector<int> candidates;
        for (int num : arr) {
            if (num & (1 << bit)) {
                candidates.push_back(num);
            }
        }
        
        if (candidates.size() >= k) {
            max_or |= (1 << bit);
            arr = std::move(candidates);
        }
    }

    return max_or;
}

int main() {
    std::vector<int> arr = {3, 6, 9, 5};
    int k = 2;
    std::cout << "The K-or of the array is: " << findKOrOfArray(arr, k) << std::endl;
    return 0;
}

Explanation and Time Complexity

Explanation

1. Initial Check:
   • If k equals 1, return the maximum element since OR’ing one number results in the number itself.
2. Bitwise OR Calculation:
   • Loop through each bit position starting from the most significant bit (31st bit for 32-bit integers).
   • For each bit position, filter out elements that have this bit set.
   • If the number of elements with the current bit set is at least k, update the max_or to include this bit and continue with the filtered list of elements.

Time Complexity

• Overall Complexity:
  • Each bit position is checked resulting in 32 iterations (constant time complexity, O(1)).
  • For each iteration, we might go through the array and filter elements, leading to a total complexity around O(31 * n), which is essentially O(n) due to constant multiplication.

Thus, the overall time complexity is O(n) where n is the number of elements in the array. This is efficient enough for large arrays up to the order of (10^5).

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?