What is the difficulty level of Pretty Subsets Count?

This problem is rated as medium difficulty in the Array / Hash Map / Bit Manipulation / Prefix XOR category.

Pretty Subsets Count

Given an integer array nums and an integer k, count contiguous subarrays where the XOR of all elements has at most k unset bits (0 bits) in its 32-bit binary representation. A subarray is pretty if its XOR value contains 32 - popcount(XOR) <= k zero bits. Return the total count of such subarrays.

Examples

Input: [[1,2,3,4],2]

Output: 7

Hints

The problem reduces to counting pairs `(i, j)` where the number of unset bits in `prefix[j+1] ^ prefix[i]` is at most `k`. To optimize, observe that the number of unset bits in a number `x` is `32 - popcount(x)`, where `popcount(x)` is the number of set bits in `x`. Thus, the condition becomes `32 - popcount(prefix[j+1] ^ prefix[i]) <= k`, which simplifies to `popcount(prefix[j+1] ^ prefix[i]) >= 32 - k`.

Use a frequency map to keep track of the prefix XOR values encountered so far. For each `prefix[j+1]`, iterate over all possible values `x` in the map and check if `popcount(prefix[j+1] ^ x) >= 32 - k`. To optimize further, note that the number of possible `x` values is limited (since XOR operations are involved), and precompute or memoize popcounts to avoid redundant calculations. The solution involves a trade-off between time and space complexity, balancing the use of the frequency map and popcount optimizations.