⚡Flashcard Drill➔
NeetCode #916LC-2698MediumMath & Geometry
← Back to All Problems

#916 · #2698 · Find the Punishment Number of an Integer(求一个整数的惩罚数)

📌 Problem Statement & Constraints

An integer i is called punishable if the decimal representation of i^2 can be partitioned into contiguous substrings whose integer values sum to exactly i. Given n, return the sum of i^2 over all punishable i in [1, n]. Constraints: 1 <= n <= 1000.

💡 Core Algorithmic Approaches

  1. For each i in [1, n], test whether i^2 admits a partition of its digits summing to i.
  2. Enumerate all partitions with a depth-first search that builds each part digit by digit: at position idx, extend the current part with the next digit and recurse.
  3. Prune as soon as the current part exceeds the target, because all parts are non-negative and extending it only makes it larger.
  4. Whenever a complete partition sums to i, add i^2 to the running total.

💻 Benchmark Python3 Implementation

class Solution:
    def punishmentNumber(self, n: int) -> int:
        def can_partition(s: str, target: int, idx: int, cur: int) -> bool:
            if idx == len(s):
                return cur == target
            val = 0
            for j in range(idx, len(s)):
                val = val * 10 + int(s[j])     # extend the current part
                if val > target:
                    break                       # pruning: parts are non-negative
                if can_partition(s, target, j + 1, cur + val):
                    return True
            return False

        total = 0
        for i in range(1, n + 1):
            if can_partition(str(i * i), i, 0, 0):
                total += i * i
        return total

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n * 2^d) where d is the digit count of n^2 (at most 7 for n = 1000); the pruning keeps the search small in practice.
💾 Space Complexity
O(d): the recursion depth.

⚠️ Interview Pitfalls & Follow-ups

  • Using subsets instead of contiguous substrings: the partition must preserve the original digit order.
  • Omitting the val > target pruning: the search becomes exponential in the number of digits.
  • Comparing the concatenation instead of the sum: the parts are summed, not concatenated back together.
  • Splitting only after single digits: a part may contain several digits, which is why the inner loop extends val before recursing.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Math & Geometry Problems