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
- For each
iin[1, n], test whetheri^2admits a partition of its digits summing toi. - 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. - Prune as soon as the current part exceeds the target, because all parts are non-negative and extending it only makes it larger.
- Whenever a complete partition sums to
i, addi^2to 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 > targetpruning: 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
valbefore recursing.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.