2698. Find the Punishment Number of an Integer - Detailed Explanation

Free Coding Questions Catalog

Boost your coding skills with our essential coding questions catalog. Take a step towards a better tech career now!

Problem Statement

Given a positive integer n, the punishment number of n is defined as the sum of the squares of all integers i in the range 1 to n such that the decimal representation of i^2 can be partitioned into contiguous substrings whose sum equals i. In other words, a number i is valid if you can split the digits of i^2 into one or more parts that add up to i. The task is to find the punishment number of n, i.e., sum of squares of all such valid i from 1 to n.

Example 1:

Input: n = 10
Output: 182
Explanation: The valid numbers in [1, 10] are 1, 9, and 10.
- 1^2 = 1 can be split as "1" which sums to 1.
- 9^2 = 81 can be split as "8" + "1" which sums to 9.
- 10^2 = 100 can be split as "10" + "0" which sums to 10.
  The punishment number is 1^2 + 9^2 + 10^2 = 1 + 81 + 100 = 182.

Example 2:

Input: n = 37
Output: 1478
Explanation: Valid numbers in [1, 37] are 1, 9, 10, 36.
- 36^2 = 1296 can be partitioned into "1" + "29" + "6" which sums to 36.
  So the punishment number is 1^2 + 9^2 + 10^2 + 36^2 = 1 + 81 + 100 + 1296 = 1478.

Constraints: 1 <= n <= 1000 .

Hints to Solve the Problem

Check each number: Iterate through each integer i from 1 to n. For each i, determine if it is valid by checking if i^2 can be partitioned into substrings that sum up to i.
Backtracking / Recursion: Use a recursive backtracking approach to try different ways of splitting the square's digits. Alternatively, use dynamic programming (with memoization) to avoid re-checking the same subproblem multiple times.
Maintain cumulative sum: If a number i is found to be valid, add i^2 to a running total for the punishment number. Initialize a sum variable and accumulate the squares of all valid numbers.

Approach 1: Brute Force with Backtracking

Idea: The straightforward solution is to try all possible ways to split the square of each number and check if any partition sums to the original number. We convert i^2 to a string and use recursion with backtracking to attempt every possible partition point. If a valid combination is found for a given i, we include i^2 in the punishment sum. This approach essentially enumerates each i and uses a depth-first search (DFS) to test partitions of the digit string.

How it works:

Iterate through 1 to n: For each number i, compute square_str = str(i*i).
Recursive check: Define a recursive helper function (e.g., canPartition(idx, curr_sum)) that tries to split square_str starting from index idx and tracking the current accumulated sum curr_sum from the chosen parts.
- If we have reached the end of the string and curr_sum == i, then we've found a valid partition (the sum of chosen parts equals the target i).
- At each recursive step, take a substring square_str[idx:j] (from the current index to some next position j) as the next part. Convert it to an integer value. Add it to curr_sum and recurse from position j.
- If at any point curr_sum exceeds i, we can prune that path (stop exploring further) because adding more digits will only increase the sum. This early termination for branches that overshoot the target is crucial for efficiency.
- If no partition leads to the exact sum, then i is not a valid number.
Accumulate result: Maintain a running total. For each i that returns true from the helper (meaning a valid partition exists), add i^2 to the punishment number sum.

Using backtracking ensures we explore all possible contiguous splits of the square's digits. For example, consider i = 9:

square_str = "81". The recursion will try splitting as "8" + "1" (sum 9, which matches i, success) and also consider the entire "81" as one part (which sums to 81, not 9, so that path fails). In this case, the split 8|1 yields a valid partition equal to 9, so 9 is counted.

Why it works: We systematically try every way to cut the squared number into pieces. If any one of those ways yields the original number as the sum, we know that number i satisfies the condition. The search is bounded because the number of digits is small (at most 7 digits for i^2 when i <= 1000). The pruning step (if partial_sum > i: break) significantly reduces unnecessary exploration by stopping any partition that already exceeds the target sum.

