Subsets with MEX in Range
Problem Overview
The MEX of a subset is the smallest missing non negative integer, and the empty subset has MEX 0.
Intuition
The MEX of a subset is the smallest missing non negative integer, and the empty subset has MEX 0. A subset has MEX k exactly when every value from 0 through k minus 1 appears at least once and k itself is left out. Each value below k has freq copies, and at least one copy must be taken, which can happen in 2 to the freq minus 1 ways. Every value above k, and every negative value, may be kept or dropped without changing that MEX. Those free choices contribute a power of two. The product for the required values grows by one integer as k increases, so each MEX in the range is scored from the previous one. The MEX of an array of n elements cannot exceed n, and it cannot pass the first missing value, so the scan stops there.
Algorithm
- 1Return 0 when the range is empty or its lower end is above n. Raise a negative lower end to 0.
- 2Count how often each value from 0 through min(r, n) appears, and precompute the powers of two up to 2 to the n.
- 3Walk the values below l. If one of them is missing, return 0. Otherwise multiply in 2 to the freq minus 1.
- 4For each k from l through the bound, add the required product times 2 to the power of the leftover elements.
- 5Stop when k itself is missing, then return the total modulo 1000000007.
Example Walkthrough
Input: arr = [2, 0, 1, 0], l = 1, r = 2
- 1. MEX 1 needs at least one 0 and no 1. The two zeros and the free 2 give 6 such subsets.
- 2. MEX 2 needs at least one 0, the 1, and no 2. The two zeros give 3 such subsets.
- 3. The subsets that also keep 2 have MEX 3, which is outside the range. The total is 6 plus 3, which is 9.
Output: 9
Common Pitfalls
- • The empty subset has MEX 0. A range that includes 0 must count every subset that contains no zero.
- • A missing value below l makes every MEX in the range impossible. The answer is 0.
- • Values larger than n, and negative values, never fill a MEX slot. They still double the count of every subset that ignores them.
- • Once a value is missing, no larger MEX is possible. Continuing the scan would add nothing.
// Approach: A subset has MEX k when every value below k appears at least
// once and k itself is absent. Values above k, and negative values, may be
// kept or dropped freely. The product of (2^freq - 1) for 0 through k - 1
// grows by one value at a time, and the free choices are the remaining
// elements. MEX cannot exceed n, and it cannot pass the first missing value.
// Complexity: O(n + min(r, n)) time, O(n) extra space.
class Solution {
public int cntSubsets(int[] arr, int l, int r) {
int n = arr.length;
if (r < 0 || l > r)
return 0;
if (l < 0)
l = 0;
if (l > n)
return 0;
final long MOD = 1000000007L;
int bound = Math.min(r, n);
int[] freq = new int[bound + 1];
for (int x : arr)
if (x >= 0 && x <= bound)
freq[x]++;
long[] pow2 = new long[n + 1];
pow2[0] = 1;
for (int i = 1; i <= n; i++)
pow2[i] = pow2[i - 1] * 2 % MOD;
long answer = 0;
long required = 1;
int seen = 0;
for (int k = 0; k < l; k++) {
if (freq[k] == 0)
return 0;
required = required * (pow2[freq[k]] - 1) % MOD;
seen += freq[k];
}
for (int k = l; k <= bound; k++) {
int count = freq[k];
answer = (answer + required * pow2[n - seen - count]) % MOD;
if (count == 0)
break;
required = required * (pow2[count] - 1) % MOD;
seen += count;
}
return (int) answer;
}
}