Count the Number of Powerful Integers — Problem & Solution
Count the Number of Powerful Integers solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.
Count the Number of Powerful Integers is a hard coding problem on strings, dynamic programming and math, asked in Google interviews.
- Difficulty: Hard
- Topics: Strings, Dynamic Programming, Math, Digit DP
- Asked at: Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given integers start, finish and limit, and a string s of digits representing a positive integer.
A positive integer x is powerful if its decimal representation ends with s (that is, s is a suffix of x) and every digit of x is at most limit.
Return how many powerful integers lie in the inclusive range [start, finish].
Example 1
Input: start = 1, finish = 6000, limit = 4, s = "124"
Output: 5
Explanation: 124, 1124, 2124, 3124 and 4124. 5124 ends with 124 but its digit 5 exceeds the limit.
Example 2
Input: start = 15, finish = 215, limit = 6, s = "10"
Output: 2
Explanation: 110 and 210.
Example 3
Input: start = 1000, finish = 2000, limit = 4, s = "3000"
Output: 0
Explanation: Every number in the range is smaller than 3000, so none can end with it.
Constraints
1 <= start <= finish <= 10^9 (reduced from 10^15 so the count fits a 32-bit integer)1 <= limit <= 91 <= s.length <= floor(log10(finish)) + 1s consists only of digits, each at most limits has no leading zeros
Hints for Count the Number of Powerful Integers
Hint 1
Count powerful integers in
[1, n]with a functionf(n); the answer isf(finish) - f(start - 1).Hint 2
A powerful integer is some prefix
p(possibly empty) followed bys. Every digit ofpmust be at mostlimit, so there arelimit + 1choices per digit.Hint 3
Walk the first
len(n) - len(s)digits ofn. If a digit exceedslimit, every smaller-digit choice there completes freely: add(limit + 1)^(remaining)and stop. Otherwise adddigit · (limit + 1)^(remaining - 1)and continue. At the end, countn's own prefix ifn's lastlen(s)digits are at leasts.
How to solve Count the Number of Powerful Integers
Strip the fixed suffix: a powerful number ≤ n is a prefix p written with digits 0..limit, followed by s. Counting such prefixes that keep the whole number at most n is a short digit walk over n's leading digits.
Approach
- Define
f(n); returnf(finish) - f(start - 1). - Let
Nbenas a string. If it is shorter thans, return 0. Letk = len(N) - len(s)be the number of prefix digits (prefixes shorter thankare covered as leading zeros). - For
i = 0..k-1with digitd = N[i]: ifd > limit, add(limit + 1)^(k - i)— every allowed digit here is belowd, and the rest is free — and return. Otherwise addd · (limit + 1)^(k - i - 1)for the choices smaller thand, and keepd. - If the loop finishes, the prefix equals
N's prefix; add 1 ifN's lastlen(s)digits, compared as a string, are≥ s.
Why it works
Two numbers with the same suffix s compare like their prefixes, and padding a shorter prefix with leading zeros does not change it, so counting length-k digit strings over 0..limit that are ≤ N's prefix (strictly smaller, or equal with a large-enough suffix) counts every powerful number up to n exactly once. A digit above limit cannot be matched, so all prefixes that branch below it are counted and nothing equal remains.
Complexity
- Time —
O(len(finish)) - Space —
O(1)
Pitfalls
- Leading zeros in the prefix are fine — they correspond to shorter numbers — but
sitself has none, so it is never confused with a number having fewer digits. - Compare the final suffix of
nwithsas equal-length strings, not character by character againstlimit. f(start - 1)may be called with 0.
Reference solution
Python
def numberOfPowerfulInt(start: int, finish: int, limit: int, s: str) -> int:
def count(n):
N = str(n)
if len(N) < len(s):
return 0
k = len(N) - len(s)
ans = 0
for i in range(k):
d = ord(N[i]) - 48
if d > limit:
return ans + (limit + 1) ** (k - i)
ans += d * (limit + 1) ** (k - i - 1)
if N[k:] >= s:
ans += 1
return ans
return count(finish) - count(start - 1)Java
static long powerfulUpTo(long n, int limit, String s) {
String N = Long.toString(n);
if (N.length() < s.length()) return 0;
int k = N.length() - s.length();
long[] pw = new long[k + 1];
pw[0] = 1;
for (int i = 1; i <= k; i++) pw[i] = pw[i - 1] * (limit + 1);
long ans = 0;
for (int i = 0; i < k; i++) {
int d = N.charAt(i) - '0';
if (d > limit) return ans + pw[k - i];
ans += d * pw[k - i - 1];
}
if (N.substring(k).compareTo(s) >= 0) ans++;
return ans;
}
public static int numberOfPowerfulInt(int start, int finish, int limit, String s) {
return (int) (powerfulUpTo(finish, limit, s) - powerfulUpTo((long) start - 1, limit, s));
}C++
long long powerfulUpTo(long long n, int limit, const string& s) {
string N = to_string(n);
if (N.size() < s.size()) return 0;
int k = N.size() - s.size();
vector<long long> pw(k + 1, 1);
for (int i = 1; i <= k; i++) pw[i] = pw[i - 1] * (limit + 1);
long long ans = 0;
for (int i = 0; i < k; i++) {
int d = N[i] - '0';
if (d > limit) return ans + pw[k - i];
ans += d * pw[k - i - 1];
}
if (N.substr(k) >= s) ans++;
return ans;
}
int numberOfPowerfulInt(int start, int finish, int limit, string s) {
return (int) (powerfulUpTo(finish, limit, s) - powerfulUpTo((long long) start - 1, limit, s));
}JavaScript
var numberOfPowerfulInt = function(start, finish, limit, s) {
var count = function(n) {
var N = String(n);
if (N.length < s.length) return 0;
var k = N.length - s.length, ans = 0;
for (var i = 0; i < k; i++) {
var d = N.charCodeAt(i) - 48;
if (d > limit) return ans + Math.pow(limit + 1, k - i);
ans += d * Math.pow(limit + 1, k - i - 1);
}
if (N.substring(k) >= s) ans++;
return ans;
};
return count(finish) - count(start - 1);
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 515 strings problems · the whole catalogue
Learn the technique: Strings · Dynamic Programming