Approach 2: Optimized with Memoization (DP)

Idea: The backtracking in Approach 1 can result in repeated calculations for the same substrings and remaining sums. We can optimize it using dynamic programming (DP) or memoization. The idea is to remember the results of subproblems: specifically, whether a certain prefix of the square's string (starting at index k with a given accumulated sum or remaining sum) can lead to a valid partition. By storing and reusing these results, we avoid redundant recursive calls.

Memoization Strategy:

Use a memo table or dictionary keyed by the state (index, current_sum) (or alternatively (index, remaining_target)), where:
- index is the current position in the square_str we are trying to partition, and
- current_sum is the sum of the parts we have taken so far (or remaining_target = i - current_sum).
Initially, index = 0 and current_sum = 0 (we've taken nothing yet). We aim to reach a state where index == len(square_str) and current_sum == i.
If we encounter the same (index, current_sum) state again in recursion, we can use the stored result (true/false) instead of recomputing it. This is classic overlapping subproblem optimization.

DP Implementation details: One way is to use a 2D boolean DP table dp[pos][sum] meaning using the substring from position pos to the end, can we achieve a current sum of sum? Another way is top-down recursion with a memo dictionary. In practice, since i (the target sum) is at most 1000 and the length of square_str is at most 7 digits, a table of size [len(square_str) x (i+1)] is feasible. For example, a memoization table could be of size 7 x 1001 in the worst case (when i=1000). We initialize all entries as unknown (or -1) and fill them as we explore partitions.

Process:

For each i from 1 to n, compute square_str. Use a recursive function find_partitions(index, current_sum) that returns true if a valid partition is possible from this state. This function will check the memo table: if this state was computed before, return the stored result.
If current_sum exceeds i at any point, mark this state as false (invalid) and prune (no need to continue from here).
If index reached end of string and current_sum == i, mark this state as valid (true).
Otherwise, try all possible next splits from index to some j and recursively check. If any leads to a valid partition, mark the current state as true. If none do, mark it as false. Store the result in memo before returning.
Add i^2 to the answer if the result from find_partitions(0,0) is true (meaning the whole string can be partitioned to sum to i).

This DP approach ensures each possible (index, current_sum) combination for a given i is evaluated at most once. The search space is pruned both by the sum-exceeding check and by memoization of already checked states. While the theoretical worst-case time remains exponential in the number of digits, memoization drastically reduces repeated work in practice.

Code Implementations

Python Code (Backtracking Approach)

Python3

. . . .

Explanation:

The helper function can_split(square_str, target, start, current_sum) attempts to partition the substring starting at index start. It tries every possible end index for the next piece.
If at any point we exactly reach the end of the string with current_sum == target, it returns True (found a valid partition). If we exhaust all options without matching the target sum, it returns False.
We also include a check if current_sum > target: return False to cut off paths that have already accumulated more than the target (pruning).
In the main loop, for each i we call the helper on str(i*i). If it returns True (meaning i is a valid number), we add i*i to total_sum.

Java Code (Using Memoization DP)

Java

. . . .

Explanation:

The punishmentNumber method loops through each number and prepares a memo table for that number's square string. The memo table memo[index][currentSum] stores whether it's possible (true/false) to reach a valid partition starting from a given index with a given current sum. We use -1 as an initial marker for "unknown" state.
The helper canPartition function checks for base conditions (reached end of string, or sum overflow, or already computed state) and then tries all splits from the current index.
If any split leads to a valid solution, it breaks out and records the success in the memo table. If none work out, it records failure for that state.
This approach uses memoization to ensure we don't recompute the same (index, currentSum) state more than once. This is the DP optimization over the pure backtracking approach.

Complexity Analysis

Time Complexity:

Brute Force Backtracking (Approach 1): In the worst case, for each number i we try to partition a string of length m (where m is the number of digits in i^2). Trying all possible partitions is exponential in m (roughly (2^{m-1}) ways to cut a string of length m). However, the maximum m for i^2 (with i <= 1000) is 7 digits, so this is at most (2^6 = 64) possibilities for each number – a small constant. Therefore, the overall complexity is about (O(n * 2^m)). Given n <= 1000 and small m, this is effectively on the order of a few thousand operations, which is very efficient. In general terms, one could say the time complexity is exponential in the number of digits of n^2, but since that digit-count grows logarithmically with n, the solution runs quickly for the given constraint. The pruning (breaking out when the partial sum exceeds i) further reduces the average-case complexity by cutting off many branches early.
DP Memoization (Approach 2): By caching results, we ensure each distinct subproblem (defined by an index in the string and a current sum) is solved only once. The number of subproblems for a given i is at most m * i (where m is length of i^2 and i is the target sum). In the worst case, m ~ 7 and i ~ 1000, so that's about 7000 states, and for each state we try at most m splits (at most 7). So roughly on the order of 50k operations for the worst-case number, which is very manageable. Looping this up to n=1000 yields on the order of a few million operations at most, still well within acceptable range. In Big-O notation, the worst-case time is (O(n * m * i)), but with the given limits this is essentially (O(n)) with a moderate constant factor.

In summary, both approaches run efficiently for n up to 1000. The backtracking approach works fine due to small search space, and the memoized approach further ensures we don't repeat work. Space complexity for the recursion stack is (O(m)) (at most the number of digits deep). The DP approach uses an extra (O(m * i)) space for the memo table, which in worst case is around 7 * 1000 = 7000 entries, quite small. Hence, memory usage is trivial for these input sizes.

Step-by-Step Walkthrough with Visuals

Let's walk through a non-trivial example to see how the backtracking finds a valid partition. Consider i = 36. We have 36^2 = 1296. We want to determine if "1296" can be split into parts that sum to 36. The backtracking will explore splits as follows (trying shorter splits first and pruning when sums exceed 36):

Start with "1296", target sum = 36.
- Take the first digit "1" (value 1). Remaining target now 35, remaining string "296".
  - From "296", take "2" (value 2). Remaining target 33, remaining string "96".
    - From "96", take "9" (value 9). Remaining target 24, remaining string "6".
      - Take "6" (value 6). Remaining target 18, string is fully used. 18 ≠ 0, so this path fails (sum is 1+2+9+6 = 18, not 36). Backtrack.
    - From "96", try taking "96" as one chunk (value 96). This exceeds the remaining target 33, so prune this branch immediately (no need to continue on this path).
  - Backtrack to "296". Now try a larger chunk at that level: take "29" (value 29) instead of "2". Remaining target 6, remaining string "6".
    - Take "6" (value 6). Remaining target becomes 0, string is fully used. Success! We found a partition: 1 | 29 | 6, which sums to 1+29+6 = 36.
    - Having found a valid split, we know 36 is a valid number.
- (The algorithm might still try other possibilities for completeness: e.g., the first chunk "12" instead of "1", but we can already see "12" + "9" + "6" would sum to 27, not 36. Indeed, it would explore "12" then "9" then "6" and fail, and "129" is pruned because 129 > 36.)

The above exploration can be visualized as a recursion tree of choices:

"1296", target=36  
├─ Take "1" (sum=1), target left=35 → "296"  
│   ├─ Take "2" (sum=1+2=3), target left=33 → "96"  
│   │   ├─ Take "9" (sum=3+9=12), target left=24 → "6"  
│   │   │   └─ Take "6" (sum=12+6=18), target left=18 → [end] (fail)  
│   │   └─ Take "96" (96 > target 33) → prune branch  
│   └─ Take "29" (sum=1+29=30), target left=6 → "6"  
│       └─ Take "6" (sum=30+6=36), target left=0 → [end] **success**  
└─ Take "12" (sum=12), target left=24 → "96"  
    └─ Take "9" (sum=12+9=21), target left=15 → "6"  
        └─ Take "6" (sum=21+6=27), target left=9 → [end] (fail)

In this tree, each node represents a state with a chosen part and the updated sum. The bold success branch corresponds to the valid partition 1+29+6 = 36. This example shows how backtracking tries different splits and uses pruning (not going into "96" when it overshoots the target, etc.) to efficiently find a valid combination. If no branch leads to success, the number would be deemed not valid.

Common Mistakes & Edge Cases

Not handling leading zeros properly: When splitting the square’s string, be cautious with substrings like "0" or "05". In our approach, converting "0" yields 0 which is fine to include in a sum. Leading zeros in a substring (e.g., "05") will be interpreted as 5 by int() conversion. This works out mathematically, but one must ensure the logic doesn’t mistakenly skip or mis-handle such cases. For example, 100 split into "10" and "0" is valid (sums to 10), so the algorithm should allow a segment that is just "0". The backtracking approach naturally handles this by converting substrings to int (so "0" becomes 0). Just be careful not to stop at a leading zero thinking it’s invalid – treat it normally in conversion.
Missing the pruning condition: A common pitfall is to recurse on all possible splits without checking if the running sum has exceeded the target. This will vastly increase the search space and can lead to timeouts on larger inputs. Always include a check to break out of inner loops when the partial sum goes beyond i – since adding more digits will only increase the sum further, there's no chance to come back down to exactly i.
Using global variables in recursion without backtracking properly: If implementing via global or outer-scope variables (like accumulating sum or parts), ensure to backtrack (undo additions) when retreating from a recursive call. In our code above, we avoided this by passing sums as parameters and using local variables for substrings. If you use a list to collect parts, remember to remove the last part after exploring a branch (as seen with curr.pop() in some implementations). Forgetting to backtrack can cause incorrect sums or include parts from a previous branch.
Edge cases:
- n = 1 should trivially return 1 (since 1 is valid by definition).
- If none of the numbers up to n are valid (which could happen for certain ranges), the result would be 0. For example, if n was 2, neither 1 nor 2 (4 -> "4") can be partitioned to sum to themselves except 1, so output would be 1.
- Ensure the function handles the upper bound n = 1000 efficiently – which our approaches do. Even though 1000 itself might not be a valid number (1000^2 = 1000000, and it doesn't seem partitionable to 1000), we still loop through all numbers up to 1000 and check each. The algorithm should not time out given the optimizations discussed.

Kaprekar Numbers: This problem is a generalization of the concept of Kaprekar numbers. A Kaprekar number is usually defined by splitting the square into two parts that sum up to the original number. For example, 45 is a Kaprekar number since (45^2 = 2025) and splitting into "20" and "25" gives 20 + 25 = 45. In our problem, we allow any number of parts (not just two). If we restricted to exactly two parts, we’d get the classic Kaprekar check. Exploring this variation could be interesting – e.g., which numbers up to 1000 are Kaprekar numbers? (9, 45, 55, 99... etc.)
Partitioning problems: The core challenge here – splitting a sequence (digits of a number or characters of a string) into pieces that meet certain criteria – is common in many problems. For practice, one could look at problems like “Word Break” (where you split a string into valid words) or “Restore IP Addresses” (split a string of digits into valid IP octets). Those problems use similar backtracking or DP approaches to try out partitions. The difference is the condition for validity (here it’s summing to a target, there it might be belonging to a dictionary or range check). The pattern of recursion with string segments and pruning invalid paths is very much alike.
Additive number problem: Another related puzzle is determining if a sequence of digits can form a valid additive sequence (where each number is the sum of the previous two). While the rule is different (fibonacci-like addition vs. summing all parts to a fixed target), the approach of splitting a number into contiguous chunks and checking a condition is similar.
Digit DP: For a more algorithmic angle, one could frame the checking of a single number’s square as a DP where you move through the digit string and accumulate a sum. This is essentially what we did with memoization. Learning digit DP techniques (often used in counting numbers with certain properties) can be helpful for solving variants where you count how many numbers satisfy a property, etc. In our case, we explicitly identified the numbers and summed their squares, but one could imagine a variant asking just for the count of such numbers or a different property of the partitions.