2999. Count the Number of Powerful Integers

[mah-shamim]

Topics: Math, String, Dynamic Programming

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.

Hint:

1. We can use digit DP to count powerful integers in the range [1, x].
2. Let dp[i][j] be the number of integers that have i digits (with allowed leading 0s) and j refers to the comparison between the current number and the prefix of x, j == 0 if the i-digit number formed currently is identical to the leftmost i digits of x, else if j ==1 it means the i-digit number is smaller than the leftmost i digits of x.
3. The answer is count[finish] - count[start - 1], where count[i] refers to the number of powerful integers in the range [1..i].

[mah-shamim]

We need to count the number of powerful integers within a given range [start, finish]. A powerful integer is defined as a number that ends with a given suffix string s and all its digits are at most a given limit. The solution involves using digit dynamic programming (DP) to efficiently count valid numbers without iterating through each number in the range.

Approach

1. Check for Direct Suffix Match: First, check if the integer value of the suffix s (denoted as s_num) lies within the range [start, finish]. If it does, this is a valid powerful integer.
2. Calculate Bounds for Prefix: For numbers formed by appending s to a prefix, compute the valid range of prefixes such that the resulting number lies within [start, finish]. The prefix must be a non-zero number with all digits ≤ limit.
3. Digit Dynamic Programming: Use digit DP to count valid prefixes within the computed range. This involves recursively checking each digit position while keeping track of constraints (tight bounds and leading zeros).

Let's implement this solution in PHP: 2999. Count the Number of Powerful Integers

<?php
/**
 * @param Integer $start
 * @param Integer $finish
 * @param Integer $limit
 * @param String $s
 * @return Integer
 */
function numberOfPowerfulInt($start, $finish, $limit, $s) {
    $s_num = (int)$s;
    $s_len = strlen($s);
    $total = 0;

    // Check if the suffix itself is within the range
    if ($s_num >= $start && $s_num <= $finish) {
        $total += 1;
    }

    $pow10s = pow(10, $s_len);

    // Calculate upper bound for P
    $temp = $finish - $s_num;
    if ($temp < 0) {
        return $total;
    }
    $upper_p = (int)($temp / $pow10s);

    // No valid P if upper_p is less than 1
    if ($upper_p < 1) {
        return $total;
    }

    // Calculate lower bound for P
    $lower_p = 1;
    if ($start > $s_num) {
        $numerator = $start - $s_num;
        $lower_p = (int)ceil($numerator / $pow10s);
        $lower_p = max(1, $lower_p);
    }

    if ($lower_p > $upper_p) {
        return $total;
    }

    // Calculate the count of valid P in [lower_p, upper_p]
    $count_upper = count_valid($upper_p, $limit);
    $count_lower = ($lower_p > 1) ? count_valid($lower_p - 1, $limit) : 0;
    $count_p = $count_upper - $count_lower;

    $total += $count_p;

    return $total;
}

/**
 * Helper function to count valid numbers up to X with digits <= limit and no leading zeros
 *
 * @param $X
 * @param $limit
 * @return int|mixed
 */
function count_valid($X, $limit) {
    if ($X < 1) {
        return 0;
    }

    $digits = str_split((string)$X);
    $n = count($digits);
    $memo = array();

    $dfs = function ($pos, $tight, $leading_zero, $digits, $limit, &$memo) use (&$dfs) {
        if ($pos == count($digits)) {
            return $leading_zero ? 0 : 1;
        }

        $key = "$pos," . ($tight ? '1' : '0') . "," . ($leading_zero ? '1' : '0');
        if (isset($memo[$key])) {
            return $memo[$key];
        }

        $max_digit = $tight ? (int)$digits[$pos] : 9;
        $max_digit = min($max_digit, $limit);

        $count = 0;
        for ($d = 0; $d <= $max_digit; $d++) {
            $new_tight = $tight && ($d == (int)$digits[$pos]);
            $new_leading_zero = $leading_zero && ($d == 0);

            if ($new_leading_zero) {
                $count += $dfs($pos + 1, $new_tight, $new_leading_zero, $digits, $limit, $memo);
            } else {
                // Check if we are transitioning from leading zero to non-zero
                if ($leading_zero && $d != 0) {
                    if ($d > $limit) {
                        continue;
                    }
                    $count += $dfs($pos + 1, $new_tight, false, $digits, $limit, $memo);
                } else {
                    $count += $dfs($pos + 1, $new_tight, false, $digits, $limit, $memo);
                }
            }
        }

        $memo[$key] = $count;
        return $count;
    };

    return $dfs(0, true, true, $digits, $limit, $memo);
}

// Test Example 1
echo numberOfPowerfulInt(1, 6000, 4, "124") . "\n"; // Output: 5

// Test Example 2
echo numberOfPowerfulInt(15, 215, 6, "10") . "\n"; // Output: 2

// Test Example 3
echo numberOfPowerfulInt(1000, 2000, 4, "3000") . "\n"; // Output: 0
?>

Explanation:

1. Direct Suffix Check: Convert the suffix string s to an integer and check if it lies within the given range. If it does, count it immediately.
2. Prefix Bounds Calculation: Compute the minimum (lower_p) and maximum (upper_p) valid prefixes such that appending s to these prefixes results in numbers within the range [start, finish].
3. Digit DP for Valid Prefixes: Use a recursive helper function with memoization to count valid prefixes. The DP tracks the current digit position, whether the number being formed is still tight to the upper bound, and whether leading zeros are present. This ensures efficient counting without explicitly generating all possible numbers.

[kovatz]

Thanks for solving the problem of "Count the Number of Powerful Integers"

[mah-shamim]

Thank