Find the Punishment Number of an Integer
MedPrompt
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 in the range [1, 10] that satisfy the conditions in the statement:
- 1 since 1 * 1 = 1
- 9 since 9 * 9 = 81 and 81 can be partitioned into 8 and 1 with a sum equal to 8 + 1 == 9.
- 10 since 10 * 10 = 100 and 100 can be partitioned into 10 and 0 with a sum equal to 10 + 0 == 10.
Hence, the punishment number of 10 is 1 + 81 + 100 = 182Example 2:
Input: n = 37
Output: 1478
Explanation: There are exactly 4 integers i in the range [1, 37] 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
Approaches
2 approaches with complexity analysis and trade-offs.
This approach iterates through each integer i from 1 to n. For each i, it first calculates its square, i*i, and converts it into a string. Then, a recursive backtracking function is used to determine if this string can be partitioned into substrings whose integer values sum up to i. If a valid partition exists, i*i is added to a running total. This method directly translates the problem statement into code.
Algorithm
- Initialize
punishmentSum = 0. - For
ifrom 1 ton:- Let
s = String.valueOf(i * i). - If a helper function
canPartition(s, i)returnstrue, addi * itopunishmentSum.
- Let
- Return
punishmentSum. - The
canPartitionfunction uses a recursive depth-first search (dfs) to check the condition. dfs(s, target, index, currentSum)function:- Base Case: If
indexreaches the end of the strings, it means we have processed the entire string. ReturntrueifcurrentSumequalstarget, otherwisefalse. - Recursive Step: Iterate through all possible next substrings starting from
index. For each substring:- Parse it to an integer
num. - If
currentSum + numexceedstarget, we can prune this path and all subsequent paths from thisindexbecause numbers will only get larger. - Make a recursive call
dfs(s, target, j + 1, currentSum + num)for the rest of the string. - If any recursive call returns
true, it means a valid partition is found, so propagatetrueup the call stack.
- Parse it to an integer
- If the loop completes without finding a valid partition, return
false.
- Base Case: If
Walkthrough
The main function punishmentNumber(n) initializes a sum to zero and then loops from i = 1 to n. Inside the loop, it calculates square = i * i and converts it to a String s. It then calls a helper function, canPartition(s, i), to check if s can be partitioned to sum to i. If canPartition returns true, square is added to the sum.
The canPartition function itself is a wrapper that initiates a recursive search. It calls a backtracking function dfs(s, target, index, currentSum) which explores all possible partitions of the string s starting from a given index to see if they can sum up to the target.
class Solution { public int punishmentNumber(int n) { int totalPunishment = 0; for (int i = 1; i <= n; i++) { String s = String.valueOf(i * i); if (canPartition(s, i)) { totalPunishment += i * i; } } return totalPunishment; } private boolean canPartition(String s, int target) { return dfs(s, target, 0, 0); } private boolean dfs(String s, int target, int index, int currentSum) { if (index == s.length()) { return currentSum == target; } for (int j = index; j < s.length(); j++) { String sub = s.substring(index, j + 1); int num = Integer.parseInt(sub); if (currentSum + num > target) { // Optimization: if current sum already exceeds target, // no need to check longer numbers from this index. break; } if (dfs(s, target, j + 1, currentSum + num)) { return true; } } return false; }}Complexity
Time
O(N * K), where `N` is the input `n`, and `K` is the cost of the `canPartition` check. The `dfs` function's complexity is exponential in the length of the string `s`, let's say `L`. `L = O(log(i^2)) = O(log i)`. The number of partitions of a string of length `L` is `2^(L-1)`. So, `K` is roughly `O(2^L)`. Given `N <= 1000`, `L` is at most 7, so this is feasible.
Space
O(log N). The space complexity is determined by the maximum depth of the recursion stack for the `dfs` function. The depth is at most the length of the string representation of `i*i`, which is proportional to `log(i^2)` or `log N`.
Trade-offs
Pros
Conceptually simple and a direct implementation of the problem requirements.
Does not require complex data structures.
Cons
Can be slow due to the exponential nature of the recursive partition check, especially for larger values of
n(though feasible for the given constraints).For multiple test cases (as in a competitive programming platform), it recomputes the same results for smaller
nvalues repeatedly.
Solutions
Solution
class Solution {public int punishmentNumber(int n) { int ans = 0; for (int i = 1; i <= n; ++i) { int x = i * i; if (check(x + "", 0, i)) { ans += x; } } return ans; }private boolean check(String s, int i, int x) { int m = s.length(); if (i >= m) { return x == 0; } int y = 0; for (int j = i; j < m; ++j) { y = y * 10 + (s.charAt(j) - '0'); if (y > x) { break; } if (check(s, j + 1, x - y)) { return true; } } return false; }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.