Count the Number of Powerful Integers
HardPrompt
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.
Approaches
2 approaches with complexity analysis and trade-offs.
This approach involves a straightforward iteration through every integer in the given range [start, finish]. For each integer, it performs checks to determine if it qualifies as a 'powerful integer' based on the two specified conditions: having s as a suffix and all its digits being within the limit.
Algorithm
- Initialize a counter
powerful_countto 0. - Iterate through each integer
xfromstarttofinish. - For each integer
x, check if it is a powerful integer:- Convert
xto its string representation,x_str. - Suffix Check: Verify if
x_strends with the given suffix strings. - Digit Limit Check: If the suffix check passes, iterate through each character (digit) of
x_str. If any digit is greater thanlimit, the number is not powerful.
- Convert
- If
xsatisfies both conditions, incrementpowerful_count. - After the loop finishes, return
powerful_count.
Walkthrough
The brute-force method directly translates the problem definition into code. It uses a loop that runs from start to finish. Inside the loop, each number is tested.
To test a number i, we first check the suffix condition. This is easily done by converting both the number i and the suffix s into strings and using the endsWith string method.
If the suffix condition is met, we proceed to the second condition: the digit limit. We can iterate through the digits of i (either by using modulo and division arithmetic or by iterating through its string representation) and check if each digit is less than or equal to limit.
If a number successfully passes both checks, we increment a counter. The final value of this counter is the result.
class Solution { public long numberOfPowerfulInt(long start, long finish, int limit, String s) { long count = 0; for (long i = start; i <= finish; i++) { if (isPowerful(i, limit, s)) { count++; } } return count; } private boolean isPowerful(long num, int limit, String s) { String numStr = String.valueOf(num); // 1. Suffix check if (!numStr.endsWith(s)) { return false; } // 2. Digit limit check for (char c : numStr.toCharArray()) { if ((c - '0') > limit) { return false; } } return true; }}While simple, this approach is not feasible for the given constraints where finish can be up to 10^15.
Complexity
Time
O((finish - start) * log10(finish))
Space
O(log10(finish))
Trade-offs
Pros
Simple to understand and implement.
Correct for small ranges.
Cons
Extremely inefficient for large ranges, leading to a 'Time Limit Exceeded' error on most platforms for the given constraints.
This highly efficient approach leverages digit dynamic programming (DP) combined with a clever problem transformation. Instead of iterating through the large range, we calculate the count of powerful integers up to finish and subtract the count up to start - 1. The core of the method is a function that counts powerful integers up to a given number N, which is implemented by transforming the problem into counting valid 'prefixes' and then using digit DP.
Algorithm
- The problem of counting in a range
[start, finish]is solved by findingcount(finish) - count(start - 1). - Implement a helper function
count(N)that counts powerful integers up toN. - Inside
count(N):- A powerful integer
xhas the formp * 10^k + s_val, wherekis the length ofsands_valis its integer value. - The condition
x <= Nis transformed into an upper bound for the prefixp:p <= (N - s_val) / 10^k. Let this bemax_p. - The problem reduces to counting integers
pin[0, max_p]where all digits ofpare at mostlimit.
- A powerful integer
- This new counting problem is solved using digit dynamic programming.
- Define a recursive function
solve(p_str, index, is_tight)with memoization. p_stris the string formax_p.indexis the current digit position being built.is_tightis a boolean to track if we are restricted by the digits ofp_str.- The function recursively counts the number of valid prefixes
pfrom0tomax_p.
- Define a recursive function
Walkthrough
The key insight is to rephrase the problem. A powerful integer x is composed of a prefix p and the fixed suffix s. So, x can be represented as p * 10^s.length() + s_val. The constraints on x can be translated into constraints on p:
x <= Nbecomesp * 10^s.length() + s_val <= N, which simplifies top <= (N - s_val) / 10^s.length(). Let's call this upper boundmax_p.- All digits of
xmust be<= limit. Since the problem guarantees that digits ofsare already<= limit, we only need to ensure that all digits of the prefixpare also<= limit.
So, the problem is now to count the number of integers p from 0 to max_p where every digit of p is at most limit. This is a classic digit DP problem.
We can create a recursive function, say solve(index, is_tight), to count these valid prefixes.
index: The current digit of the prefix we are considering (from left to right).is_tight: A boolean flag. Iftrue, it means the prefix we've built so far matches the prefix ofmax_p, so the current digit is bounded by the corresponding digit inmax_p. Iffalse, we can use any digit up tolimit.
We use memoization on the state (index, is_tight) to store results and avoid redundant computations. The final answer for count(N) is the result of this DP. The overall solution is count(finish) - count(start - 1).
class Solution { private String s; private int limit; private Long[][] memo; private String pStr; public long numberOfPowerfulInt(long start, long finish, int limit, String s) { this.s = s; this.limit = limit; long ans = count(finish) - count(start - 1); return ans; } private long count(long n) { long sVal; try { sVal = Long.parseLong(s); } catch (NumberFormatException e) { // This case is unlikely given constraints but good for robustness. // If s is longer than n's string representation, no powerful int exists. if (s.length() > String.valueOf(n).length()) return 0; // If same length, compare lexicographically. if (s.length() == String.valueOf(n).length() && s.compareTo(String.valueOf(n)) > 0) return 0; // For very large s, BigInteger would be needed, but constraints allow long. sVal = -1; // Should not happen } if (n < sVal) { return 0; } long powerOf10 = 1L; for (int i = 0; i < s.length(); i++) { powerOf10 *= 10; } long maxP = (n - sVal) / powerOf10; this.pStr = String.valueOf(maxP); this.memo = new Long[pStr.length()][2]; // This counts numbers in [0, maxP] where all digits are <= limit. // Each such number corresponds to a valid prefix p. return solve(0, true); } private long solve(int index, boolean isTight) { if (index == pStr.length()) { return 1; // Found one valid prefix number } if (memo[index][isTight ? 1 : 0] != null) { return memo[index][isTight ? 1 : 0]; } long ans = 0; int upperBound = isTight ? (pStr.charAt(index) - '0') : 9; int digitLimit = Math.min(upperBound, limit); for (int digit = 0; digit <= digitLimit; digit++) { boolean newTight = isTight && (digit == upperBound); ans += solve(index + 1, newTight); } return memo[index][isTight ? 1 : 0] = ans; }}Complexity
Time
O(log10(finish))
Space
O(log10(finish))
Trade-offs
Pros
Highly efficient and can handle the large constraints of the problem.
It's a generalizable technique for a wide class of 'counting numbers with properties' problems.
Cons
More complex to understand and implement than the brute-force approach.
Requires careful handling of number conversions and the digit DP state.
Solutions
Solution
public 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 = ( start - 1 ). ToString (); f = new long ?[ 20 ]; long a = Dfs ( 0 , true ); t = finish . ToString (); f = new long ?[ 20 ]; long b = Dfs ( 0 , true ); return b - a ; } private long Dfs ( int pos , bool lim ) { if ( t . Length < s . Length ) { return 0 ; } if (! lim && f [ pos ]. HasValue ) { return f [ pos ]. Value ; } if ( t . Length - pos == s . Length ) { return lim ? ( string . Compare ( s , t . Substring ( pos )) <= 0 ? 1 : 0 ) : 1 ; } int up = lim ? t [ 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 [ pos ] - '0' )); } if (! lim ) { f [ pos ] = ans ; } return ans ; } }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; }}class Solution: def numberOfPowerfulInt(self, start: int, finish: int, limit: int, s: str) -> int: @ cache def dfs(pos: int, lim: 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 - aclass Solution {public: long long numberOfPowerfulInt(long long start, long long finish, int limit, string s) { string t = to_string(start - 1); long long f[20]; memset(f, -1, sizeof(f)); function<long long(int, bool)> dfs = [&](int pos, bool lim) -> long long { if (t.size() < s.size()) { return 0; } if (!lim && f[pos] != -1) { return f[pos]; } if (t.size() - pos == s.size()) { return lim ? s <= t.substr(pos) : 1; } long long ans = 0; int up = min(lim ? t[pos] - '0' : 9, limit); for (int i = 0; i <= up; ++i) { ans += dfs(pos + 1, lim && i == (t[pos] - '0')); } if (!lim) { f[pos] = ans; } return ans; }; long long a = dfs(0, true); t = to_string(finish); memset(f, -1, sizeof(f)); long long b = dfs(0, true); return b - a; }};Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.