Subsets with MEX in Range

1. Introduction

Given an integer array arr[] and a range [l, r], we need to count the number of subsets whose MEX (Minimum Excluded) value lies between l and r, inclusive.

The answer can be very large, so we return it modulo:

10^9 + 7

What is MEX?

The MEX of a set or subset is the smallest non-negative integer that does not appear in it.

For example:

Subset = {0, 1, 3}
MEX = 2

because 0 and 1 are present, but 2 is missing.

Another example:

Subset = {1, 2, 3}
MEX = 0

because 0 is not present.

For an empty subset:

MEX = 0

Suppose:

arr = [2, 0, 1, 0]
l = 1
r = 2

We need to count all subsets whose MEX is either:

1 or 2

Instead of generating every subset, which would take O(2^n), we can use the frequency of each number.

The key is to understand what is required for a subset to have exactly MEX = k.

For a subset to have MEX equal to k:

Condition 1: Every number smaller than k must exist

The subset must contain:

0, 1, 2, ..., k - 1

at least once.

For example, if:

MEX = 3

then the subset must contain:

0, 1, 2

Condition 2: k must not exist

The number k must be completely absent from the subset.

For:

MEX = 3

the subset cannot contain 3.

Condition 3: Numbers greater than k are optional

Any number greater than k can either be selected or not selected.

Therefore, every occurrence of a number greater than k gives two choices:

Select it
Don't select it

This is the most important part of the problem.

Suppose:

freq[0] = 2

There are two occurrences of 0.

If we need at least one 0, how many ways can we select them?

Each occurrence has two choices:

Select
Don't select

Therefore, the total number of ways is:

2^2 = 4

These choices are:

{}
{first 0}
{second 0}
{first 0, second 0}

But we need at least one zero, so we remove the empty choice:

2^2 - 1 = 3

Therefore:

Ways to select at least one occurrence of x
= 2^freq[x] - 1

This formula is the heart of the solution.

Suppose the frequency of each value is known.

For MEX k:

For values 0 to k-1

Each must appear at least once.

Therefore:

(2^freq[0] - 1)
×
(2^freq[1] - 1)
×
...
×
(2^freq[k-1] - 1)

For value k

It must not be selected.

Therefore:

1 way

For values greater than k

Every occurrence can be selected or not selected.

If there are greaterElements such elements:

2^greaterElements

Therefore:

ways(MEX = k)
=
[product of (2^freq[x] - 1), x = 0 ... k-1]
×
2^greaterElements

Consider:

arr = [2, 0, 1, 0]

Frequencies are:

freq[0] = 2
freq[1] = 1
freq[2] = 1

MEX = 1

For MEX 1:

• 0 must be present.

• 1 must not be present.

• 2 is optional.

There are two zeros.

Ways to select at least one zero:

2^2 - 1 = 3

There is one element greater than 1:

2

It can be selected or not:

2^1 = 2

Therefore:

Ways(MEX = 1)
= 3 × 2
= 6

MEX = 2

For MEX 2:

• 0 must be present.

• 1 must be present.

• 2 must not be present.

For zero:

2^2 - 1 = 3

For one:

2^1 - 1 = 1

There are no elements greater than 2.

Therefore:

Ways(MEX = 2)
= 3 × 1
= 3

Total:

6 + 3 = 9

An array of size n has:

2^n

possible subsets.

If:

n = 100000

generating all subsets is impossible.

Therefore, we need a mathematical counting approach.

Instead of looking at every subset, we look at the frequency of each value.

This reduces the problem to approximately:

O(n + r)

We don't need to calculate the entire product again for every MEX.

Suppose we already calculated:

waysRequired
=
(2^freq[0] - 1)
×
(2^freq[1] - 1)

When moving from:

MEX = 2

to:

MEX = 3

we only need to add the contribution of 2:

waysRequired *= (2^freq[2] - 1)

This allows us to calculate every MEX incrementally.

class Solution {

    static final long MOD = 1000000007L;

    public int cntSubsets(int arr[], int l, int r) {

        int n = arr.length;

        // Store frequency of every value
        int[] freq = new int[n + 1];

        for (int x : arr) {
            if (x <= n) {
                freq[x]++;
            }
        }

        // powers of 2
        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;

        /*
         * Product of:
         *
         * (2^freq[0] - 1)
         * (2^freq[1] - 1)
         * ...
         *
         * for values smaller than current MEX.
         */
        long waysRequired = 1;

        // Number of elements whose value is smaller
        // than the current MEX.
        int used = 0;

        for (int mex = 0; mex <= r; mex++) {

            /*
             * Elements greater than mex are optional.
             *
             * Total elements = n
             * Elements smaller than mex = used
             * Elements equal to mex = freq[mex]
             */
            int greaterElements =
                    n - used - freq[mex];

            /*
             * Number of subsets with exactly this MEX.
             */
            long ways =
                    (waysRequired * pow2[greaterElements]) % MOD;

            /*
             * Add only if MEX lies in [l, r].
             */
            if (mex >= l) {
                answer = (answer + ways) % MOD;
            }

            /*
             * To make the next MEX possible,
             * current mex must be present at least once.
             *
             * Number of ways:
             *
             * 2^freq[mex] - 1
             */
            long currentWays =
                    (pow2[freq[mex]] - 1 + MOD) % MOD;

            waysRequired =
                    (waysRequired * currentWays) % MOD;

            used += freq[mex];
        }

        return (int) answer;
    }
}

