Daily DSA: Count Alternating-Parity Integers with Divisible Digit Sum (Hard)
Advertisement
Problem Statement
You are given two large positive integers represented as strings low and high, and a positive integer k.
An integer is defined as valid if it satisfies both of the following conditions:
- Alternating Parity: No two adjacent decimal digits have the same parity. That is, if a digit is even, the immediately following digit must be odd, and if a digit is odd, the immediately following digit must be even. Single-digit numbers trivially satisfy this condition.
- Divisible Digit Sum: The sum of all its digits is divisible by
k.
Return the number of valid integers in the inclusive range [low, high].
Since the answer may be very large, return it modulo $10^9 + 7$.
Example 1
Input: low = "10", high = "30", k = 3
Output: 5
Explanation:
The valid integers between 10 and 30 are:
- 12: parities are [odd, even], sum = 1 + 2 = 3 (divisible by 3)
- 18: parities are [odd, even], sum = 1 + 8 = 9 (divisible by 3)
- 21: parities are [even, odd], sum = 2 + 1 = 3 (divisible by 3)
- 27: parities are [even, odd], sum = 2 + 7 = 9 (divisible by 3)
- 30: parities are [odd, even], sum = 3 + 0 = 3 (divisible by 3)
Total count is 5.
Example 2
Input: low = "1", high = "9", k = 2
Output: 4
Explanation:
Single-digit integers trivially satisfy the alternating parity condition.
The integers with an even digit sum are 2, 4, 6, and 8. Thus, there are 4 valid integers.
Example 3
Input: low = "50", high = "100", k = 5
Output: 6
Explanation:
The valid integers are 50 (sum=5), 69 (sum=15), 78 (sum=15), 87 (sum=15), 96 (sum=15), and 104 is out of range.
Among integers up to 100, the valid ones in [50, 100] are 50, 69, 78, 87, 96. Note: 100 has adjacent digits '0' and '0' (both even), so it is invalid.
Constraints
- $1 \le \text{low.length} \le \text{high.length} \le 500$
lowandhighconsist only of decimal digits and do not contain leading zeros.- Numerically, $\text{low} \le \text{high}$.
- $1 \le k \le 50$
Approach / Hints
-
Range Query Decomposition: Instead of counting directly in the range
[low, high], computef(high)which counts valid numbers in[1, high], andf(low)which counts valid numbers in[1, low]. The answer is(f(high) - f(low) + isValid(low)) % MOD. - Digit DP State Representation:
Process the digits from the most significant to the least significant (index $0$ to $N - 1$).
We define our DP state as
dp(idx, sum_mod, last_parity, is_less):idx: Current digit position we are placing ($0$ to $N-1$).sum_mod: Sum of chosen digits modulo $k$ ($0$ to $k - 1$).last_parity: Parity of the previous non-leading-zero digit. We can represent this with0(even),1(odd), or2(no digit placed yet / leading zeros).is_less: A boolean flag indicating whether the prefix placed so far is strictly less than the prefix of the boundary string.
- Transitions:
- The upper bound for the current digit $d$ is $9$ if
is_lessis true, or the digit in the boundary string otherwise. - If we havenβt started forming the number yet (
last_parity == 2):- We can place $0$, remaining in the non-started state (
last_parity = 2,sum_mod = 0). - Or place $d \in [1, \text{limit}]$, transitioning to
last_parity = d % 2andsum_mod = d % k.
- We can place $0$, remaining in the non-started state (
- If the number has started (
last_parityis 0 or 1):- We can place any digit $d$ where $d \% 2 \ne \text{last_parity}$.
- The new
sum_modbecomes(sum_mod + d) % kandlast_paritybecomesd % 2.
- The upper bound for the current digit $d$ is $9$ if
- Base Case:
- When
idx == N, we return $1$ iflast_parity != 2andsum_mod == 0, otherwise $0$.
- When
- Complexity:
- Total number of states: $N \times k \times 3 \times 2$.
- For $N = 500$ and $k = 50$, the number of states is $500 \times 50 \times 3 \times 2 = 150{,}000$.
- From each state, we iterate over at most 10 digits. Total transitions $\approx 1.5 \times 10^6$, which easily runs well within the 1-second time limit in C++.
C++ Solution
#include <iostream>
#include <string>
#include <vector>
#include <cstring>
using namespace std;
class Solution {
static const int MOD = 1e9 + 7;
int memo[505][55][3][2];
int solve(int idx, int sum_mod, int last_parity, bool is_less, const string& S, int k) {
if (idx == (int)S.size()) {
return (last_parity != 2 && sum_mod == 0) ? 1 : 0;
}
if (memo[idx][sum_mod][last_parity][is_less] != -1) {
return memo[idx][sum_mod][last_parity][is_less];
}
int limit = is_less ? 9 : (S[idx] - '0');
long long ans = 0;
for (int d = 0; d <= limit; ++d) {
bool next_less = is_less || (d < limit);
if (last_parity == 2) {
if (d == 0) {
// Still leading zero
ans = (ans + solve(idx + 1, 0, 2, next_less, S, k)) % MOD;
} else {
// First non-zero digit
ans = (ans + solve(idx + 1, d % k, d % 2, next_less, S, k)) % MOD;
}
} else {
// Must alternate parity
if (d % 2 != last_parity) {
ans = (ans + solve(idx + 1, (sum_mod + d) % k, d % 2, next_less, S, k)) % MOD;
}
}
}
return memo[idx][sum_mod][last_parity][is_less] = ans;
}
int countUpTo(const string& S, int k) {
memset(memo, -1, sizeof(memo));
return solve(0, 0, 2, false, S, k);
}
bool isValid(const string& S, int k) {
int sum = 0;
for (int i = 0; i < (int)S.size(); ++i) {
sum += (S[i] - '0');
if (i > 0 && (S[i] - '0') % 2 == (S[i - 1] - '0') % 2) {
return false;
}
}
return (sum % k == 0);
}
public:
int countAlternatingParity(string low, string high, int k) {
long long count_high = countUpTo(high, k);
long long count_low = countUpTo(low, k);
long long ans = (count_high - count_low + (isValid(low, k) ? 1 : 0)) % MOD;
if (ans < 0) {
ans += MOD;
}
return ans;
}
};
Complexity Analysis
- Time Complexity: $\mathcal{O}(N \times k \times D)$, where $N$ is the number of digits in
high($N \le 500$), $k$ is the divisor ($k \le 50$), and $D = 10$ is the base size. Total operations $\le 1.5 \times 10^6$, running in under $50\text{ ms}$. - Space Complexity: $\mathcal{O}(N \times k)$ for the 4-dimensional memoization table and recursion stack.
Advertisement