Find the Punishment Number of an Integer - Video Solutions
Find the Punishment Number of an Integer - Leetcode 2698 - Python
Find the Punishment Number of an Integer - Video Solution
Watch 10 video solutions for Find the Punishment Number of an Integer, a medium level problem involving Math, Backtracking. This walkthrough by NeetCodeIO has 12,937 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Problem Statement
Given a positive integer n, return the punishment number of n.
The punishment number of n is defined as the sum of the squares of all integers i such that:
1 <= i <= n- The decimal representation of
i * ican be partitioned into contiguous substrings such that the sum of the integer values of these substrings equalsi.
Example 1:
Input: n = 10 Output: 182 Explanation: There are exactly 3 integers i that satisfy the conditions in the statement: - 1 since 1 * 1 = 1 - 9 since 9 * 9 = 81 and 81 can be partitioned into 8 + 1. - 10 since 10 * 10 = 100 and 100 can be partitioned into 10 + 0. Hence, the punishment number of 10 is 1 + 81 + 100 = 182
Example 2:
Input: n = 37 Output: 1478 Explanation: There are exactly 4 integers i that satisfy the conditions in the statement: - 1 since 1 * 1 = 1. - 9 since 9 * 9 = 81 and 81 can be partitioned into 8 + 1. - 10 since 10 * 10 = 100 and 100 can be partitioned into 10 + 0. - 36 since 36 * 36 = 1296 and 1296 can be partitioned into 1 + 29 + 6. Hence, the punishment number of 37 is 1 + 81 + 100 + 1296 = 1478
Constraints:
1 <= n <= 1000
Approach Overview
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.
Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Backtracking for Partitioning Squares | O(n * 2^d) | O(d) | Single query scenario where you directly test each square's digit partitions |
| Precomputation and Dynamic Validation | O(n * 2^d) preprocessing, O(n) query | O(1) | Multiple queries or platforms where valid punishment numbers can be cached |