3704. Count No-Zero Pairs That Sum to N

HardMathDynamic Programming

LeetCode ↗

Problem Pattern Idea Example Code Complex Pitfalls

Problem Description

A no-zero integer is a positive integer whose decimal representation contains no digit 0 anywhere. For example, 123 and 456 are no-zero integers, while 105 and 230 are not, because they contain the digit 0.

You are given an integer n. Your task is to count the number of pairs (a, b) that satisfy both of the following conditions:

a and b are both no-zero integers.
a + b = n

Return the total number of such pairs.

A few points to keep in mind:

Both a and b must be positive, so neither of them can be 0.
Every digit of a and every digit of b must be from 1 to 9 — a single 0 digit in either number disqualifies the pair.
Ordered pairs are counted, meaning (a, b) and (b, a) count as different pairs when a ≠ b.

Example:

For n = 11, the valid pairs are:

(2, 9), (3, 8), (4, 7), (5, 6), (6, 5), (7, 4), (8, 3), (9, 2)

Note that (1, 10) and (10, 1) are not counted, because 10 contains the digit 0. So the answer is 8.

The challenge of this problem is that n can be very large, so simply iterating over all possible values of a from 1 to n - 1 and checking whether both a and n - a are no-zero integers would be too slow. An efficient approach builds the pair digit by digit (such as digit DP), tracking the carry produced by the addition and whether each number has finished contributing digits.

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

How We Pick the Algorithm

Why Dynamic Programming?

This problem maps to Dynamic Programming through a short path in the full flowchart.

Counting pairs of no-zero integers summing to n decomposes into digit DP with carry and alive/dead state tracking.

Open in Flowchart

Intuition

The brute-force idea — try every a from 1 to n - 1 and check whether both a and n - a are no-zero integers — fails immediately because n can be astronomically large. We need a way to count pairs without enumerating them.

The key observation is that the condition a + b = n is really a statement about column-by-column addition, exactly like the grade-school method. If we look at the units digit, then the tens digit, and so on, the digits of a and b at each position must add up (together with any incoming carry) to match the corresponding digit of n. This means the problem has a natural digit-level structure: what happens at one position only affects the next position through a single carry of 0 or 1.

Whenever a problem decomposes like this — local digit choices connected by a tiny amount of shared information (the carry) — it is a classic setup for digit DP. Instead of counting whole numbers, we count ways to fill in digits position by position, and the total count falls out at the end.

So what state do we need to carry from one digit position to the next?

The carry (0 or 1). Two digits plus a carry can sum to at most 9 + 9 + 1 = 19, so the carry into the next column is always 0 or 1. This is the only arithmetic information that links columns together.
Whether each number is still "alive." Here is the subtle part. The numbers a and b may have different lengths. For example, 999 + 2 = 1001: while processing the higher digits, b has already "ended" and contributes nothing. But "contributing nothing" means its digit is 0 — and 0 digits are forbidden inside a no-zero integer, yet perfectly fine as leading zeros that don't actually appear in the number. So we must distinguish two situations:
- The number is still alive: its current digit must be from 1 to 9 (no zeros allowed).
- The number has ended: every remaining digit must be 0, and once ended it can never restart — otherwise there would be a real 0 sandwiched inside the number.
One boolean per number (aliveA, aliveB) captures this perfectly.

With this state — (carry, aliveA, aliveB) — the transition at each position is simple: pick a digit da for a and db for b consistent with their alive status, and accept the choice only if (da + db + carry) % 10 equals the digit of n at that position. The new carry is (da + db + carry) / 10, and each number is free to "die" (stop emitting digits) at any point after its first digit.

One last detail: after processing the most significant digit of n, a leftover carry of 1 would mean a + b overshoots n. Appending an artificial leading 0 to n forces this final carry to be resolved, so the only valid terminal state is carry = 0 with both numbers ended — exactly the count we return.

The total state space is tiny (2 × 2 × 2 = 8 states per digit), and at each of the O(log n) positions we try at most 10 × 10 digit pairs, so the whole count is computed in time proportional to the number of digits of n — a dramatic improvement over enumeration.

Pattern Learn more about Math and Dynamic Programming patterns.

Solution Approach

