Count the Number of Powerful Integers solution and explanation
Google
9 more videos on this problem
Count the Number of Powerful Integers | Detailed Thought Process | Leetcode 2999 | codestorywithMIKcodestorywithMIK · 45:21 · 13K views
Count the Number of Powerful Integers | Leetcode 2999Techdose · 46:22 · 8K views
Count the Number of Powerful Integers | Digit DP | Hard Cases ProblemAryan Mittal · 41:38 · 8K views
LeetCode 2999. Count the Number of Powerful Integers | 🍥 Chakra-Controlled DP Made Easy!Code Crusaders · 6:10 · 3K views
Leetcode 2999. Count the Number of Powerful Integers | Python Digit DP SolutionStatLearn Tech · 19:06 · 1K views
10034. Count the Number of Powerful Integers | Leetcode Biweekly 121codingMohan · 43:41 · 1K views
2999 Count the Number of Powerful Integers | LeetCodeR Sai Siddhu · 15:50 · 965 views
LeetCode 2999 Count the Number of Powerful Integers | Easy Brute Force - Digit DPCode Harmony · 26:54 · 887 views
2999. Count the Number of Powerful Integers | Leetcode Daily - PythonLeetcode Daily · 9:00 · 723 views
Daily Leetcode #1836: Apr 10, 2025 - 2999. Count the Number of Powerful IntegersProgramming Live with Larry · 1:16:51 · 666 views
The problem
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)) + 1sonly consists of numeric digits which are at mostlimit.sdoes not have leading zeros.
Approach overview
Problem Overview: You are given a range [start, finish], a digit limit, and a string s. A number is considered powerful if every digit is ≤ limit and the number ends with the suffix s. The task is to count how many such integers exist inside the range.
Approach 1: Brute Force Generation (O(n * d) time, O(1) space)
The most direct approach iterates through every number between start and finish. Convert each number to a string, check whether it ends with s, and verify that every digit is ≤ limit. The suffix comparison is a simple string operation, while the digit validation scans each character. This method works for small ranges but becomes infeasible when the interval spans millions or billions of numbers.
An alternative brute force variation generates numbers digit by digit where each digit is ≤ limit, then filters those ending with s and inside the range. Both variants still explore too many candidates when the bounds are large.
Approach 2: Mathematical Construction / Digit DP (O(d) time, O(d) space)
The key observation: every valid number must end with the fixed suffix s. Instead of scanning the entire range, treat the number as prefix + s. Only the prefix digits vary, and every digit in the prefix must also be ≤ limit. The problem reduces to counting valid prefixes such that the full number lies within [start, finish].
Convert the bounds into strings and compute how many prefixes produce numbers ≤ a given bound. This is a classic dynamic programming over digits problem. At each position, decide which digit (0…limit) can be placed while respecting the tight constraint of the bound. The suffix is fixed, so the DP only processes the prefix portion.
To get the final result, compute count(finish) - count(start - 1). Each count(x) counts valid numbers ≤ x. The DP ensures digits never exceed the limit and the constructed number always ends with s. This approach avoids enumerating the range and runs in time proportional to the number of digits.
The logic combines ideas from math and digit constraints with suffix matching from string handling. The result is efficient even when the numeric range is extremely large.
Recommended for interviews: The mathematical construction with digit DP is the expected solution. Brute force demonstrates understanding of the constraints, but the DP approach shows that you can transform the range problem into a prefix-counting problem and handle digit constraints efficiently.
Approach 1: Brute Force Generation
This approach involves generating numbers by appending different prefixes to 's', checking if they're powerful numbers within the specified range. We start by generating the smallest number that ends with 's' and continue checking larger numbers by incrementally adding allowed digits as prefixes. We'll ensure each prefix leads to a number < or = finish and continues applying constraints until finish is no longer reachable with valid digits.
def count_powerful_integers(start, finish, limit, s):
count = 0
for num in range(start, finish + 1):
str_num = str(num)
if str_num.endswith(s) and all(int(d) <= limit for d in str_num):
count += 1
return count
start = 1
finish = 6000
limit = 4
s = "124"
print(count_powerful_integers(start, finish, limit, s))public class PowerfulIntegers {
public static void main(String[] args) {
int start = 1, finish = 6000, limit = 4;
String s = "124";
System.out.println(countPowerfulIntegers(start, finish, limit, s));
}
public static int countPowerfulIntegers(int start, int finish, int limit, String s) {
int count = 0;
for (int i = start; i <= finish; i++) {
String number = Integer.toString(i);
if (number.endsWith(s) && validDigits(number, limit)) {
count++;
}
}
return count;
}
private static boolean validDigits(String number, int limit) {
for (char c : number.toCharArray()) {
if (c - '0' > limit) return false;
}
return true;
}
}#include <iostream>
#include <string>
using namespace std;
bool isSuffix(const string& number, const string& suffix) {
if (number.size() < suffix.size()) return false;
return number.substr(number.size() - suffix.size()) == suffix;
}
bool validDigits(const string& number, int limit) {
for (char digit : number) {
if (digit - '0' > limit) return false;
}
return true;
}
int countPowerfulIntegers(int start, int finish, int limit, const string& s) {
int count = 0;
for (int i = start; i <= finish; i++) {
string number = to_string(i);
if (isSuffix(number, s) && validDigits(number, limit)) {
count++;
}
}
return count;
}
int main() {
int start = 1, finish = 6000, limit = 4;
string s = "124";
cout << countPowerfulIntegers(start, finish, limit, s) << endl;
return 0;
}function countPowerfulIntegers(start, finish, limit, s) {
let count = 0;
for (let num = start; num <= finish; num++) {
const strNum = num.toString();
if (strNum.endsWith(s) && [...strNum].every(digit => Number(digit) <= limit)) {
count++;
}
}
return count;
}
const start = 1;
const finish = 6000;
const limit = 4;
const s = "124";
console.log(countPowerfulIntegers(start, finish, limit, s));#include <stdio.h>
#include <stdbool.h>
#include <string.h>
bool isPowerful(int num, int limit, const char *suffix) {
char str[20];
sprintf(str, "%d", num);
int len = strlen(str);
int suffixLen = strlen(suffix);
if (len < suffixLen || strcmp(str + len - suffixLen, suffix) != 0)
return false;
for (int i = 0; i < len; i++) {
if (str[i] - '0' > limit) return false;
}
return true;
}
int countPowerfulIntegers(int start, int finish, int limit, const char *suffix) {
int count = 0;
for (int i = start; i <= finish; i++) {
if (isPowerful(i, limit, suffix)) {
count++;
}
}
return count;
}
int main() {
int start = 1, finish = 6000, limit = 4;
char s[] = "124";
printf("%d\n", countPowerfulIntegers(start, finish, limit, s));
return 0;
}using System;
public class PowerfulIntegers {
public static void Main(string[] args) {
int start = 1, finish = 6000, limit = 4;
string s = "124";
Console.WriteLine(CountPowerfulIntegers(start, finish, limit, s));
}
public static int CountPowerfulIntegers(int start, int finish, int limit, string s) {
int count = 0;
for (int i = start; i <= finish; i++) {
string number = i.ToString();
if (number.EndsWith(s) && ValidDigits(number, limit)) {
count++;
}
}
return count;
}
private static bool ValidDigits(string number, int limit) {
foreach (char c in number) {
if (c - '0' > limit) return false;
}
return true;
}
}This Python code iterates through the range [start, finish], converting each number to a string. It checks if the number ends with the given suffix 's' and if all digits are less than or equal to limit.
Time Complexity: O(n * m), where n is the numbers to check, and m is the transform and verification time per number.
Space Complexity: O(1)
Approach 2: Mathematical Construction
This alternative approach leverages carefully constructing numbers using suffix 's' with digits 0 to limit appended as prefixes. We eliminate numbers not in range by direct construction, reducing iteration. This requires potential backtracking to build valid numbers and avoid unnecessary calculations.
def targeted_powerful_construction(start, finish, limit, s):
# Implementation for efficient construction strategy
pass
start = 1
finish = 6000
limit = 4
s = "124"
# Result placeholder
# print(targeted_powerful_construction(start, finish, limit, s))/* Placeholder for complete mathematical approach Java solution *//* Placeholder for complete mathematical approach C++ solution *//* Placeholder for complete mathematical approach JavaScript solution *//* Placeholder for complete mathematical approach C solution *//* Placeholder for complete mathematical approach C# solution */Description for Python implementation leveraging constructive approach, skipping irrelevant checks.
Time Complexity: Considerable reductions leveraging arithmetic operations and selective validations.
Space Complexity: O(1)
Approach 3: Digit DP
This problem is essentially about finding the count of numbers in the given range [l, .., r] that satisfy the conditions. The count depends on the number of digits and the value of each digit. We can solve this problem using the Digit DP approach, where the size of the number has minimal impact on the complexity.
For the range [l, .., r], we typically transform it into two subproblems: [1, .., r] and [1, .., l - 1], i.e.,
$
ans = sum_{i=1}^{r} ans_i - sum_{i=1}^{l-1} ans_i
For this problem, we calculate the count of numbers in [1, finish] that satisfy the conditions, and subtract the count of numbers in [1, start - 1] that satisfy the conditions to get the final answer.
We use memoization to implement Digit DP. Starting from the topmost digit, we recursively calculate the number of valid numbers, accumulate the results layer by layer, and finally return the answer from the starting point.
The basic steps are as follows:
- Convert start
andfinishto strings for easier manipulation in Digit DP. - Design a function dfs(pos, lim)
, which represents the count of valid numbers starting from thepos-th digit, with the current restriction conditionlim. - If the maximum number of digits is less than the length of s
, return 0. - If the remaining number of digits equals the length of s
, check if the current number satisfies the condition and return 1 or 0. - Otherwise, calculate the upper limit of the current digit as up = min(lim ? t[pos] : 9, limit)
. Then iterate through the digitsifrom 0 toup, recursively calldfs(pos + 1, lim \&\& i == t[pos]), and accumulate the results. - If lim
is false, store the current result in the cache to avoid redundant calculations. - Finally, return the result.
The answer is the count of valid numbers in [1, finish] minus the count of valid numbers in [1, start - 1].
Time complexity is O(log M times D), and space complexity is O(log M), where M is the upper limit of the number, and D = 10$.
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;
}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
}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
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Brute Force Generation | Time Complexity: O(n * m), where n is the numbers to check, and m is the transform and verification time per number. |
| Mathematical Construction | Time Complexity: Considerable reductions leveraging arithmetic operations and selective validations. |
| Digit DP | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Range Iteration | O(n * d) | O(1) | Small numeric ranges where iterating every number is feasible |
| Digit Generation with Validation | O(k * d) | O(d) | When generating candidate numbers with digit constraints before filtering |
| Mathematical Construction / Digit DP | O(d) | O(d) | Large ranges where counting valid prefixes is far more efficient than enumeration |
Frequently asked questions
Is Count the Number of Powerful Integers easy or hard?
The problem is classified as Hard because it combines range queries, suffix constraints, and digit limits. A brute force idea is simple, but deriving the prefix counting strategy with digit DP requires strong understanding of number construction and dynamic programming.
Count the Number of Powerful Integers Python/Java solution
Most implementations build a helper function count(x) using digit DP to count valid numbers ≤ x. The final answer is count(finish) - count(start - 1). The same logic works across Python, Java, C++, and other languages because it relies only on string conversion and memoized recursion.
How to solve Count the Number of Powerful Integers in O(d)?
Fix the suffix s and treat valid numbers as prefix + s. Count how many prefixes produce numbers ≤ finish while ensuring every digit is ≤ limit. Use digit DP with a tight bound flag to enforce the upper limit. Compute the result as count(finish) minus count(start - 1).
What is the best approach for Count the Number of Powerful Integers?
The most efficient approach uses mathematical construction with digit dynamic programming (Digit DP). Instead of scanning the entire range, treat each number as prefix + suffix and count how many valid prefixes exist. This reduces the problem to counting numbers with digit constraints up to a bound, giving roughly O(d) complexity where d is the number of digits.
Is Count the Number of Powerful Integers asked at Google/Amazon/Meta?
Problems involving digit DP and constrained number counting frequently appear in interviews at companies like Google, Amazon, and Meta. Variants often involve counting numbers with digit restrictions, suffix constraints, or range queries.
What data structure is used in Count the Number of Powerful Integers?
The optimal solution primarily uses digit dynamic programming with memoization. The DP state typically tracks the current digit index, whether the prefix is tight with the bound, and the allowed digit range determined by the limit.
What is the time complexity of Count the Number of Powerful Integers?
The optimal digit DP solution runs in O(d) time and O(d) space, where d is the number of digits in the bound (typically ≤ 18 for 64‑bit integers). Brute force iteration across the range takes O(n * d) time because every number must be checked and each digit validated.