shortest-subarray-with-or-at-least-k-i.cpp

// Time:  O(nlogr) = O(n * 30)
// Space: O(logr) = O(30)

// freq table, two pointers
class Solution {
public:
    int minimumSubarrayLength(vector<int>& nums, int k) {
        const auto& bit_length = [](int x) {
            return (x ? std::__lg(x) : -1) + 1;
        };
    
        const int total = accumulate(cbegin(nums), cend(nums), 0, [](const auto& x, const auto& y) {
            return x | y;
        });
        if (total < k) {
            return -1;
        }
        vector<int> cnt(bit_length(total));
        const auto& update = [&](int x, int d, int curr) {
            for (int i = 0; (1 << i) <= x; ++i) {
                if (!(x & (1 << i))) {
                    continue;
                }
                if (cnt[i] == 0) {
                    curr ^= 1 << i;
                }
                cnt[i] += d;
                if (cnt[i] == 0) {
                    curr ^= 1 << i;
                }
            }
            return curr;
        };

        int result = size(nums);
        for (int right = 0, left = 0, curr = 0; right < size(nums); ++right) {
            curr = update(nums[right], +1, curr);
            for (; left <= right && curr >= k; ++left) {
                result = min(result, right - left + 1);
                curr = update(nums[left], -1, curr);
            }
        }
        return result;
    }
};

// Time:  O(n^2)
// Space: O(1)
// brute force
class Solution2 {
public:
    int minimumSubarrayLength(vector<int>& nums, int k) {
        static const int INF = numeric_limits<int>::max();
    
        int result = INF;
        for (int left = 0; left < size(nums); ++left) {
            for (int right = left, curr = 0; right < size(nums); ++right) {
                curr |= nums[right];
                if (curr < k) {
                    continue;
                }
                result = min(result, right - left + 1);
                break;
            }
        }
        return result != INF ? result : -1;
    }
};