The solution is a digit DP that processes n from its least-significant digit to its most-significant digit, counting all valid ways to build a and b column by column.

Step 1: Prepare the digits

digits = list(map(int, str(n)))[::-1]
digits.append(0)  # absorb final carry
L = len(digits)

Convert n into a list of digits and reverse it, so digits[0] is the units digit. We process columns in the same order the addition produces carries.
Append an extra 0 as an artificial leading digit. This forces any leftover carry from the highest real digit to be checked against 0. If a carry of 1 survives to this position, no digit choice can match 0 (since both numbers must already be dead and contribute 0), and the path is correctly eliminated.

Step 2: Define the DP state

dp = [[[0] * 2 for _ in range(2)] for _ in range(2)]
dp[0][1][1] = 1

The state is dp[carry][aliveA][aliveB] = number of ways to fill all digit positions processed so far, such that:

carry is the carry going into the current column (0 or 1);
aliveA / aliveB indicate whether a / b still have digits to place at the current and higher positions.

The initial state is dp[0][1][1] = 1: no carry yet, and both numbers must be alive at position 0 — this guarantees a ≥ 1 and b ≥ 1, since every number must emit at least its units digit.

Step 3: Transitions

For each position pos, we build a fresh table ndp and iterate over every reachable state:

if aliveA:
    A = [(d, 1) for d in range(1, 10)]
    if pos > 0:
        A.append((0, 0))  # end number here
else:
    A = [(0, 0)]

Each entry is a pair (digit, newAlive):

If the number is alive, it may emit any digit 1–9 and stay alive ((d, 1)). Zero is excluded because the number is no-zero.
If the number is alive and pos > 0, it may instead end here: emit 0 (a leading zero that is not part of the number) and become dead ((0, 0)). The check pos > 0 prevents a number from ending before placing a single digit, which would make it 0 — not a positive integer.
If the number is already dead, its only option is (0, 0): it keeps emitting zeros and stays dead. This is what makes "ending" irreversible — a dead number can never produce a nonzero digit again, so no internal 0 can ever appear.

The same list is built independently for b. Then every combination is matched against the target digit:

