Count No-Zero Pairs That Sum to N solution and explanation
4 more videos on this problem
【每日一题】LeetCode 3704. Count No-Zero Pairs That Sum to NHuifeng Guan · 25:36 · 1K views
Count No-Zero Pairs That Sum to N | LeetCode 3704 | Advanced Digit DPSanyam IIT Guwahati · 25:41 · 1K views
Weekly Contest 470 🔥 Count No-Zero Pairs That Sum to N | Leetcode 3704 (Q4) Digit DP Explained Study Placement · 20:23 · 652 views
3704. Count No-Zero Pairs That Sum to N (Leetcode Hard)Programming Live with Larry · 2:01:43 · 549 views
Leetcode 3704 | Count No-Zero Pairs That Sum to N | Dynamic ProgrammingCodeWithMeGuys · 19:01 · 425 views
The problem
A no-zero integer is a positive integer that does not contain the digit 0 in its decimal representation.
Given an integer n, count the number of pairs (a, b) where:
aandbare no-zero integers.a + b = n
Return an integer denoting the number of such pairs.
Example 1:
Input: n = 2
Output: 1
Explanation:
The only pair is (1, 1).
Example 2:
Input: n = 3
Output: 2
Explanation:
The pairs are (1, 2) and (2, 1).
Example 3:
Input: n = 11
Output: 8
Explanation:
The pairs are (2, 9), (3, 8), (4, 7), (5, 6), (6, 5), (7, 4), (8, 3), and (9, 2). Note that (1, 10) and (10, 1) do not satisfy the conditions because 10 contains 0 in its decimal representation.
Constraints:
2 <= n <= 1015
Approach overview
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.
Solution
We do a digit DP over the decimal representation of n from the least-significant digit to the most-significant digit.
State: dp[pos][carry][aliveA][aliveB] = number of ways for the processed suffix.
carryis the carry into the current digit (0 or 1).aliveA/aliveBindicates whether the number still has digits in higher positions. IfaliveX = 0, all remaining higher digits must be leading zeros (digit 0), which are not part of the decimal representation.
Transition: choose digits da and db:
- If
aliveX = 1, digit is in[1..9](no-zero). - Otherwise digit is
0.
They must satisfy (da + db + carry) % 10 == digit_n[pos]. After that, aliveA/aliveB can stay 1 or become 0 (ending the number at this digit).
We append one extra leading digit 0 to n so the last carry is fully handled. The answer is dp[last][0][0][0].
Time complexity is O(L cdot 9^2) and space complexity is O(1), where L is the number of digits of n.
class Solution:
def countNoZeroPairs(self, n: int) -> int:
digits = list(map(int, str(n)))[::-1]
digits.append(0) # absorb final carry
L = len(digits)
# dp[carry][aliveA][aliveB]
dp = [[[0] * 2 for _ in range(2)] for _ in range(2)]
dp[0][1][1] = 1
for pos in range(L):
ndp = [[[0] * 2 for _ in range(2)] for _ in range(2)]
target = digits[pos]
for carry in range(2):
for aliveA in range(2):
for aliveB in range(2):
ways = dp[carry][aliveA][aliveB]
if ways == 0:
continue
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)]
if aliveB:
B = [(d, 1) for d in range(1, 10)]
if pos > 0:
B.append((0, 0))
else:
B = [(0, 0)]
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
dp = ndp
return dp[0][0][0]class Solution {
public long countNoZeroPairs(long n) {
char[] cs = Long.toString(n).toCharArray();
int m = cs.length;
int[] digits = new int[m + 1];
for (int i = 0; i < m; i++) {
digits[i] = cs[m - 1 - i] - '0';
}
digits[m] = 0;
long[][][] dp = new long[2][2][2];
dp[0][1][1] = 1;
for (int pos = 0; pos < m + 1; pos++) {
long[][][] ndp = new long[2][2][2];
int target = digits[pos];
for (int carry = 0; carry <= 1; carry++) {
for (int aliveA = 0; aliveA <= 1; aliveA++) {
for (int aliveB = 0; aliveB <= 1; aliveB++) {
long ways = dp[carry][aliveA][aliveB];
if (ways == 0) {
continue;
}
int[] aDigits;
int[] aNext;
if (aliveA == 1) {
if (pos == 0) {
aDigits = new int[] {1, 2, 3, 4, 5, 6, 7, 8, 9};
aNext = new int[] {1, 1, 1, 1, 1, 1, 1, 1, 1};
} else {
aDigits = new int[] {1, 2, 3, 4, 5, 6, 7, 8, 9, 0};
aNext = new int[] {1, 1, 1, 1, 1, 1, 1, 1, 1, 0};
}
} else {
aDigits = new int[] {0};
aNext = new int[] {0};
}
int[] bDigits;
int[] bNext;
if (aliveB == 1) {
if (pos == 0) {
bDigits = new int[] {1, 2, 3, 4, 5, 6, 7, 8, 9};
bNext = new int[] {1, 1, 1, 1, 1, 1, 1, 1, 1};
} else {
bDigits = new int[] {1, 2, 3, 4, 5, 6, 7, 8, 9, 0};
bNext = new int[] {1, 1, 1, 1, 1, 1, 1, 1, 1, 0};
}
} else {
bDigits = new int[] {0};
bNext = new int[] {0};
}
for (int ai = 0; ai < aDigits.length; ai++) {
int da = aDigits[ai];
int na = aNext[ai];
for (int bi = 0; bi < bDigits.length; bi++) {
int db = bDigits[bi];
int nb = bNext[bi];
int s = da + db + carry;
if (s % 10 != target) {
continue;
}
int ncarry = s / 10;
ndp[ncarry][na][nb] += ways;
}
}
}
}
}
dp = ndp;
}
return dp[0][0][0];
}
}class Solution {
public:
long long countNoZeroPairs(long long n) {
std::string s = std::to_string(n);
int m = (int) s.size();
std::vector<int> digits(m + 1);
for (int i = 0; i < m; i++) {
digits[i] = s[m - 1 - i] - '0';
}
digits[m] = 0;
long long dp[2][2][2] = {};
dp[0][1][1] = 1;
for (int pos = 0; pos < m + 1; pos++) {
long long ndp[2][2][2] = {};
int target = digits[pos];
for (int carry = 0; carry <= 1; carry++) {
for (int aliveA = 0; aliveA <= 1; aliveA++) {
for (int aliveB = 0; aliveB <= 1; aliveB++) {
long long ways = dp[carry][aliveA][aliveB];
if (!ways) continue;
int aDigits[10];
int aNext[10];
int aLen = 0;
if (aliveA) {
for (int d = 1; d <= 9; d++) {
aDigits[aLen] = d;
aNext[aLen] = 1;
aLen++;
}
if (pos > 0) {
aDigits[aLen] = 0;
aNext[aLen] = 0;
aLen++;
}
} else {
aDigits[0] = 0;
aNext[0] = 0;
aLen = 1;
}
int bDigits[10];
int bNext[10];
int bLen = 0;
if (aliveB) {
for (int d = 1; d <= 9; d++) {
bDigits[bLen] = d;
bNext[bLen] = 1;
bLen++;
}
if (pos > 0) {
bDigits[bLen] = 0;
bNext[bLen] = 0;
bLen++;
}
} else {
bDigits[0] = 0;
bNext[0] = 0;
bLen = 1;
}
for (int ia = 0; ia < aLen; ia++) {
int da = aDigits[ia];
int na = aNext[ia];
for (int ib = 0; ib < bLen; ib++) {
int db = bDigits[ib];
int nb = bNext[ib];
int sum = da + db + carry;
if (sum % 10 != target) continue;
int ncarry = sum / 10;
ndp[ncarry][na][nb] += ways;
}
}
}
}
}
std::memcpy(dp, ndp, sizeof(dp));
}
return dp[0][0][0];
}
};package main
import "strconv"
func countNoZeroPairs(n int64) int64 {
s := []byte(strconv.FormatInt(n, 10))
m := len(s)
digits := make([]int, m+1)
for i := 0; i < m; i++ {
digits[i] = int(s[m-1-i] - '0')
}
digits[m] = 0
var dp [2][2][2]int64
dp[0][1][1] = 1
for pos := 0; pos < m+1; pos++ {
var ndp [2][2][2]int64
target := digits[pos]
for carry := 0; carry <= 1; carry++ {
for aliveA := 0; aliveA <= 1; aliveA++ {
for aliveB := 0; aliveB <= 1; aliveB++ {
ways := dp[carry][aliveA][aliveB]
if ways == 0 {
continue
}
var A [10][2]int
aLen := 0
if aliveA == 1 {
for d := 1; d <= 9; d++ {
A[aLen][0] = d
A[aLen][1] = 1
aLen++
}
if pos > 0 {
A[aLen][0] = 0
A[aLen][1] = 0
aLen++
}
} else {
A[0][0] = 0
A[0][1] = 0
aLen = 1
}
var B [10][2]int
bLen := 0
if aliveB == 1 {
for d := 1; d <= 9; d++ {
B[bLen][0] = d
B[bLen][1] = 1
bLen++
}
if pos > 0 {
B[bLen][0] = 0
B[bLen][1] = 0
bLen++
}
} else {
B[0][0] = 0
B[0][1] = 0
bLen = 1
}
for ai := 0; ai < aLen; ai++ {
da, na := A[ai][0], A[ai][1]
for bi := 0; bi < bLen; bi++ {
db, nb := B[bi][0], B[bi][1]
sum := da + db + carry
if sum%10 != target {
continue
}
ncarry := sum / 10
ndp[ncarry][na][nb] += ways
}
}
}
}
}
dp = ndp
}
return dp[0][0][0]
}Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Enumeration | O(n * d) | O(1) | Small n or quick validation of constraints |
| Digit Dynamic Programming | O(d * 100) | O(d * 10) | Large n with digit restrictions and carry handling |
Frequently asked questions
Is Count No-Zero Pairs That Sum to N easy or hard?
The problem is considered Hard because it requires recognizing a digit-level constraint and converting the addition rule into a Digit DP state transition. Implementing carry handling and digit validation correctly is the main challenge.
Count No-Zero Pairs That Sum to N Python/Java solution
Most implementations use Digit DP with recursion plus memoization or a bottom-up DP table. The same logic works across Python, Java, C++, and Go: iterate digit positions, try digits 1–9 for both numbers, validate the sum with carry, and accumulate counts.
How to solve Count No-Zero Pairs That Sum to N in O(n)?
A direct O(n) solution is generally not suitable when n can be large. Instead, treat the problem as a digit counting task and apply Digit DP. By iterating through digits of n and validating digit pairs (1–9 only) with carry propagation, the complexity reduces to O(d * 100).
What is the best approach for Count No-Zero Pairs That Sum to N?
Digit Dynamic Programming (Digit DP) is the most efficient approach. Instead of iterating over every possible pair, it processes the digits of n and counts valid digit combinations for a and b while tracking carry between positions. The complexity becomes O(d * 100), where d is the number of digits in n.
Is Count No-Zero Pairs That Sum to N asked at Google/Amazon/Meta?
Digit-restriction counting problems appear frequently in interviews at large tech companies. Variants involving Digit DP, carry handling, or counting numbers with restricted digits have been reported in interviews at companies like Google and Amazon.
What data structure is used in Count No-Zero Pairs That Sum to N?
The core structure is a dynamic programming table indexed by digit position and carry state. Each state stores the number of valid ways to form partial sums while respecting the no-zero digit constraint.
What is the time complexity of Count No-Zero Pairs That Sum to N?
The optimal Digit DP solution runs in O(d * 100) time because each digit position evaluates up to 9×9 digit combinations and a small number of carry states. Space complexity is typically O(d * 10) for the DP table. A naive brute force approach would take O(n * d).