Count the Number of Powerful Integers

Hard
1647.

Count the Number of Powerful Integers

Count the Number of Powerful Integers is a hard coding problem on strings, dynamic programming and math, asked in Google interviews.

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 <= 9
  • 1 <= s.length <= floor(log10(finish)) + 1
  • s consists only of digits, each at most limit
  • s has no leading zeros
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number} start
 * @param {number} finish
 * @param {number} limit
 * @param {string} s
 * @return {number}
 */
var numberOfPowerfulInt = function(start, finish, limit, s) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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.

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 <= 9
  • 1 <= s.length <= floor(log10(finish)) + 1
  • s consists only of digits, each at most limit
  • s has no leading zeros

Hints for Count the Number of Powerful Integers

  1. Hint 1

    Count powerful integers in [1, n] with a function f(n); the answer is f(finish) - f(start - 1).

  2. Hint 2

    A powerful integer is some prefix p (possibly empty) followed by s. Every digit of p must be at most limit, so there are limit + 1 choices per digit.

  3. Hint 3

    Walk the first len(n) - len(s) digits of n. If a digit exceeds limit, every smaller-digit choice there completes freely: add (limit + 1)^(remaining) and stop. Otherwise add digit · (limit + 1)^(remaining - 1) and continue. At the end, count n's own prefix if n's last len(s) digits are at least s.

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

  1. Define f(n); return f(finish) - f(start - 1).
  2. Let N be n as a string. If it is shorter than s, return 0. Let k = len(N) - len(s) be the number of prefix digits (prefixes shorter than k are covered as leading zeros).
  3. For i = 0..k-1 with digit d = N[i]: if d > limit, add (limit + 1)^(k - i) — every allowed digit here is below d, and the rest is free — and return. Otherwise add d · (limit + 1)^(k - i - 1) for the choices smaller than d, and keep d.
  4. If the loop finishes, the prefix equals N's prefix; add 1 if N's last len(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 s itself has none, so it is never confused with a number having fewer digits.
  • Compare the final suffix of n with s as equal-length strings, not character by character against limit.
  • 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