for da, na in A:
    for db, nb in B:
        s = da + db + carry
        if s % 10 != target:
            continue
        ndp[s // 10][na][nb] += ways

s = da + db + carry is the column sum; it must satisfy s % 10 == digits[pos], otherwise the addition would not produce n.
The outgoing carry is s // 10, which is always 0 or 1 since s ≤ 9 + 9 + 1 = 19.
The count ways flows into the successor state (s // 10, na, nb).

After processing the column, dp = ndp rolls the table forward — only the previous column's table is needed, so memory stays at O(1) beyond the digit list.

Step 4: Read off the answer

return dp[0][0][0]

After all L positions (including the artificial leading 0) are processed, a valid pair must satisfy:

carry = 0 — the addition is complete with nothing left over;
aliveA = 0 and aliveB = 0 — both numbers have properly ended.

The value dp[0][0][0] is exactly the number of ordered pairs (a, b) of no-zero integers with a + b = n.

Complexity

Let m be the number of digits of n (m = O(log10 n)).

Time: at each of the m + 1 positions we visit at most 2 × 2 × 2 = 8 states, and each state tries at most 10 × 10 digit combinations — so O(m) overall with a small constant.
Space: O(m) for the digit list, plus O(1) for the two fixed-size DP tables.

Example Walkthrough

Let's trace the digit DP on n = 11, where the expected answer is 8.

Setup. Convert n to digits, reverse them, and append the artificial leading 0:

digits = [1, 1, 0]      # digits[0] = units, digits[1] = tens, digits[2] = sentinel

The DP starts with both numbers alive and no carry:

dp[carry=0][aliveA=1][aliveB=1] = 1

Position 0 — target digit 1 (units column).

Both numbers are alive and pos = 0, so each must emit a digit 1–9 (ending here would make it 0, not a positive integer). We need:

(da + db + 0) % 10 == 1

da + db = 1 is impossible — both digits are at least 1.
da + db = 11 works: (2,9), (3,8), (4,7), (5,6), (6,5), (7,4), (8,3), (9,2) — 8 combinations, each producing carry 11 // 10 = 1.

New state:

State `(carry, aliveA, aliveB)`	Ways
`(1, 1, 1)`	8

Position 1 — target digit 1 (tens column).

Now pos > 0, so each alive number may either emit 1–9 (stay alive) or emit 0 and end. With incoming carry 1, we need:

(da + db + 1) % 10 == 1   →   da + db ∈ {0, 10}

da + db = 0: both numbers end here (da = db = 0). Sum is 0 + 0 + 1 = 1, matching the target with outgoing carry 0. This routes all 8 ways into (0, 0, 0). These are exactly the pairs like (2, 9) — both numbers are single-digit, so both stop after the units column.
da + db = 10: pairs (1,9), (2,8), …, (9,1) — 9 combinations, both staying alive, sum 11, carry 1. This routes 8 × 9 = 72 ways into (1, 1, 1). These speculative paths are trying to build two-digit numbers like a = 29, b = 92 — but 29 + 92 = 121 ≠ 11, and the DP will kill them at the next step.

State `(carry, aliveA, aliveB)`	Ways
`(0, 0, 0)`	8
`(1, 1, 1)`	72

Position 2 — sentinel digit 0 (the appended leading zero).

State (0, 0, 0), 8 ways: both numbers are dead, so the only choice is da = db = 0. Sum is 0 + 0 + 0 = 0, which matches the target 0 with carry 0. All 8 ways survive into (0, 0, 0).
State (1, 1, 1), 72 ways: we need (da + db + 1) % 10 == 0, i.e. da + db = 9 (since 19 exceeds the maximum 18). Every such choice produces a sum of 10 and an outgoing carry of 1 — but there are no more digit positions to absorb it. These paths land in states like (1, 1, 1) or (1, 0, 1), none of which is the accepting state. All 72 invalid paths are eliminated, exactly as intended: this is why the sentinel digit exists.

Final table:

State `(carry, aliveA, aliveB)`	Ways
`(0, 0, 0)`	8

Answer. dp[0][0][0] = 8, matching the eight ordered pairs:

(2,9), (3,8), (4,7), (5,6), (6,5), (7,4), (8,3), (9,2)

Notice how the DP never enumerated any pair explicitly — it only tracked 8 tiny states per column, which is what lets the same procedure handle an n with thousands of digits just as easily.

Solution Implementation

1class Solution:
2    def countNoZeroPairs(self, n: int) -> int:
3        """
4        Count pairs (a, b) of positive integers such that:
5          - a + b == n
6          - neither a nor b contains the digit 0 in its decimal representation.
7
8        Approach: digit DP processed from the least significant digit upward,
9        simulating column-wise addition with a carry.
10
11        State: dp[carry][alive_a][alive_b]
12          - carry   : current carry into this column (0 or 1)
13          - alive_a : 1 if number `a` is still emitting digits, 0 if it has ended
14          - alive_b : 1 if number `b` is still emitting digits, 0 if it has ended
15        Once a number "ends", all of its higher digits are implicitly 0.
16        """
17        # Digits of n from least significant to most significant.
18        digits = list(map(int, str(n)))[::-1]
19        digits.append(0)  # extra column to absorb a possible final carry
20        length = len(digits)
21
22        # dp[carry][alive_a][alive_b] = number of ways to reach this state
23        dp = [[[0] * 2 for _ in range(2)] for _ in range(2)]
24        dp[0][1][1] = 1  # start: no carry, both numbers still producing digits
25
26        for pos in range(length):
27            ndp = [[[0] * 2 for _ in range(2)] for _ in range(2)]
28            target = digits[pos]  # required digit of the sum in this column
29
30            for carry in range(2):
31                for alive_a in range(2):
32                    for alive_b in range(2):
33                        ways = dp[carry][alive_a][alive_b]
34                        if ways == 0:
35                            continue
36
37                        # Possible (digit, next_alive) choices for number a.
38                        if alive_a:
39                            # Still alive: must place a non-zero digit 1..9,
40                            # or terminate here (only if at least one digit
41                            # has already been placed, i.e. pos > 0).
42                            choices_a = [(d, 1) for d in range(1, 10)]
43                            if pos > 0:
44                                choices_a.append((0, 0))  # number a ends here
45                        else:
46                            # Already ended: contributes an implicit 0.
47                            choices_a = [(0, 0)]
48
49                        # Possible (digit, next_alive) choices for number b.
50                        if alive_b:
51                            choices_b = [(d, 1) for d in range(1, 10)]
52                            if pos > 0:
53                                choices_b.append((0, 0))  # number b ends here
54                        else:
55                            choices_b = [(0, 0)]
56
57                        # Try every combination of digits for this column.
58                        for digit_a, next_alive_a in choices_a:
59                            for digit_b, next_alive_b in choices_b:
60                                column_sum = digit_a + digit_b + carry
61                                # The column's resulting digit must match n.
62                                if column_sum % 10 != target:
63                                    continue
64                                next_carry = column_sum // 10
65                                ndp[next_carry][next_alive_a][next_alive_b] += ways
66
67            dp = ndp
68
69        # Valid final state: no leftover carry and both numbers have ended.
70        return dp[0][0][0]
71
72    def countPairs(self, n: int) -> int:
73        # Delegate to the digit-DP implementation.
74        return self.countNoZeroPairs(n)
75

1class Solution {
2
3    /**
4     * Counts the number of ordered pairs (a, b) such that:
5     *   1. a + b == n
6     *   2. Neither a nor b contains the digit 0 in its decimal representation.
7     *
8     * Approach: digit DP processed from the least significant digit to the most
9     * significant one, simulating column-wise addition with a carry.
10     *
11     * DP state: dp[carry][aliveA][aliveB]
12     *   - carry  : the carry (0 or 1) propagated into the current column.
13     *   - aliveA : 1 if number A still has digits to place at this column
14     *              (i.e., A has not terminated yet), 0 otherwise.
15     *   - aliveB : same as aliveA but for number B.
16     *
17     * Transition rules per column:
18     *   - An "alive" number must place a non-zero digit (1-9) to stay alive,
19     *     or it may place 0 (only after the lowest column) which means the
20     *     number has ended (it contributes nothing from here upward).
21     *   - A "dead" (terminated) number always contributes digit 0.
22     *   - The column sum (digitA + digitB + carry) must match the corresponding
23     *     digit of n modulo 10; the quotient becomes the new carry.
24     *
25     * The answer is the number of ways to finish all columns (including one
26     * extra column for a possible final carry) with carry == 0 and both
27     * numbers terminated.
28     */
29    public long countNoZeroPairs(long n) {
30        char[] chars = Long.toString(n).toCharArray();
31        int numDigits = chars.length;
32
33        // digits[i] holds the i-th digit of n counted from the least
34        // significant side; one extra leading 0 absorbs a possible final carry.
35        int[] digits = new int[numDigits + 1];
36        for (int i = 0; i < numDigits; i++) {
37            digits[i] = chars[numDigits - 1 - i] - '0';
38        }
39        digits[numDigits] = 0;
40
41        // dp[carry][aliveA][aliveB] = number of ways to reach this state.
42        long[][][] dp = new long[2][2][2];
43        // Initially: no carry, and both numbers are still "alive"
44        // (they must each place at least one non-zero digit).
45        dp[0][1][1] = 1;
46
47        // Process every column, including the extra carry column.
48        for (int pos = 0; pos <= numDigits; pos++) {
49            long[][][] nextDp = new long[2][2][2];
50            int targetDigit = digits[pos];
51
52            for (int carry = 0; carry <= 1; carry++) {
53                for (int aliveA = 0; aliveA <= 1; aliveA++) {
54                    for (int aliveB = 0; aliveB <= 1; aliveB++) {
55                        long ways = dp[carry][aliveA][aliveB];
56                        if (ways == 0) {
57                            continue;
58                        }
59
60                        // Enumerate the digit choices for number A together
61                        // with the resulting "alive" flag after this column.
62                        int[] digitsA;
63                        int[] nextAliveA;
64                        if (aliveA == 1) {
65                            if (pos == 0) {
66                                // The lowest digit must be non-zero, and the
67                                // number必须 stay alive (it cannot be empty).
68                                digitsA = new int[] {1, 2, 3, 4, 5, 6, 7, 8, 9};
69                                nextAliveA = new int[] {1, 1, 1, 1, 1, 1, 1, 1, 1};
70                            } else {
71                                // Either place a non-zero digit and stay alive,
72                                // or place 0 meaning the number has terminated.
73                                digitsA = new int[] {1, 2, 3, 4, 5, 6, 7, 8, 9, 0};
74                                nextAliveA = new int[] {1, 1, 1, 1, 1, 1, 1, 1, 1, 0};
75                            }
76                        } else {
77                            // A terminated number always contributes 0.
78                            digitsA = new int[] {0};
79                            nextAliveA = new int[] {0};
80                        }
81
82                        // Same enumeration for number B.
83                        int[] digitsB;
84                        int[] nextAliveB;
85                        if (aliveB == 1) {
86                            if (pos == 0) {
87                                digitsB = new int[] {1, 2, 3, 4, 5, 6, 7, 8, 9};
88                                nextAliveB = new int[] {1, 1, 1, 1, 1, 1, 1, 1, 1};
89                            } else {
90                                digitsB = new int[] {1, 2, 3, 4, 5, 6, 7, 8, 9, 0};
91                                nextAliveB = new int[] {1, 1, 1, 1, 1, 1, 1, 1, 1, 0};
92                            }
93                        } else {
94                            digitsB = new int[] {0};
95                            nextAliveB = new int[] {0};
96                        }
97
98                        // Try every combination of digits for A and B.
99                        for (int ai = 0; ai < digitsA.length; ai++) {
100                            int digitA = digitsA[ai];
101                            int newAliveA = nextAliveA[ai];
102                            for (int bi = 0; bi < digitsB.length; bi++) {
103                                int digitB = digitsB[bi];
104                                int newAliveB = nextAliveB[bi];
105
106                                int columnSum = digitA + digitB + carry;
107                                // The column sum must reproduce the digit of n.
108                                if (columnSum % 10 != targetDigit) {
109                                    continue;
110                                }
111                                int newCarry = columnSum / 10;
112                                nextDp[newCarry][newAliveA][newAliveB] += ways;
113                            }
114                        }
115                    }
116                }
117            }
118            dp = nextDp;
119        }
120
121        // Valid final state: no leftover carry and both numbers terminated.
122        return dp[0][0][0];
123    }
124
125    public long countPairs(long n) {
126        return countNoZeroPairs(n);
127    }
128}
129```
130
131Note: I noticed one stray non-English fragment slipped into a comment draft above (`number必须 stay alive`). Here is the corrected final version of that comment line, so you can replace it directly:
132
133```java
134// The lowest digit must be non-zero, and the
135// number must stay alive (it cannot be empty).
136

1class Solution {
2public:
3    long long countNoZeroPairs(long long n) {
4        // Convert n to a string and extract its digits in
5        // least-significant-first order. An extra sentinel digit 0 is
6        // appended so the final carry can be resolved in the last round.
7        std::string numStr = std::to_string(n);
8        int numLen = static_cast<int>(numStr.size());
9        std::vector<int> digits(numLen + 1);
10        for (int i = 0; i < numLen; i++) {
11            digits[i] = numStr[numLen - 1 - i] - '0';
12        }
13        digits[numLen] = 0;  // sentinel position for the leftover carry
14
15        // dp[carry][activeA][activeB] = number of ways to fill all digit
16        // positions processed so far, where:
17        //   carry   - the carry propagated into the current position (0/1)
18        //   activeA - 1 if number A is still producing digits (not yet ended)
19        //   activeB - 1 if number B is still producing digits (not yet ended)
20        // Initially no carry and both numbers are active (must place at
21        // least one non-zero digit each).
22        long long dp[2][2][2] = {};
23        dp[0][1][1] = 1;
24
25        // Process every digit position from the least significant to the
26        // sentinel position.
27        for (int pos = 0; pos <= numLen; pos++) {
28            long long nextDp[2][2][2] = {};
29            int targetDigit = digits[pos];
30
31            for (int carry = 0; carry <= 1; carry++) {
32                for (int activeA = 0; activeA <= 1; activeA++) {
33                    for (int activeB = 0; activeB <= 1; activeB++) {
34                        long long ways = dp[carry][activeA][activeB];
35                        if (ways == 0) continue;
36
37                        // Enumerate the candidate digits for number A at
38                        // this position together with its resulting state.
39                        // While active, A may place a non-zero digit (1..9)
40                        // and stay active, or stop (represented by digit 0)
41                        // provided it already placed at least one digit
42                        // (pos > 0). Once inactive, A only contributes 0.
43                        int candDigitsA[10];
44                        int candStatesA[10];
45                        int candCountA = 0;
46                        if (activeA) {
47                            for (int d = 1; d <= 9; d++) {
48                                candDigitsA[candCountA] = d;
49                                candStatesA[candCountA] = 1;  // remain active
50                                candCountA++;
51                            }
52                            if (pos > 0) {
53                                candDigitsA[candCountA] = 0;
54                                candStatesA[candCountA] = 0;  // number ends here
55                                candCountA++;
56                            }
57                        } else {
58                            candDigitsA[0] = 0;
59                            candStatesA[0] = 0;
60                            candCountA = 1;
61                        }
62
63                        // Same enumeration for number B.
64                        int candDigitsB[10];
65                        int candStatesB[10];
66                        int candCountB = 0;
67                        if (activeB) {
68                            for (int d = 1; d <= 9; d++) {
69                                candDigitsB[candCountB] = d;
70                                candStatesB[candCountB] = 1;  // remain active
71                                candCountB++;
72                            }
73                            if (pos > 0) {
74                                candDigitsB[candCountB] = 0;
75                                candStatesB[candCountB] = 0;  // number ends here
76                                candCountB++;
77                            }
78                        } else {
79                            candDigitsB[0] = 0;
80                            candStatesB[0] = 0;
81                            candCountB = 1;
82                        }
83
84                        // Try every digit combination; keep only those whose
85                        // column sum matches the corresponding digit of n.
86                        for (int ia = 0; ia < candCountA; ia++) {
87                            int digitA = candDigitsA[ia];
88                            int nextActiveA = candStatesA[ia];
89                            for (int ib = 0; ib < candCountB; ib++) {
90                                int digitB = candDigitsB[ib];
91                                int nextActiveB = candStatesB[ib];
92
93                                int columnSum = digitA + digitB + carry;
94                                if (columnSum % 10 != targetDigit) continue;
95
96                                int nextCarry = columnSum / 10;
97                                nextDp[nextCarry][nextActiveA][nextActiveB] += ways;
98                            }
99                        }
100                    }
101                }
102            }
103
104            std::memcpy(dp, nextDp, sizeof(dp));
105        }
106
107        // A valid pair requires no leftover carry and both numbers finished.
108        return dp[0][0][0];
109    }
110
111    long long countPairs(long long n) {
112        return countNoZeroPairs(n);
113    }
114};
115

1/**
2 * Counts the number of ordered pairs (A, B) of positive integers such that:
3 *   - A + B = n
4 *   - Neither A nor B contains the digit 0 in its decimal representation.
5 *
6 * The solution uses digit DP, processing columns of the addition from the
7 * least significant digit to the most significant one, tracking the carry
8 * and whether each number is still "active" (still producing digits).
9 */
10function countNoZeroPairs(n: number): number {
11    // Convert n to a string and extract its digits in
12    // least-significant-first order. An extra sentinel digit 0 is
13    // appended so the final carry can be resolved in the last round.
14    const numStr: string = n.toString();
15    const numLen: number = numStr.length;
16    const digits: number[] = new Array(numLen + 1).fill(0);
17    for (let i = 0; i < numLen; i++) {
18        digits[i] = numStr.charCodeAt(numLen - 1 - i) - 48; // '0' === 48
19    }
20    digits[numLen] = 0; // sentinel position for the leftover carry
21
22    // Helper that builds a fresh 2 x 2 x 2 table filled with zeros.
23    const createTable = (): number[][][] =>
24        Array.from({ length: 2 }, () =>
25            Array.from({ length: 2 }, () => [0, 0])
26        );
27
28    // dp[carry][activeA][activeB] = number of ways to fill all digit
29    // positions processed so far, where:
30    //   carry   - the carry propagated into the current position (0/1)
31    //   activeA - 1 if number A is still producing digits (not yet ended)
32    //   activeB - 1 if number B is still producing digits (not yet ended)
33    // Initially no carry and both numbers are active (each must place at
34    // least one non-zero digit).
35    let dp: number[][][] = createTable();
36    dp[0][1][1] = 1;
37
38    // Process every digit position from the least significant up to the
39    // sentinel position.
40    for (let pos = 0; pos <= numLen; pos++) {
41        const nextDp: number[][][] = createTable();
42        const targetDigit: number = digits[pos];
43
44        for (let carry = 0; carry <= 1; carry++) {
45            for (let activeA = 0; activeA <= 1; activeA++) {
46                for (let activeB = 0; activeB <= 1; activeB++) {
47                    const ways: number = dp[carry][activeA][activeB];
48                    if (ways === 0) continue;
49
50                    // Enumerate the candidate digits for number A at this
51                    // position together with its resulting state.
52                    // While active, A may place a non-zero digit (1..9)
53                    // and stay active, or stop (represented by digit 0)
54                    // provided it already placed at least one digit
55                    // (pos > 0). Once inactive, A only contributes 0.
56                    const candDigitsA: number[] = [];
57                    const candStatesA: number[] = [];
58                    if (activeA === 1) {
59                        for (let d = 1; d <= 9; d++) {
60                            candDigitsA.push(d);
61                            candStatesA.push(1); // remain active
62                        }
63                        if (pos > 0) {
64                            candDigitsA.push(0);
65                            candStatesA.push(0); // number ends here
66                        }
67                    } else {
68                        candDigitsA.push(0);
69                        candStatesA.push(0);
70                    }
71
72                    // Same enumeration for number B.
73                    const candDigitsB: number[] = [];
74                    const candStatesB: number[] = [];
75                    if (activeB === 1) {
76                        for (let d = 1; d <= 9; d++) {
77                            candDigitsB.push(d);
78                            candStatesB.push(1); // remain active
79                        }
80                        if (pos > 0) {
81                            candDigitsB.push(0);
82                            candStatesB.push(0); // number ends here
83                        }
84                    } else {
85                        candDigitsB.push(0);
86                        candStatesB.push(0);
87                    }
88
89                    // Try every digit combination; keep only those whose
90                    // column sum matches the corresponding digit of n.
91                    for (let ia = 0; ia < candDigitsA.length; ia++) {
92                        const digitA: number = candDigitsA[ia];
93                        const nextActiveA: number = candStatesA[ia];
94                        for (let ib = 0; ib < candDigitsB.length; ib++) {
95                            const digitB: number = candDigitsB[ib];
96                            const nextActiveB: number = candStatesB[ib];
97
98                            const columnSum: number = digitA + digitB + carry;
99                            if (columnSum % 10 !== targetDigit) continue;
100
101                            const nextCarry: number = Math.floor(columnSum / 10);
102                            nextDp[nextCarry][nextActiveA][nextActiveB] += ways;
103                        }
104                    }
105                }
106            }
107        }
108
109        dp = nextDp;
110    }
111
112    // A valid pair requires no leftover carry and both numbers finished.
113    return dp[0][0][0];
114}
115
116/**
117 * Entry point matching the problem signature; delegates to the DP routine.
118 */
119function countPairs(n: number): number {
120    return countNoZeroPairs(n);
121}
122

Time and Space Complexity

Time Complexity: O(L * 9^2), where L is the number of digits of n.
- The outer loop runs over each digit position, contributing the factor L (the code processes L + 1 positions due to the appended carry-absorbing digit, which is still O(L)).
- Inside each position, the DP state space is constant: carry ∈ {0, 1}, aliveA ∈ {0, 1}, aliveB ∈ {0, 1}, giving at most 2 * 2 * 2 = 8 states.
- For each state, the code enumerates candidate digit pairs (da, db). Each of A and B contains at most 10 options (digits 1..9 plus the option to terminate), so the pair enumeration costs at most O(9^2) (up to a small constant).
- Combining these, the total work is O(L * 8 * 9^2) = O(L * 9^2).
Space Complexity: O(1) extra space (excluding the input-derived digit list).
- The DP tables dp and ndp each hold a fixed 2 * 2 * 2 = 8 entries, independent of n.
- The candidate lists A and B contain at most 10 elements each, which is also a constant.
- The digits list itself takes O(L) space, but the auxiliary DP storage used by the algorithm is constant, matching the reference answer's O(1).

Pattern Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Forgetting the extra column for the final carry

A frequent mistake is to process only the m real digits of n and then read the answer from dp[0][0][0]. The problem is that the highest column of the addition can still produce a carry of 1, and that carry must be matched against an (implicit) leading digit 0 of n. Without the artificial appended 0 column, states with a leftover carry are silently merged into the result or never validated, producing wrong counts.

Fix: append a sentinel digit 0 after reversing the digits:

digits = list(map(int, str(n)))[::-1]
digits.append(0)  # absorbs and validates the final carry

In the extra column both numbers are forced to contribute 0 (alive numbers cannot emit 0 and match the target only if they end), so any surviving carry makes s % 10 == 1 != 0 and the invalid path is correctly killed.

2. Allowing a number to "end" at position 0

The termination transition (0, 0) lets a number stop emitting digits. If this option is offered at pos == 0 (the units column), the DP counts paths where a or b never places a single digit — i.e., the number equals 0, which is not a positive integer. For example, with n = 9 this would wrongly count (0, 9) and (9, 0).

Fix: guard the termination choice:

if pos > 0:
    choices_a.append((0, 0))

3. Letting a dead number come back to life

If the state does not enforce that "ended" is irreversible — e.g., if a dead number is allowed to emit a nonzero digit at a higher position — the DP effectively permits internal zeros: a number like 105 would be modeled as digit 5, then "dead" (the 0), then digit 1. This is exactly the kind of number the problem forbids.

Fix: a dead number must have only one choice, forever:

else:
    choices_a = [(0, 0)]  # stays dead, contributes 0

The combination of "alive numbers can never emit 0" and "dead numbers can never emit nonzero" is what guarantees the no-zero property without ever inspecting whole numbers.

4. Processing digits from the most significant side

Carries in addition propagate from the least significant digit upward. Writing the DP from the most significant digit makes the carry a future unknown rather than a known input, which requires a much more awkward formulation (guessing incoming carries and verifying them later). Reversing the digit list and iterating from the units column keeps the transition simple: s = da + db + carry, outgoing carry s // 10.

Fix: always reverse before processing:

digits = list(map(int, str(n)))[::-1]

5. Checking `s == target` instead of `s % 10 == target`

The column sum s = da + db + carry ranges up to 19. Comparing s directly with the target digit drops every transition that generates a carry (e.g., 7 + 5 = 12 matching target digit 2). The comparison must be modulo 10, with the quotient becoming the next carry:

if column_sum % 10 != target:
    continue
next_carry = column_sum // 10

6. Brute-forcing for large `n`

Iterating a from 1 to n - 1 and checking both a and n - a for zeros is O(n · log n) and times out once n grows beyond roughly 10^7–10^8. The brute force is still valuable, though — as a cross-check: validate the digit DP against it for all n up to, say, 10^5 before trusting it on large inputs:

def brute(n):
    ok = lambda x: '0' not in str(x)
    return sum(1 for a in range(1, n) if ok(a) and ok(n - a))

7. Misreading the pair-counting convention

The problem counts ordered pairs: (2, 9) and (9, 2) are distinct. The DP naturally counts ordered pairs because a and b have independent choice lists. A common error in the opposite direction is to divide the result by 2 to "deduplicate" — this is wrong both because the problem wants ordered pairs and because a symmetric pair like (5, 5) for n = 10 would be halved incorrectly. Match the convention to the problem statement before adjusting the count.

Ready to land your dream job?

Unlock your dream job with a 5-minute quiz for a personalized study roadmap!

Get My Roadmap

Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Get a Personalized Study Roadmap:

You are given an array of intervals where intervals[i] = [start_i, end_i] represent the start and end of the ith interval. You need to merge all overlapping intervals and return an array of the non-overlapping intervals that cover all the intervals in the input.

Sort the intervals by their start time, then iterate through the sorted intervals, merging any overlapping intervals.

Brute force through all interval combinations and find the answer with the least total intervals.

Iterate through the intervals in their original order, merging any overlapping intervals.

Use a priority queue to keep track of the intervals, merging any overlapping intervals.

I don't know