Count Subsequences Divisible by N Using Dynamic Programming in Java

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:

Code

s = "1234"
n = 4

The subsequences that are divisible by 4 are:

Code

Therefore, the answer is:

Code

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:

Code

oldNumber × 10 + d

Therefore, its new remainder is:

Code

(oldRemainder × 10 + d) % n

For example, suppose:

Code

n = 4
old remainder = 1
digit = 2

Appending 2 gives:

Code

The new remainder is:

Code

(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:

Java

long[] dp = new long[n];

Here:

Code

dp[r]

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

For example, if:

Code

n = 4

then we have:

Code

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

At the end, we need:

Java

dp[0]

because remainder 0 means the number is divisible by n.

3. Processing Each Digit

Consider:

Code

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:

Code

"4"

Its remainder is:

Code

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:

Code

(r * 10 + d) % n

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

4. Java Solution

Java

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

Java

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:

Code

1,000,000,007

We apply modulo during every addition.

Step 2: Create DP array

Java

long[] dp = new long[n];

There are only n possible remainders:

Code

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

So we only need n DP states.

Initially there are no subsequences:

Code

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

6. Convert Character to Digit

Java

int digit = ch - '0';

The string contains characters.

For example:

Java

ch = '7'

Then:

Java

'7' - '0' = 7

So we get the integer digit.

7. Why Do We Clone `dp`?

This is an important part of the solution.

Java

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:

Code

"3"

we should have only:

Code

not:

Code

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

Java

int rem = digit % n;

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

Every digit can independently form a new subsequence.

For example:

Code

s = "5"
n = 3

The subsequence:

Code

has remainder:

Code

5 % 3 = 2

Therefore:

Code

dp[2] = 1

9. Extending Existing Subsequences

The main DP transition is:

Java

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:

Code

r = 2
digit = 4
n = 6

Then:

Code

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:

Code

s = "1234"
n = 4

Initially:

Code

dp = [0, 0, 0, 0]

Process `1`

New subsequence:

Code

Remainder:

Code

1 % 4 = 1

So:

Code

dp = [0, 1, 0, 0]

Process `2`

We can create:

Code

Remainder:

Code

We can also extend:

Code

1 → 12

Remainder:

Code

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

So we now have:

Code

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

The subsequences are:

Code

12
1
2

Process `3`

The existing subsequences can be extended:

Code

12 → 123
1  → 13
2  → 23

And we can start:

Code

The DP continues tracking only their remainders.

Process `4`

The important divisible subsequences include:

Code

Therefore:

Code

dp[0] = 4

Final answer:

Code

11. Why Does This Work?

The algorithm considers both possibilities for every character:

Code

Don't use the current digit

and

Code

Use the current digit

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

That's why we start with:

Java

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:

Code

s = "330"
n = 6

There are two different occurrences of 3.

The subsequences:

Code

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:

Code

for:

Code

13. Why Not Generate All Subsequences?

A string with L characters has:

Code

2^L - 1

non-empty subsequences.

For example:

Code

L = 10

gives:

Code

2^10 - 1 = 1023

But:

Code

L = 100

gives more than:

Code

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:

Code

|s| × n ≤ 10^6

For every character, we iterate through all n remainders.

Therefore:

Code

Time Complexity = O(|s| × n)

We use two arrays of size n:

Java

dp
next

Therefore:

Code

Space Complexity = O(n)

This satisfies the required complexity.

15. Important Formula to Remember

The most important formula in this problem is:

Code

newRemainder = (oldRemainder × 10 + digit) % n

This works because if:

Code

number = X

and we append digit d, the new number is:

Code

10X + d

Therefore:

Code

(10X + d) % n

can be calculated using only the remainder of X:

Code

(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:

Code

How many subsequences produce each remainder?

The DP state is:

Code

dp[r] = number of subsequences with remainder r

The transition is:

Code

newRem = (r × 10 + digit) % n

And the final answer is:

Java

dp[0]

because remainder 0 represents numbers divisible by n.

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

Introduction

1. Key Observation

2. DP Definition

3. Processing Each Digit

Option 1: Start a new subsequence

Option 2: Append the digit to existing subsequences

4. Java Solution

5. Code Explanation

Step 1: MOD value

Step 2: Create DP array

6. Convert Character to Digit

7. Why Do We Clone dp?

8. Starting a New Subsequence

9. Extending Existing Subsequences

10. Dry Run

Process 1

Process 2

Process 3

Process 4

11. Why Does This Work?

12. Handling Duplicate Subsequences

13. Why Not Generate All Subsequences?

14. Complexity

15. Important Formula to Remember

Final Takeaway

7. Why Do We Clone `dp`?

Process `1`

Process `2`

Process `3`

Process `4`