Find the Punishment Number of an Integer - Video Solutions

Problem Overview: You need the punishment number for an integer n. For every i from 1 to n, square the number (i * i) and check whether its digits can be partitioned into contiguous pieces whose sum equals i. If it works, add i^2 to the total. The final sum of all such squares is the punishment number.

Approach 1: Backtracking for Partitioning Squares (O(n * 2^d) time, O(d) space)

Convert i * i into a string and try every possible way to split it into contiguous substrings. Use backtracking to explore partitions: at each position, extend the current segment and recursively check whether the running sum plus that segment can still reach i. If the sum equals i exactly when the string ends, the square qualifies. The search space is bounded by the number of digits d in i^2 (at most 7 for typical constraints), so even though the theoretical branching is 2^d, the recursion stays small. This approach is straightforward and mirrors the problem definition.

Approach 2: Precomputation and Dynamic Validation (O(n * 2^d) preprocessing, O(n) query, O(1) extra space)

Instead of recomputing the partition check every time, precompute which integers satisfy the property. For each i, run the same partition validation on the digits of i^2. If valid, store the square or maintain a running prefix sum of valid values. After preprocessing, computing the punishment number for any n becomes a simple prefix lookup or iteration. This approach combines math operations with recursive partition validation and works well when multiple queries are expected or when the platform constraints cap n to a small range.

Recommended for interviews: The backtracking partition approach is what interviewers expect. It shows you recognize the partition search pattern and can implement recursive pruning. Precomputation is an optimization layered on top of the same logic and demonstrates awareness of repeated computation and practical performance improvements.