Skip to main content
Talentd

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

HardMathDynamic Programming11 min read
Practice this problem

Problem Statement

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:

  • a and b are 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.

  • carry is the carry into the current digit (0 or 1).
  • aliveA/aliveB indicates whether the number still has digits in higher positions. If aliveX = 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.

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force EnumerationO(n * d)O(1)Small n or quick validation of constraints
Digit Dynamic ProgrammingO(d * 100)O(d * 10)Large n with digit restrictions and carry handling

Video Solution

【每日一题】LeetCode 3704. Count No-Zero Pairs That Sum to N • Huifeng Guan • 1,064 views views

Watch 4 more video solutions →

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).

Ready to solve this problem?

Practice Count No-Zero Pairs That Sum to N with our built-in code editor and test cases.

Practice on FleetCode
Previous

Add Two Numbers

Next

Reverse Integer