Number of Beautiful Integers in the Range — Solution
Number of Beautiful Integers in the Range solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.
Number of Beautiful Integers in the Range is a hard coding problem on dynamic programming, math and Digit DP, asked in Amazon and Google interviews.
- Difficulty: Hard
- Topics: Dynamic Programming, Math, Digit DP
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Call a positive integer beautiful for a given k when both of these hold:
- its decimal representation has exactly as many even digits as odd digits, and
- it is divisible by
k.
Given low, high and k, return how many beautiful integers lie in the inclusive range [low, high].
Example 1
Input: low = 10, high = 20, k = 3
Output: 2
Explanation: 12 (one odd digit, one even) and 18 (likewise) are multiples of 3. 15 is a multiple of 3 but both its digits are odd.
Example 2
Input: low = 1, high = 10, k = 1
Output: 1
Explanation: Only 10 has one odd and one even digit; every single-digit number is unbalanced.
Example 3
Input: low = 5, high = 5, k = 2
Output: 0
Explanation: A one-digit number can never have equal counts.
Constraints
0 < low <= high <= 10^90 < k <= 20
Hints for Number of Beautiful Integers in the Range
Hint 1
Count beautiful numbers in
[1, n]with a functionf(n); the answer isf(high) - f(low - 1).Hint 2
Build numbers digit by digit from the most significant one (digit DP). What do you need to remember about the prefix so far to finish the decision?
Hint 3
Track four things: whether the prefix still equals
n's prefix (tight), whether a non-zero digit has been placed yet (leading zeros are not digits), the remainder modulok, and the difference between even and odd digit counts.
How to solve Number of Beautiful Integers in the Range
The range is too large to scan, but whether a number is beautiful depends only on two running quantities — its remainder modulo k and the balance of even versus odd digits — so a digit DP counts all numbers up to a bound at once.
Approach
- Write
f(n)= beautiful numbers in[1, n]; returnf(high) - f(low - 1). - For
f(n), walk the digits ofnfrom the left. A state is(tight, started, rem, balance)with a count of prefixes in it; start from(tight, not started, 0, 0)with count 1. - At each position try every digit
gfrom 0 up ton's digit if tight, else 9. The new state stays tight only if it was tight andgequals the bound. - If the number has not started and
g = 0, it is still a leading zero: stay unstarted with remainder 0 and balance 0. Otherwise mark it started, setrem = (rem * 10 + g) mod kand add +1 to the balance for an eveng, -1 for an odd one. - After the last digit, add up the counts of started states with remainder 0 and balance 0.
Why it works
Two numbers whose prefixes agree on remainder and balance can be completed by exactly the same suffixes, so grouping prefixes by those values loses nothing. The tight flag keeps every counted number at most n, and the started flag keeps leading zeros out of the even-digit count.
Complexity
- Time —
O(D · k · D · 10) per bound, with D ≤ 10 digits - Space —
O(k · D)
Pitfalls
- Leading zeros are not even digits — without the started flag, 7 would be read as 07 and look balanced.
- Use
low - 1for the lower bound, notlow. - The balance can range from -10 to +10, so offset it before using it as an index.
Reference solution
Python
def numberOfBeautifulIntegers(low: int, high: int, k: int) -> int:
# state index = ((tight * 2 + started) * k + rem) * 21 + balance + 10
def count(n):
if n <= 0:
return 0
size = 4 * k * 21
cur = [0] * size
cur[2 * k * 21 + 10] = 1
for ch in str(n):
top = ord(ch) - 48
nxt = [0] * size
for idx in range(size):
c = cur[idx]
if c == 0:
continue
d = idx % 21
r = (idx // 21) % k
ts = idx // (21 * k)
t, st = ts >> 1, ts & 1
hi = top if t else 9
for g in range(hi + 1):
nt = 1 if (t and g == hi) else 0
if not st and g == 0:
nxt[nt * 2 * k * 21 + 10] += c
else:
nd = d + 1 if g % 2 == 0 else d - 1
nxt[((nt * 2 + 1) * k + (r * 10 + g) % k) * 21 + nd] += c
cur = nxt
return cur[k * 21 + 10] + cur[3 * k * 21 + 10]
return count(high) - count(low - 1)Java
static long beautifulUpTo(int n, int k) {
// state index = ((tight * 2 + started) * k + rem) * 21 + balance + 10
if (n <= 0) return 0;
int size = 4 * k * 21;
long[] cur = new long[size];
cur[2 * k * 21 + 10] = 1;
String digits = Integer.toString(n);
for (int p = 0; p < digits.length(); p++) {
int top = digits.charAt(p) - '0';
long[] nxt = new long[size];
for (int idx = 0; idx < size; idx++) {
long c = cur[idx];
if (c == 0) continue;
int d = idx % 21, r = (idx / 21) % k, ts = idx / (21 * k);
int t = ts >> 1, st = ts & 1;
int hi = t == 1 ? top : 9;
for (int g = 0; g <= hi; g++) {
int nt = (t == 1 && g == hi) ? 1 : 0;
if (st == 0 && g == 0) nxt[nt * 2 * k * 21 + 10] += c;
else nxt[((nt * 2 + 1) * k + (r * 10 + g) % k) * 21 + d + (g % 2 == 0 ? 1 : -1)] += c;
}
}
cur = nxt;
}
return cur[k * 21 + 10] + cur[3 * k * 21 + 10];
}
public static int numberOfBeautifulIntegers(int low, int high, int k) {
return (int) (beautifulUpTo(high, k) - beautifulUpTo(low - 1, k));
}C++
long long beautifulUpTo(int n, int k) {
// state index = ((tight * 2 + started) * k + rem) * 21 + balance + 10
if (n <= 0) return 0;
int size = 4 * k * 21;
vector<long long> cur(size, 0);
cur[2 * k * 21 + 10] = 1;
string digits = to_string(n);
for (char ch : digits) {
int top = ch - '0';
vector<long long> nxt(size, 0);
for (int idx = 0; idx < size; idx++) {
long long c = cur[idx];
if (c == 0) continue;
int d = idx % 21, r = (idx / 21) % k, ts = idx / (21 * k);
int t = ts >> 1, st = ts & 1;
int hi = t ? top : 9;
for (int g = 0; g <= hi; g++) {
int nt = (t && g == hi) ? 1 : 0;
if (!st && g == 0) nxt[nt * 2 * k * 21 + 10] += c;
else nxt[((nt * 2 + 1) * k + (r * 10 + g) % k) * 21 + d + (g % 2 == 0 ? 1 : -1)] += c;
}
}
cur = nxt;
}
return cur[k * 21 + 10] + cur[3 * k * 21 + 10];
}
int numberOfBeautifulIntegers(int low, int high, int k) {
return (int) (beautifulUpTo(high, k) - beautifulUpTo(low - 1, k));
}JavaScript
var numberOfBeautifulIntegers = function(low, high, k) {
// state index = ((tight * 2 + started) * k + rem) * 21 + balance + 10
var count = function(n) {
if (n <= 0) return 0;
var size = 4 * k * 21;
var cur = new Array(size).fill(0);
cur[2 * k * 21 + 10] = 1;
var digits = String(n);
for (var p = 0; p < digits.length; p++) {
var top = digits.charCodeAt(p) - 48;
var nxt = new Array(size).fill(0);
for (var idx = 0; idx < size; idx++) {
var c = cur[idx];
if (c === 0) continue;
var d = idx % 21, r = Math.floor(idx / 21) % k, ts = Math.floor(idx / (21 * k));
var t = ts >> 1, st = ts & 1;
var hi = t ? top : 9;
for (var g = 0; g <= hi; g++) {
var nt = (t && g === hi) ? 1 : 0;
if (!st && g === 0) nxt[nt * 2 * k * 21 + 10] += c;
else nxt[((nt * 2 + 1) * k + (r * 10 + g) % k) * 21 + d + (g % 2 === 0 ? 1 : -1)] += c;
}
}
cur = nxt;
}
return cur[k * 21 + 10] + cur[3 * k * 21 + 10];
};
return count(high) - count(low - 1);
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 402 dynamic programming problems · the whole catalogue
Learn the technique: Dynamic Programming