# Count the Number of Powerful Integers
**Difficulty:** HARD
[External](https://leetcode.com/problems/count-the-number-of-powerful-integers)
Canonical: https://scaleengineer.com/dsa/problems/count-the-number-of-powerful-integers
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Data structures:** String
**Companies:** [HashedIn](https://scaleengineer.com/companies/hashedin), [Sprinklr](https://scaleengineer.com/companies/sprinklr)
---
## 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 <= 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.

# Approaches
## Brute Force Iteration
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`.
**Time:** O((finish - start) * log10(finish)) · **Space:** O(log10(finish))
**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.
### Explanation
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.

```java
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`.
### Algorithm
- Initialize a counter `powerful_count` to 0.
- Iterate through each integer `x` from `start` to `finish`.
- For each integer `x`, check if it is a powerful integer:
  - Convert `x` to its string representation, `x_str`.
  - **Suffix Check**: Verify if `x_str` ends with the given suffix string `s`.
  - **Digit Limit Check**: If the suffix check passes, iterate through each character (digit) of `x_str`. If any digit is greater than `limit`, the number is not powerful.
- If `x` satisfies both conditions, increment `powerful_count`.
- After the loop finishes, return `powerful_count`.

## Digit DP with Prefix Transformation
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.
**Time:** O(log10(finish)) · **Space:** O(log10(finish))
**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.
### Explanation
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`:

1.  `x <= N` becomes `p * 10^s.length() + s_val <= N`, which simplifies to `p <= (N - s_val) / 10^s.length()`. Let's call this upper bound `max_p`.
2.  All digits of `x` must be `<= limit`. Since the problem guarantees that digits of `s` are already `<= limit`, we only need to ensure that all digits of the prefix `p` are 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. If `true`, it means the prefix we've built so far matches the prefix of `max_p`, so the current digit is bounded by the corresponding digit in `max_p`. If `false`, we can use any digit up to `limit`.

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)`.

```java
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;
    }
}
```
### Algorithm
- The problem of counting in a range `[start, finish]` is solved by finding `count(finish) - count(start - 1)`.
- Implement a helper function `count(N)` that counts powerful integers up to `N`.
- Inside `count(N)`:
  - A powerful integer `x` has the form `p * 10^k + s_val`, where `k` is the length of `s` and `s_val` is its integer value.
  - The condition `x <= N` is transformed into an upper bound for the prefix `p`: `p <= (N - s_val) / 10^k`. Let this be `max_p`.
  - The problem reduces to counting integers `p` in `[0, max_p]` where all digits of `p` are at most `limit`.
- This new counting problem is solved using digit dynamic programming.
  - Define a recursive function `solve(p_str, index, is_tight)` with memoization.
  - `p_str` is the string for `max_p`.
  - `index` is the current digit position being built.
  - `is_tight` is a boolean to track if we are restricted by the digits of `p_str`.
  - The function recursively counts the number of valid prefixes `p` from `0` to `max_p`.

# Solutions
### CSharp

```csharp
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 ; } }
```

### Java

```java
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;
  }
}

```

### Python

```python
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 - a

```

### CPP

```cpp
class 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;
  }
};

```