Step 1: Count Frequencies

int[] freq = new int[n + 1];

for (int x : arr) {
    if (x <= n) {
        freq[x]++;
    }
}

We store how many times each number occurs.

For:

[2, 0, 1, 0]

we get:

freq[0] = 2
freq[1] = 1
freq[2] = 1

Values greater than n cannot affect the MEX up to r, so they do not need frequency storage.

long[] pow2 = new long[n + 1];

pow2[0] = 1;

for (int i = 1; i <= n; i++) {
    pow2[i] = (pow2[i - 1] * 2) % MOD;
}

We frequently need:

2^freq[x]

Instead of calculating powers repeatedly, we precompute them.

For example:

pow2[0] = 1
pow2[1] = 2
pow2[2] = 4
pow2[3] = 8
pow2[4] = 16
...

This keeps the algorithm efficient.

long waysRequired = 1;

This variable stores the number of ways to select at least one occurrence of every number smaller than the current MEX.

Initially, there are no required numbers.

Therefore:

waysRequired = 1

When processing 0, it becomes:

waysRequired *= 2^freq[0] - 1

Then when processing 1:

waysRequired *= 2^freq[1] - 1

And so on.

This line is important:

int greaterElements =
        n - used - freq[mex];

At a particular MEX:

used

represents the number of array elements whose value is smaller than the current MEX.

freq[mex]

represents the number of occurrences of the MEX itself.

Therefore:

greaterElements
=
n - used - freq[mex]

These remaining elements have values greater than the current MEX.

Every one of them is optional, giving:

2^greaterElements

possibilities.

long ways =
        (waysRequired * pow2[greaterElements]) % MOD;

This combines two independent choices:

Required values

waysRequired

Every value smaller than MEX must occur at least once.

Optional values

2^greaterElements

Every value greater than MEX can be selected or skipped.

Therefore:

ways
=
waysRequired × 2^greaterElements

Suppose:

MEX = 2

Then 2 must be absent.

If there are freq[2] copies of 2, every one of them has only one valid choice:

Do not select it

So the number of choices is simply:

1

That's why there is no multiplication by 2^freq[mex].

After calculating the current MEX, we prepare for the next one:

long currentWays =
        (pow2[freq[mex]] - 1 + MOD) % MOD;

waysRequired =
        (waysRequired * currentWays) % MOD;

Why?

Suppose the current MEX is 2.

For the next MEX, 3, the number 2 must now be present.

Therefore, we need to select at least one occurrence of 2.

The number of ways is:

2^freq[2] - 1

We multiply this into waysRequired.

The problem asks for:

l <= MEX <= r

So:

if (mex >= l) {
    answer = (answer + ways) % MOD;
}

The loop already stops at r, so every calculated MEX is automatically:

MEX <= r

Therefore, checking:

mex >= l

is sufficient.

MEX 0 means:

0 is absent from the subset.

There are no required values smaller than 0.

Therefore:

waysRequired = 1

The number of elements greater than 0 can be freely selected.

So:

ways(MEX = 0)
=
2^(number of elements whose value > 0)

This also correctly counts the empty subset.

The maximum possible MEX of an array of size n is at most n.

Why?

To have MEX n, the subset must contain:

0, 1, 2, ..., n-1

which already requires n elements.

Therefore, values larger than n cannot become the MEX.

They are still optional elements, but since the problem guarantees:

r <= n

we only need to track frequencies up to n.

Time Complexity

Frequency calculation:

O(n)

Power precomputation:

O(n)

MEX processing:

O(r)

Total:

O(n + r)

Space Complexity

We use:

freq[]
pow2[]

Both require O(n) space.

Therefore:

O(n)

auxiliary space.

A common mistake is to use:

2^freq[x]

for a required value.

That includes the possibility of selecting zero occurrences.

For example, if:

freq[0] = 3

then:

2^3 = 8

includes:

select no zero

But for MEX 1, zero must be present.

Therefore we need:

2^3 - 1 = 7

The general rule is:

Required value:
2^frequency - 1

Optional value:
2^frequency

Forbidden value:
1

This is the most important pattern to remember.

The problem looks like a subset-generation problem, but generating all subsets is impossible because there can be 2^n subsets.

The key mathematical observation is to classify every value relative to the chosen MEX:

Value < MEX
    → must appear at least once
    → 2^freq - 1 choices

Value = MEX
    → must not appear
    → 1 choice

Value > MEX
    → completely optional
    → 2^freq choices

By maintaining the product for all required values incrementally, we can calculate the number of subsets for every possible MEX in linear time.

Thus, the final complexity is:

Time  : O(n + r)
Space : O(n)

This is a good example of how a seemingly exponential subset problem can be transformed into an efficient frequency + combinatorics solution.