Count No-Zero Pairs That Sum to N - Solution & Explanation

Problem Overview: Given an integer n, count ordered pairs (a, b) such that a + b = n and neither number contains the digit 0. Every digit in both numbers must be from 1–9. The challenge is enforcing the digit restriction while respecting addition carries across digits.

Approach 1: Brute Force Enumeration (O(n * d) time, O(1) space)

Iterate a from 1 to n-1 and compute b = n - a. For each pair, scan the digits of both numbers and reject any value containing digit 0. If both pass the check, increment the answer. The digit validation takes O(d) time where d is the number of digits in n. This approach quickly becomes infeasible for large n because you must inspect up to n candidates.

The brute force version is useful to understand the constraint: the only thing that invalidates a pair is the presence of digit 0. Once you recognize that the restriction operates per digit, the problem becomes a natural fit for digit-level counting techniques.

Approach 2: Digit Dynamic Programming (Digit DP) (O(d * 100) time, O(d * 10) space)

Instead of enumerating numbers, process the digits of n from least significant to most significant and count valid digit combinations for a and b. For each position, choose digits da and db in the range 1..9. Their sum plus an incoming carry must match the corresponding digit of n. The next state depends on the new carry produced by da + db.

The DP state typically looks like dp[pos][carry], representing the number of ways to construct valid digit pairs for the first pos digits with a given carry. At each step, try all 9 × 9 digit combinations and keep only those that satisfy the addition constraint. Because the digit range is fixed, each state explores at most 81 transitions.

This transforms the search space from potentially billions of numbers to a small state graph proportional to the number of digits in n. Digit DP is a common technique for problems involving digit restrictions or counting numbers under arithmetic constraints. If you want to deepen the pattern, review related concepts in dynamic programming, math, and digit-based state modeling.

Recommended for interviews: Start by describing the brute-force check to show understanding of the constraint. Then transition to Digit DP once you observe that the restriction applies independently to each digit while addition only introduces a carry dependency. Interviewers typically expect the Digit DP solution because it reduces the search space to O(d) states and demonstrates strong control over digit-level dynamic programming.