Skip to main content
Talentd

Count the Number of Powerful Integers - Solution & Explanation

HardMathStringDynamic Programming28 min readAsked at: Meta, Google, Sprinklr +2
Practice this problem

Problem Statement

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 <= 1015
  • 1 <= limit <= 9
  • 1 <= s.length <= floor(log10(finish)) + 1
  • s only consists of numeric digits which are at most limit.
  • s does 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.

The C implementation uses basic string operations to verify if a number is powerful. It checks for the suffix match and ensures each digit is within the limit. The main function calculates the count by iterating through the range [start, finish].

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n * m) where n is the number of elements in the range and m is the length of each number in digits.
Space Complexity: O(1)

Try this approach in the editor →

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.

The detailed explanation of C implementation, describing direct construction of numbers without iterating through the entire range for efficiency.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: Reduced compared to brute force due to targeted number constructions.
Space Complexity: O(1)

Try this approach in the editor →

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:

  1. Convert start and finish to strings for easier manipulation in Digit DP.
  2. Design a function dfs(pos, lim), which represents the count of valid numbers starting from the pos-th digit, with the current restriction condition lim.
  3. If the maximum number of digits is less than the length of s, return 0.
  4. If the remaining number of digits equals the length of s, check if the current number satisfies the condition and return 1 or 0.
  5. Otherwise, calculate the upper limit of the current digit as up = min(lim ? t[pos] : 9, limit). Then iterate through the digits i from 0 to up, recursively call dfs(pos + 1, lim \&\& i == t[pos]), and accumulate the results.
  6. If lim is false, store the current result in the cache to avoid redundant calculations.
  7. 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$.

Code

PythonJavaC++GoTypeScriptRustC#

Python

Java

C++

Go

TypeScript

Rust

C#

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Brute Force Generation

Time Complexity: O(n * m) where n is the number of elements in the range and m is the length of each number in digits.
Space Complexity: O(1)

Mathematical Construction

Time Complexity: Reduced compared to brute force due to targeted number constructions.
Space Complexity: O(1)

Digit DP—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Range IterationO(n * d)O(1)Small numeric ranges where iterating every number is feasible
Digit Generation with ValidationO(k * d)O(d)When generating candidate numbers with digit constraints before filtering
Mathematical Construction / Digit DPO(d)O(d)Large ranges where counting valid prefixes is far more efficient than enumeration

Video Solution

Count the Number of Powerful Integers | Detailed Thought Process | Leetcode 2999 | codestorywithMIK • codestorywithMIK • 13,306 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice Count the Number of Powerful Integers with our built-in code editor and test cases.

Practice on FleetCode
Previous

Numbers With Repeated Digits

Next

Powerful Integers