Queries for number of array elements in a range with Kth Bit Set

Given an array arr[] of n positive integers and q queries, in which each query have an integer k. For each query, the task is to output the minimum size of subarray whose binary representation of each elements if concatenated will have at least k number of set bits. If no such array exist, print -1.

Examples:

Input : 
n = 4, arr[] = { 1, 2, 4, 8 }, q = 3
k1 = 1 
k2 = 2
k3 = 3

Output :
1
2
3

First observe, if a concatenation of binary representation of elements in a subarray of size S have k set bits then there must be a subarray of size S + 1 which will always have more or equal to k set bits. Minimum and maximum possible value of S can be 1 and n respectively.

So, we can apply binary search for each query to find the minimum length that have at least k set bits. So, first precompute number of set bits of all integers. Now, construct the prefix sum array, where prefixsum[i] contain sum of set bits of all array elements upto ith element. Then we can apply binary search to find minumum subarray size which satisfies the condition prefixsum[i+L] – prefixsum[i] >= k. If no such subarray exist, print “-1”.

Below is C++ implementation of this approach:

#include <bits/stdc++.h>
using namespace std;
const int N = 1000005;

// Return the number of set bits in a number
int countSetbits(int n)
{
    int cnt = 0;
    while(n)
    {
        n = n & (n - 1);
        cnt++;
    }
    return cnt;
}

// Count the number of set bits of the first N whole numbers
void precomputeSetbits(int sbit[])
{
    for(int i = 0; i < N; i++)
    {
        sbit[i] = countSetbits(i);
    }
}

// Calculate the prefix sum array of set bits
void calSum(int n, int sum[], int sbit[], int a[])
{
    sum[0] = 0;

    // Finding the prefix sum
    for(int i = 1; i <= n; i++)
    {
        sum[i] = sum[i - 1] + sbit[a[i - 1]];
    }
}

// Check if any subarray of size x has at least k set bits
bool check(int n, int x, int k, int sum[])
{
    for(int i = 0; i <= n - x; i++)
    {
        if((sum[i + x] - sum[i]) >= k)
        {
            return true;
        }
    }
    return false;
}

// Wrapper function
void wrapper(int n, int arr[], int q, int k[])
{
    int sbit[N];
    precomputeSetbits(sbit);

    int sum[N];
    calSum(n, sum, sbit, arr);

    for(int i = 0; i < q; i++)
    {
        // Binary search to find the minimum length.
        int lo = 1, hi = n, ans = -1;
        int mid;

        while (hi - lo >= 0)
        {
            mid = (lo + hi) / 2;
            if (check(n, mid, k[i], sum))
            {
                ans = mid;
                hi = mid - 1;
            }
            else
            {
                lo = mid + 1;
            }
        }
        printf("%d\n", ans);
    }
}

// Driven Program
int main()
{
    int n = 4;
    int arr[] = { 1, 2, 4, 8 };
    int q = 3;
    int k[] = { 1, 2, 3 };

    wrapper(n, arr, q, k);

    return 0;
}

Output:

1
2
3

Similar Reads