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 three integers start, finish, and limit. You are also given a 0-indexed string s representing a positive integer.
A positive integer x is called powerful if it ends with s (in other words, s is a suffix of x) and each digit in x is at most limit.
Return the total number of powerful integers in the range [start..finish].
A string x is a suffix of a string y if and only if x is a substring of y that starts from some index (including 0) in y and extends to the index y.length - 1. For example, 25 is a suffix of 5125 whereas 512 is not.
Example 1:
Input: start = 1, finish = 6000, limit = 4, s = "124" Output: 5 Explanation: The powerful integers in the range [1..6000] are 124, 1124, 2124, 3124, and, 4124. All these integers have each digit <= 4, and "124" as a suffix. Note that 5124 is not a powerful integer because the first digit is 5 which is greater than 4. It can be shown that there are only 5 powerful integers in this range.
Example 2:
Input: start = 15, finish = 215, limit = 6, s = "10" Output: 2 Explanation: The powerful integers in the range [15..215] are 110 and 210. All these integers have each digit <= 6, and "10" as a suffix. It can be shown that there are only 2 powerful integers in this range.
Example 3:
Input: start = 1000, finish = 2000, limit = 4, s = "3000" Output: 0 Explanation: All integers in the range [1000..2000] are smaller than 3000, hence "3000" cannot be a suffix of any integer in this range.
Constraints:
1 <= start <= finish <= 10151 <= limit <= 91 <= s.length <= floor(log10(finish)) + 1s only consists of numeric digits which are at most limit.s does not have leading zeros.Problem summary: You are given three integers start, finish, and limit. You are also given a 0-indexed string s representing a positive integer. A positive integer x is called powerful if it ends with s (in other words, s is a suffix of x) and each digit in x is at most limit. Return the total number of powerful integers in the range [start..finish]. A string x is a suffix of a string y if and only if x is a substring of y that starts from some index (including 0) in y and extends to the index y.length - 1. For example, 25 is a suffix of 5125 whereas 512 is not.
Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.
Pattern signal: Math · Dynamic Programming
1 6000 4 "124"
15 215 6 "10"
1000 2000 4 "3000"
powerful-integers)numbers-with-repeated-digits)Source-backed implementations are provided below for direct study and interview prep.
// Accepted solution for LeetCode #2999: Count the Number of Powerful Integers
class Solution {
private String s;
private String t;
private Long[] f;
private int limit;
public long numberOfPowerfulInt(long start, long finish, int limit, String s) {
this.s = s;
this.limit = limit;
t = String.valueOf(start - 1);
f = new Long[20];
long a = dfs(0, true);
t = String.valueOf(finish);
f = new Long[20];
long b = dfs(0, true);
return b - a;
}
private long dfs(int pos, boolean lim) {
if (t.length() < s.length()) {
return 0;
}
if (!lim && f[pos] != null) {
return f[pos];
}
if (t.length() - pos == s.length()) {
return lim ? (s.compareTo(t.substring(pos)) <= 0 ? 1 : 0) : 1;
}
int up = lim ? t.charAt(pos) - '0' : 9;
up = Math.min(up, limit);
long ans = 0;
for (int i = 0; i <= up; ++i) {
ans += dfs(pos + 1, lim && i == (t.charAt(pos) - '0'));
}
if (!lim) {
f[pos] = ans;
}
return ans;
}
}
// Accepted solution for LeetCode #2999: Count the Number of Powerful Integers
func numberOfPowerfulInt(start, finish int64, limit int, s string) int64 {
t := strconv.FormatInt(start-1, 10)
f := make([]int64, 20)
for i := range f {
f[i] = -1
}
var dfs func(int, bool) int64
dfs = func(pos int, lim bool) int64 {
if len(t) < len(s) {
return 0
}
if !lim && f[pos] != -1 {
return f[pos]
}
if len(t)-pos == len(s) {
if lim {
if s <= t[pos:] {
return 1
}
return 0
}
return 1
}
ans := int64(0)
up := 9
if lim {
up = int(t[pos] - '0')
}
up = min(up, limit)
for i := 0; i <= up; i++ {
ans += dfs(pos+1, lim && i == int(t[pos]-'0'))
}
if !lim {
f[pos] = ans
}
return ans
}
a := dfs(0, true)
t = strconv.FormatInt(finish, 10)
for i := range f {
f[i] = -1
}
b := dfs(0, true)
return b - a
}
# Accepted solution for LeetCode #2999: Count the Number of Powerful Integers
class Solution:
def numberOfPowerfulInt(self, start: int, finish: int, limit: int, s: str) -> int:
@cache
def dfs(pos: int, lim: int) -> int:
if len(t) < n:
return 0
if len(t) - pos == n:
return int(s <= t[pos:]) if lim else 1
up = min(int(t[pos]) if lim else 9, limit)
ans = 0
for i in range(up + 1):
ans += dfs(pos + 1, lim and i == int(t[pos]))
return ans
n = len(s)
t = str(start - 1)
a = dfs(0, True)
dfs.cache_clear()
t = str(finish)
b = dfs(0, True)
return b - a
// Accepted solution for LeetCode #2999: Count the Number of Powerful Integers
impl Solution {
pub fn number_of_powerful_int(start: i64, finish: i64, limit: i32, s: String) -> i64 {
fn count(x: i64, limit: i32, s: &str) -> i64 {
let t = x.to_string();
if t.len() < s.len() {
return 0;
}
let t_bytes: Vec<u8> = t.bytes().collect();
let mut f = [-1_i64; 20];
fn dfs(pos: usize, lim: bool, t: &[u8], s: &str, limit: i32, f: &mut [i64; 20]) -> i64 {
if t.len() < s.len() {
return 0;
}
if !lim && f[pos] != -1 {
return f[pos];
}
if t.len() - pos == s.len() {
if lim {
let suffix = &t[pos..];
let suffix_str = String::from_utf8_lossy(suffix);
return if suffix_str.as_ref() >= s { 1 } else { 0 };
} else {
return 1;
}
}
let mut ans = 0;
let up = if lim {
(t[pos] - b'0').min(limit as u8)
} else {
limit as u8
};
for i in 0..=up {
let next_lim = lim && i == t[pos] - b'0';
ans += dfs(pos + 1, next_lim, t, s, limit, f);
}
if !lim {
f[pos] = ans;
}
ans
}
dfs(0, true, &t_bytes, s, limit, &mut f)
}
let a = count(start - 1, limit, &s);
let b = count(finish, limit, &s);
b - a
}
}
// Accepted solution for LeetCode #2999: Count the Number of Powerful Integers
function numberOfPowerfulInt(start: number, finish: number, limit: number, s: string): number {
let t: string = (start - 1).toString();
let f: number[] = Array(20).fill(-1);
const dfs = (pos: number, lim: boolean): number => {
if (t.length < s.length) {
return 0;
}
if (!lim && f[pos] !== -1) {
return f[pos];
}
if (t.length - pos === s.length) {
if (lim) {
return s <= t.substring(pos) ? 1 : 0;
}
return 1;
}
let ans: number = 0;
const up: number = Math.min(lim ? +t[pos] : 9, limit);
for (let i = 0; i <= up; i++) {
ans += dfs(pos + 1, lim && i === +t[pos]);
}
if (!lim) {
f[pos] = ans;
}
return ans;
};
const a: number = dfs(0, true);
t = finish.toString();
f = Array(20).fill(-1);
const b: number = dfs(0, true);
return b - a;
}
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.