Welcome to Subscribe On Youtube
3704. Count No-Zero Pairs That Sum to N
Description
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
Solutions
Solution 1
-
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]; } public long countPairs(long n) { return countNoZeroPairs(n); } } -
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]; } long long countPairs(long long n) { return countNoZeroPairs(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] def countPairs(self, n: int) -> int: return self.countNoZeroPairs(n) -
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] } func countPairs(n int64) int64 { return countNoZeroPairs(n) }