3883. Count Non Decreasing Arrays With Given Digit Sums
You are given an integer array digitSum of length n.
An array arr of length n is considered valid if:
0 <= arr[i] <= 5000- it is non-decreasing.
- the sum of the digits of
arr[i] equals digitSum[i].
Return an integer denoting the number of distinct valid arrays. Since the answer may be large, return it modulo 10^9 + 7.
An array is said to be non-decreasing if each element is greater than or equal to the previous element, if it exists.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
| class Solution {
public:
int countArrays(vector<int>& digitSum) {
vector<vector<int>> cands(51);
auto sumOf = [&](int x) {
int res = 0;
while(x) {
res += x % 10;
x /= 10;
}
return res;
};
for(int i = 0; i <= 5000; i++) {
cands[sumOf(i)].push_back(i);
}
long long mod = 1e9 + 7, res = 0;
vector<pair<int,long long>> dp{{-1,1}};
for(auto& d : digitSum) {
long long sum = 0, idx = 0, n = dp.size();
vector<pair<int,long long>> dpp;
for(auto& val : cands[d]) {
while(idx < n and dp[idx].first <= val) {
sum = (sum + dp[idx].second) % mod;
idx++;
}
if(sum) {
dpp.push_back({val, sum});
}
}
swap(dp,dpp);
}
for(auto& [k,v] : dp) {
res = (res + v) % mod;
}
return res;
}
};
|
