Count the Number of Powerful Integers

Count the Number of Powerful Integers

What is this problem about?

The Count the Number of Powerful Integers interview question provides a range $[low, high]$, a limit $limit$, and a string $suffix$. An integer is considered "powerful" if:

1. It is within the range $[low, high]$.
2. Every digit in the number is $\le limit$.
3. The number ends with the given suffix.

You need to count how many powerful integers exist. Since the numbers can be very large, they are often given as strings.

Why is this asked in interviews?

This "Hard" problem is common at Meta and Google. It is a classic digit DP interview pattern question. It tests whether a candidate can handle multiple constraints: a digit-level bound, a suffix requirement, and range bounds. It evaluates the ability to build a recursive counting function with state memoization to avoid exponential complexity.

Algorithmic pattern used

The problem is solved using Digit Dynamic Programming.

1. Range Property: Result = countPowerful(high) - countPowerful(low - 1).
2. Recursive Function: solve(index, is_less, is_started):
   • index: Current digit being placed (from left to right).
   • is_less: Boolean, true if we are already smaller than the prefix of the bound.
   • is_started: Boolean, true if we have placed a non-zero digit.
3. Logic:
   • If index reaches the start of the suffix, check if the remaining suffix matches the requirement and if digits $\le limit$.
   • For other indices, iterate digits from 0 to $\min(limit, bound\_digit)$.
4. Use memoization on (index, is_less, is_started).

Example explanation

high = "200", limit = 2, suffix = "1"

• Digits allowed: 0, 1, 2.
• Must end in "1".
• Possible numbers:
  • 1-digit: "1" (Valid)
  • 2-digit: "01" (1), "11", "21".
  • 3-digit: "101", "111", "121", "201"...
• We check if each fits $\le 200$.

Common mistakes candidates make

• Suffix handling: Not correctly identifying when to start matching the suffix.
• Limit check: Forgetting that even the suffix digits must be $\le limit$.
• String subtraction: Failing to implement low - 1 correctly for strings. (Alternatively, solve for $high$ and $low$ and check $low$ separately).

Interview preparation tip

Digit DP is about "filling slots." Always visualize the bound as a ceiling. If you place a digit smaller than the ceiling, all subsequent slots are "free" (can be any digit within other constraints). If you place a digit equal to the ceiling, you remain "restricted."