Overflow in intermediate arithmetic
Wrong move: Temporary multiplications exceed integer bounds.
Usually fails on: Large inputs wrap around unexpectedly.
Fix: Use wider types, modular arithmetic, or rearranged operations.
Break down a hard problem into reliable checkpoints, edge-case handling, and complexity trade-offs.
You are given positive integers low, high, and k.
A number is beautiful if it meets both of the following conditions:
k.Return the number of beautiful integers in the range [low, high].
Example 1:
Input: low = 10, high = 20, k = 3 Output: 2 Explanation: There are 2 beautiful integers in the given range: [12,18]. - 12 is beautiful because it contains 1 odd digit and 1 even digit, and is divisible by k = 3. - 18 is beautiful because it contains 1 odd digit and 1 even digit, and is divisible by k = 3. Additionally we can see that: - 16 is not beautiful because it is not divisible by k = 3. - 15 is not beautiful because it does not contain equal counts even and odd digits. It can be shown that there are only 2 beautiful integers in the given range.
Example 2:
Input: low = 1, high = 10, k = 1 Output: 1 Explanation: There is 1 beautiful integer in the given range: [10]. - 10 is beautiful because it contains 1 odd digit and 1 even digit, and is divisible by k = 1. It can be shown that there is only 1 beautiful integer in the given range.
Example 3:
Input: low = 5, high = 5, k = 2 Output: 0 Explanation: There are 0 beautiful integers in the given range. - 5 is not beautiful because it is not divisible by k = 2 and it does not contain equal even and odd digits.
Constraints:
0 < low <= high <= 1090 < k <= 20Problem summary: You are given positive integers low, high, and k. A number is beautiful if it meets both of the following conditions: The count of even digits in the number is equal to the count of odd digits. The number is divisible by k. Return the number of beautiful integers in the range [low, high].
Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.
Pattern signal: Math · Dynamic Programming
10 20 3
1 10 1
5 5 2
count-numbers-with-non-decreasing-digits)Source-backed implementations are provided below for direct study and interview prep.
// Accepted solution for LeetCode #2827: Number of Beautiful Integers in the Range
class Solution {
private String s;
private int k;
private Integer[][][] f = new Integer[11][21][21];
public int numberOfBeautifulIntegers(int low, int high, int k) {
this.k = k;
s = String.valueOf(high);
int a = dfs(0, 0, 10, true, true);
s = String.valueOf(low - 1);
f = new Integer[11][21][21];
int b = dfs(0, 0, 10, true, true);
return a - b;
}
private int dfs(int pos, int mod, int diff, boolean lead, boolean limit) {
if (pos >= s.length()) {
return mod == 0 && diff == 10 ? 1 : 0;
}
if (!lead && !limit && f[pos][mod][diff] != null) {
return f[pos][mod][diff];
}
int ans = 0;
int up = limit ? s.charAt(pos) - '0' : 9;
for (int i = 0; i <= up; ++i) {
if (i == 0 && lead) {
ans += dfs(pos + 1, mod, diff, true, limit && i == up);
} else {
int nxt = diff + (i % 2 == 1 ? 1 : -1);
ans += dfs(pos + 1, (mod * 10 + i) % k, nxt, false, limit && i == up);
}
}
if (!lead && !limit) {
f[pos][mod][diff] = ans;
}
return ans;
}
}
// Accepted solution for LeetCode #2827: Number of Beautiful Integers in the Range
func numberOfBeautifulIntegers(low int, high int, k int) int {
s := strconv.Itoa(high)
f := g(len(s), k, 21)
var dfs func(pos, mod, diff int, lead, limit bool) int
dfs = func(pos, mod, diff int, lead, limit bool) int {
if pos >= len(s) {
if mod == 0 && diff == 10 {
return 1
}
return 0
}
if !lead && !limit && f[pos][mod][diff] != -1 {
return f[pos][mod][diff]
}
up := 9
if limit {
up = int(s[pos] - '0')
}
ans := 0
for i := 0; i <= up; i++ {
if i == 0 && lead {
ans += dfs(pos+1, mod, diff, true, limit && i == up)
} else {
nxt := diff + 1
if i%2 == 0 {
nxt -= 2
}
ans += dfs(pos+1, (mod*10+i)%k, nxt, false, limit && i == up)
}
}
if !lead && !limit {
f[pos][mod][diff] = ans
}
return ans
}
a := dfs(0, 0, 10, true, true)
s = strconv.Itoa(low - 1)
f = g(len(s), k, 21)
b := dfs(0, 0, 10, true, true)
return a - b
}
func g(m, n, k int) [][][]int {
f := make([][][]int, m)
for i := 0; i < m; i++ {
f[i] = make([][]int, n)
for j := 0; j < n; j++ {
f[i][j] = make([]int, k)
for d := 0; d < k; d++ {
f[i][j][d] = -1
}
}
}
return f
}
# Accepted solution for LeetCode #2827: Number of Beautiful Integers in the Range
class Solution:
def numberOfBeautifulIntegers(self, low: int, high: int, k: int) -> int:
@cache
def dfs(pos: int, mod: int, diff: int, lead: int, limit: int) -> int:
if pos >= len(s):
return mod == 0 and diff == 10
up = int(s[pos]) if limit else 9
ans = 0
for i in range(up + 1):
if i == 0 and lead:
ans += dfs(pos + 1, mod, diff, 1, limit and i == up)
else:
nxt = diff + (1 if i % 2 == 1 else -1)
ans += dfs(pos + 1, (mod * 10 + i) % k, nxt, 0, limit and i == up)
return ans
s = str(high)
a = dfs(0, 0, 10, 1, 1)
dfs.cache_clear()
s = str(low - 1)
b = dfs(0, 0, 10, 1, 1)
return a - b
// Accepted solution for LeetCode #2827: Number of Beautiful Integers in the Range
// Rust example auto-generated from java reference.
// Replace the signature and local types with the exact LeetCode harness for this problem.
impl Solution {
pub fn rust_example() {
// Port the logic from the reference block below.
}
}
// Reference (java):
// // Accepted solution for LeetCode #2827: Number of Beautiful Integers in the Range
// class Solution {
// private String s;
// private int k;
// private Integer[][][] f = new Integer[11][21][21];
//
// public int numberOfBeautifulIntegers(int low, int high, int k) {
// this.k = k;
// s = String.valueOf(high);
// int a = dfs(0, 0, 10, true, true);
// s = String.valueOf(low - 1);
// f = new Integer[11][21][21];
// int b = dfs(0, 0, 10, true, true);
// return a - b;
// }
//
// private int dfs(int pos, int mod, int diff, boolean lead, boolean limit) {
// if (pos >= s.length()) {
// return mod == 0 && diff == 10 ? 1 : 0;
// }
// if (!lead && !limit && f[pos][mod][diff] != null) {
// return f[pos][mod][diff];
// }
// int ans = 0;
// int up = limit ? s.charAt(pos) - '0' : 9;
// for (int i = 0; i <= up; ++i) {
// if (i == 0 && lead) {
// ans += dfs(pos + 1, mod, diff, true, limit && i == up);
// } else {
// int nxt = diff + (i % 2 == 1 ? 1 : -1);
// ans += dfs(pos + 1, (mod * 10 + i) % k, nxt, false, limit && i == up);
// }
// }
// if (!lead && !limit) {
// f[pos][mod][diff] = ans;
// }
// return ans;
// }
// }
// Accepted solution for LeetCode #2827: Number of Beautiful Integers in the Range
function numberOfBeautifulIntegers(low: number, high: number, k: number): number {
let s = String(high);
let f: number[][][] = Array(11)
.fill(0)
.map(() =>
Array(21)
.fill(0)
.map(() => Array(21).fill(-1)),
);
const dfs = (pos: number, mod: number, diff: number, lead: boolean, limit: boolean): number => {
if (pos >= s.length) {
return mod == 0 && diff == 10 ? 1 : 0;
}
if (!lead && !limit && f[pos][mod][diff] != -1) {
return f[pos][mod][diff];
}
let ans = 0;
const up = limit ? Number(s[pos]) : 9;
for (let i = 0; i <= up; ++i) {
if (i === 0 && lead) {
ans += dfs(pos + 1, mod, diff, true, limit && i === up);
} else {
const nxt = diff + (i % 2 ? 1 : -1);
ans += dfs(pos + 1, (mod * 10 + i) % k, nxt, false, limit && i === up);
}
}
if (!lead && !limit) {
f[pos][mod][diff] = ans;
}
return ans;
};
const a = dfs(0, 0, 10, true, true);
s = String(low - 1);
f = Array(11)
.fill(0)
.map(() =>
Array(21)
.fill(0)
.map(() => Array(21).fill(-1)),
);
const b = dfs(0, 0, 10, true, true);
return a - b;
}
Use this to step through a reusable interview workflow for this problem.
Pure recursion explores every possible choice at each step. With two choices per state (take or skip), the decision tree has 2ⁿ leaves. The recursion stack uses O(n) space. Many subproblems are recomputed exponentially many times.
Each cell in the DP table is computed exactly once from previously solved subproblems. The table dimensions determine both time and space. Look for the state variables — each unique combination of state values is one cell. Often a rolling array can reduce space by one dimension.
Review these before coding to avoid predictable interview regressions.
Wrong move: Temporary multiplications exceed integer bounds.
Usually fails on: Large inputs wrap around unexpectedly.
Fix: Use wider types, modular arithmetic, or rearranged operations.
Wrong move: An incomplete state merges distinct subproblems and caches incorrect answers.
Usually fails on: Correctness breaks on cases that differ only in hidden state.
Fix: Define state so each unique subproblem maps to one DP cell.