Introduction

The problem is to count how many non-empty subsequences of a numeric string form a number that is divisible by n.

For example:

s = "1234"
n = 4

The subsequences that are divisible by 4 are:

4
12
24
124

Therefore, the answer is:

4

The important challenge is that the string can be large, and the subsequences can be exponentially many. If the string has L digits, there can be up to 2^L - 1 non-empty subsequences.

So, generating every subsequence is not practical.

The efficient solution uses Dynamic Programming based on remainders.

1. Key Observation

We do not need to store the complete value of every subsequence.

Suppose we already have a number with remainder r when divided by n.

If we append a digit d to that number, the new number becomes:

oldNumber × 10 + d

Therefore, its new remainder is:

(oldRemainder × 10 + d) % n

For example, suppose:

n = 4
old remainder = 1
digit = 2

Appending 2 gives:

12

The new remainder is:

(1 × 10 + 2) % 4
= 12 % 4
= 0

So 12 is divisible by 4.

This observation allows us to avoid storing potentially huge numbers.

2. DP Definition

We use an array:

long[] dp = new long[n];

Here:

dp[r]

represents the number of non-empty subsequences whose value has remainder r when divided by n.

For example, if:

n = 4

then we have:

dp[0] → subsequences divisible by 4
dp[1] → remainder 1
dp[2] → remainder 2
dp[3] → remainder 3

At the end, we need:

dp[0]

because remainder 0 means the number is divisible by n.

3. Processing Each Digit

Consider:

s = "1234"

We process one digit at a time.

For every digit, there are two possibilities.

Option 1: Start a new subsequence

If the current digit is 4, we can create:

"4"

Its remainder is:

4 % n

So we add one subsequence to that remainder.

Option 2: Append the digit to existing subsequences

Suppose we already have a subsequence with remainder r.

If the current digit is d, its new remainder becomes:

(r * 10 + d) % n

So we transfer the count from dp[r] to the new remainder.

4. Java Solution

class Solution {
    public int countSubsequences(String s, int n) {
        final int MOD = 1_000_000_007;

        long[] dp = new long[n];

        for (char ch : s.toCharArray()) {
            int digit = ch - '0';

            // Keep the previous DP values unchanged
            long[] next = dp.clone();

            // Start a new subsequence with the current digit
            int rem = digit % n;
            next[rem] = (next[rem] + 1) % MOD;

            // Append current digit to all existing subsequences
            for (int r = 0; r < n; r++) {
                if (dp[r] == 0) {
                    continue;
                }

                int newRem = (r * 10 + digit) % n;

                next[newRem] =
                    (next[newRem] + dp[r]) % MOD;
            }

            dp = next;
        }

        return (int) dp[0];
    }
}

5. Code Explanation

Step 1: MOD value

final int MOD = 1_000_000_007;

The number of subsequences can become extremely large.

Therefore, the problem asks us to return the answer modulo:

1,000,000,007

We apply modulo during every addition.

Step 2: Create DP array

long[] dp = new long[n];

There are only n possible remainders:

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

So we only need n DP states.

Initially there are no subsequences:

dp = [0, 0, ..., 0]

6. Convert Character to Digit

int digit = ch - '0';

The string contains characters.

For example:

ch = '7'

Then:

'7' - '0' = 7

So we get the integer digit.

7. Why Do We Clone dp?

This is an important part of the solution.

long[] next = dp.clone();

Suppose the current digit is 3.

We want to use this digit only once in each subsequence.

If we update dp directly, a newly created subsequence could immediately be used again during the same iteration.

That would incorrectly allow the same digit to appear multiple times.

For example, if the current character is only:

"3"

we should have only:

3

not:

33
333
3333

Using next prevents this problem.

dp represents the subsequences before using the current digit.

next represents the subsequences after using the current digit.

8. Starting a New Subsequence

int rem = digit % n;

next[rem] = (next[rem] + 1) % MOD;

Every digit can independently form a new subsequence.

For example:

s = "5"
n = 3

The subsequence:

5

has remainder:

5 % 3 = 2

Therefore:

dp[2] = 1

9. Extending Existing Subsequences

The main DP transition is:

for (int r = 0; r < n; r++) {
    if (dp[r] == 0) {
        continue;
    }

    int newRem = (r * 10 + digit) % n;

    next[newRem] =
        (next[newRem] + dp[r]) % MOD;
}

Suppose:

r = 2
digit = 4
n = 6

Then:

newRem = (2 × 10 + 4) % 6
       = 24 % 6
       = 0

So every subsequence having remainder 2 becomes a subsequence having remainder 0 after appending 4.

10. Dry Run

Let's take:

s = "1234"
n = 4

Initially:

dp = [0, 0, 0, 0]

Process 1

New subsequence:

1

Remainder:

1 % 4 = 1

So:

dp = [0, 1, 0, 0]

Process 2

We can create:

2

Remainder:

2

We can also extend:

1 → 12

Remainder:

(1 × 10 + 2) % 4
= 12 % 4
= 0

So we now have:

dp[0] = 1
dp[1] = 1
dp[2] = 1

The subsequences are:

12
1
2

Process 3

The existing subsequences can be extended:

12 → 123
1  → 13
2  → 23

And we can start:

3

The DP continues tracking only their remainders.

Process 4

The important divisible subsequences include:

4
12
24
124

Therefore:

dp[0] = 4

Final answer:

4

11. Why Does This Work?

The algorithm considers both possibilities for every character:

Don't use the current digit

and

Use the current digit

If we don't use it, the old subsequence count remains in next.

That's why we start with:

long[] next = dp.clone();

If we use it, we append the digit to every existing subsequence and update its remainder.

Additionally, we create a new subsequence containing only the current digit.

Therefore, every possible non-empty subsequence is counted exactly once.

12. Handling Duplicate Subsequences

Consider:

s = "330"
n = 6

There are two different occurrences of 3.

The subsequences:

30
30

have the same numeric value, but they come from different positions in the original string.

Both must be counted.

The DP naturally handles this because every character position is processed independently.

The expected answer is:

4

for:

30
30
330
0

13. Why Not Generate All Subsequences?

A string with L characters has:

2^L - 1

non-empty subsequences.

For example:

L = 10

gives:

2^10 - 1 = 1023

But:

L = 100

gives more than:

10^30

subsequences.

So generating all subsequences is impossible for large input.

The DP reduces the problem to only n remainder states for every character.

14. Complexity

The constraints specify:

|s| × n ≤ 10^6

For every character, we iterate through all n remainders.

Therefore:

Time Complexity = O(|s| × n)

We use two arrays of size n:

dp
next

Therefore:

Space Complexity = O(n)

This satisfies the required complexity.

15. Important Formula to Remember

The most important formula in this problem is:

newRemainder = (oldRemainder × 10 + digit) % n

This works because if:

number = X

and we append digit d, the new number is:

10X + d

Therefore:

(10X + d) % n

can be calculated using only the remainder of X:

(10 × (X % n) + d) % n

This is the key idea that makes the solution efficient.

Final Takeaway

This problem is a good example of remainder-based Dynamic Programming.

Instead of storing every subsequence or its complete numeric value, we store only:

How many subsequences produce each remainder?

The DP state is:

dp[r] = number of subsequences with remainder r

The transition is:

newRem = (r × 10 + digit) % n

And the final answer is:

dp[0]

because remainder 0 represents numbers divisible by n.

Time: O(|s| × n)
Space: O(n)
Approach: Dynamic Programming + Remainder Tracking