Shortest Subarray With OR at Least K II

Leetcode Problem:

• Shortest Subarray With OR at Least K II

Summary

• The problem requires finding the length of the shortest special subarray in the given array of non-negative integers and an integer k
• A special subarray is defined as an array where the bitwise OR of all its elements is at least k.

Approach

• The approach used is to use a bit manipulation technique to efficiently calculate the bitwise OR of all subarrays
• A custom _bit struct is created to store the count of 1s in the binary representation of each number
• The add and sub methods are used to update the count of 1s in the _bit struct
• The getNum method is used to calculate the bitwise OR of all numbers in the subarray
• The minimumSubarrayLength function uses two pointers to traverse the array and update the _bit struct accordingly
• If the bitwise OR of the subarray is greater than or equal to k, the length of the subarray is updated
• The function returns the length of the shortest special subarray or -1 if no special subarray exists.

Complexity

• O(n log n) due to the getNum method, where n is the size of the input array
• The add and sub methods are O(log n) and are called in a loop, so the overall time complexity is O(n log n)
• The space complexity is O(1) as the _bit struct only uses a constant amount of space.

Explanation

• The solution code first creates a custom _bit struct to store the count of 1s in the binary representation of each number
• The add and sub methods are used to update the count of 1s in the _bit struct
• The getNum method is used to calculate the bitwise OR of all numbers in the subarray
• The minimumSubarrayLength function uses two pointers to traverse the array and update the _bit struct accordingly
• If the bitwise OR of the subarray is greater than or equal to k, the length of the subarray is updated
• The function returns the length of the shortest special subarray or -1 if no special subarray exists.

Solution Code:

struct _bit{
    int cnt[32] = {0};
    void add(int num){
        int c = 0;
        while(num){
            if (num%2){
                cnt[c]++;
            }
            num /= 2;
            c++;
        }
    }
    void sub(int num){
        int c = 0;
        while(num){
            if (num %2){
                cnt[c]--;
            }
            num /= 2;
            c++;
        }
    }
    int getNum(){
        long long pow = 1;
        long long num = 0;
        for(int i = 0 ; i < 31; i++){
            int x = 0;
            if(cnt[i] > 0){
                x = 1;
            }
            num += pow * x;
            pow *= 2;
        }
        return num;
    }
};


class Solution {
public:
    _bit b;
    int minimumSubarrayLength(vector& nums, int k) {
        int res = nums.size()+1;
        
        int l = 0;
        int r = 0;
        if (k == 0 ) return 1;
        while(r < nums.size() && l <= r){
            int num = b.getNum();
            if(num >= k){
                res = min(res, r - l);
                b.sub(nums[l++]);
            } else {
                b.add(nums[r++]);
            }
        }
        int num = b.getNum();
        if(num >= k){
            res = min(res, r - l);
        } 
        while(l < nums.size()){
            num = b.getNum();
            if(num >= k){
                res = min(res, r - l);
                b.sub(nums[l++]);
            } else {
                break;
            }
        }
        
        if (res == nums.size() + 1) return -1;
        return res;
    }
};