Count the Number of Powerful Integers - Practice Coding Problems

Count the Number of Powerful Integers - 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.

Input & Output

Example 1 — Basic Case

$ Input: start = 1, finish = 15, limit = 2, s = "2"

› Output: 2

💡 Note: The powerful integers are 2 and 12. Both end with "2" and have all digits ≤ 2. Numbers like 22 are > 15, and 32 has digit 3 > 2.

Example 2 — No Valid Numbers

$ Input: start = 1, finish = 15, limit = 1, s = "2"

› Output: 0

💡 Note: No numbers ending with "2" can have all digits ≤ 1, since "2" itself contains digit 2 > 1.

Example 3 — Larger Suffix

$ Input: start = 1000, finish = 2000, limit = 4, s = "124"

› Output: 1

💡 Note: Only 1124 is in range [1000,2000], ends with "124", and has all digits ≤ 4.

Constraints

1 ≤ start ≤ finish ≤ 10¹⁵
1 ≤ limit ≤ 9
1 ≤ s.length ≤ floor(log₁₀(finish)) + 1
s only contains digits, and doesn't have leading zeros

Visualization

Tap to expand

Understanding the Visualization

Input Range

Numbers from start=1 to finish=15, limit=2, suffix="2"

Filter Process

Check each number for suffix and digit constraints

Count Result

Count valid powerful integers: 2

Key Takeaway

🎯 Key Insight: Use digit DP to efficiently count valid numbers without enumerating them all

Asked in

G Google 25 f Meta 18 A Amazon 15

The key insight is to use digit dynamic programming instead of brute force enumeration. We build valid numbers position by position, tracking tight bounds and suffix constraints. Best approach uses memoized digit DP with Time: O(d × 10), Space: O(d) where d is the number of digits.

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force Enumeration	O(n × m)	O(1)	Check every number in range [start, finish] for validity
Digit DP with Memoization	O(d × 2 × 2 × 10)	O(d × 2 × 2)	Use digit dynamic programming to count valid numbers efficiently

Brute Force Enumeration — Algorithm Steps

Iterate from start to finish
Convert each number to string
Check if it ends with s and all digits ≤ limit

Visualization

Tap to expand

Step-by-Step Walkthrough

Range Iteration

Go through numbers 1 to 15

Suffix Check

Check if number ends with '2'

Digit Limit Check

Verify all digits ≤ 2

Code -

solution.c — C

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

int solution(int start, int finish, int limit, char* s) {
    int count = 0;
    int suffixLen = strlen(s);
    
    for (int num = start; num <= finish; num++) {
        char numStr[20];
        sprintf(numStr, "%d", num);
        int numLen = strlen(numStr);
        
        if (numLen >= suffixLen && 
            strcmp(numStr + numLen - suffixLen, s) == 0) {
            int valid = 1;
            for (int i = 0; i < numLen; i++) {
                if (numStr[i] - '0' > limit) {
                    valid = 0;
                    break;
                }
            }
            if (valid) count++;
        }
    }
    return count;
}

int main() {
    int start, finish, limit;
    char s[20];
    scanf("%d", &start);
    scanf("%d", &finish);
    scanf("%d", &limit);
    scanf("%s", s);
    
    printf("%d\n", solution(start, finish, limit, s));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n × m)

n = finish - start numbers, m = average number length for string operations

✓ Linear Growth

Space Complexity

O(1)

Only using constant extra variables

✓ Linear Space

12.5K Views

Medium Frequency

~35 min Avg. Time

340 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force Enumeration — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler