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
|
impl Solution {
pub fn count_beautiful_numbers(l: i32, r: i32) -> i32 {
fn count(n: i32) -> i32 {
let s = n.to_string().chars().collect::<Vec<_>>();
use std::collections::HashMap;
fn dp(pos: usize, tight: bool, sum: i32, prod: i32, leading_zero: bool, s: &Vec<char>, memo: &mut HashMap<(usize, bool, i32, i32, bool), i32>) -> i32 {
if pos == s.len() {
return if sum > 0 && prod % sum == 0 { 1 } else { 0 };
}
let key = (pos, tight, sum, prod, leading_zero);
if !tight && !leading_zero {
if let Some(&v) = memo.get(&key) { return v; }
}
let up = if tight { s[pos].to_digit(10).unwrap() as i32 } else { 9 };
let mut res = 0;
for d in 0..=up {
let nsum = if leading_zero && d == 0 { sum } else { sum + d };
let nprod = if leading_zero && d == 0 { prod } else { if d == 0 { prod } else { prod * d } };
let nleading_zero = leading_zero && d == 0;
let ntight = tight && d == up;
res += dp(pos+1, ntight, nsum, nprod, nleading_zero, s, memo);
}
if !tight && !leading_zero { memo.insert(key, res); }
res
}
let mut memo = HashMap::new();
dp(0, true, 0, 1, true, &s, &mut memo)
}
count(r) - count(l-1)
}
}
|