Count Subsequences Divisible by n

Problem Overview

Track how many non-empty subsequences form a number congruent to each residue mod n.

Intuition

Track how many non-empty subsequences form a number congruent to each residue mod n. Appending a digit d to a subsequence with residue r produces residue (10*r + d) mod n. You also always keep the option of not taking the digit, and of starting a brand-new one-digit subsequence. The answer is the count of residue 0.

Algorithm

1Let dp[r] be the number of subsequences with value ≡ r (mod n). Start with all zeros.
2For each digit d in s: copy dp into next (skip case).
3For every residue r with dp[r] > 0, add those ways to next[(10*r + d) % n].
4Add 1 to next[d % n] for the singleton subsequence made of this digit alone.
5Swap next into dp. After the last digit, return dp[0] mod 1e9+7.

Example Walkthrough

Input: s = "123", n = 3

1. Digit 1: singleton residue 1. dp = [0,1,0].
2. Digit 2: keep old, extend 1 to 12 ≡ 0, add singleton 2. dp = [1,1,1].
3. Digit 3: extend each residue, add singleton 3 ≡ 0. Residue 0 ends with 3 ways: "12", "3", "123".

Output: 3

Common Pitfalls

• Do not count the empty subsequence. Start dp at zeros and only increment when a digit is taken.
• Use (10L * r + d) % n to avoid int overflow when multiplying residues.
• Copy the previous dp before extending; updating in place would reuse the same digit twice in one pass.
• Reuse two arrays and swap instead of cloning a fresh array on every character.

Count Subsequences Divisible by n.java

Java

// Approach: dp[r] = number of non-empty subsequences whose decimal value is
// congruent to r (mod n). For each digit, either skip it (copy dp), append it
// to every existing subsequence (r -> (10*r + d) % n), or start a new one-
// digit subsequence. Answer is dp[0] mod 1e9+7.
// Complexity: O(|s| * n) time and O(n) extra space.

class Solution {

    public int countSubsequences(String s, int n) {
        final int MOD = 1_000_000_007;
        long[] dp = new long[n];
        long[] next = new long[n];

        for (int i = 0; i < s.length(); i++) {
            int d = s.charAt(i) - '0';
            System.arraycopy(dp, 0, next, 0, n);

            for (int r = 0; r < n; r++) {
                long ways = dp[r];
                if (ways == 0) {
                    continue;
                }
                int nr = (int) ((r * 10L + d) % n);
                next[nr] = (next[nr] + ways) % MOD;
            }

            int dr = d % n;
            next[dr] = (next[dr] + 1) % MOD;

            long[] tmp = dp;
            dp = next;
            next = tmp;
        }

        return (int) dp[0];
    }
}

Was this solution helpful?