Find the Punishment Number of an Integer

Find the Punishment Number of an Integer

1. What is this problem about?

The Find the Punishment Number of an Integer interview question is a mathematical search task with a recursive sub-problem. You are given an integer $n$. For each number $i$ from 1 to $n$, you calculate its square ($i^2$). The "punishment number" of $n$ is the sum of all $i^2$ such that the decimal string representation of $i^2$ can be partitioned into contiguous substrings that sum up to $i$.

2. Why is this asked in interviews?

Companies like Google and Amazon ask the Find the Punishment Number coding problem to test a candidate's mastery of Backtracking and string-to-number manipulation. It requires a combination of iterative searching (for the outer sum) and a recursive "can-partition" check for each square. It evaluations your ability to handle nested logical structures.

3. Algorithmic pattern used

This problem follows the Backtracking interview pattern for partitioning.

• Outer Loop: Iterate $i$ from 1 to $n$.
• Recursive Check: For each $i$, check if $i^2$ is "punishable":
  • Convert $i^2$ to a string.
  • Use recursion to explore all ways to split the string into parts.
  • In each step, pick a substring of length $L$, convert it to a number, and subtract it from the target value $i$.
  • If you reach the end of the string and the target value becomes exactly 0, the number is valid.

4. Example explanation

$i = 10$. $i^2 = 100$.

• Can "100" sum to 10?
  • Split: "10" + "0". Sum: $10 + 0 = 10$. YES!
• 10 is punishable. $10^2 = 100$ is added to the total punishment number. $i = 9$. $i^2 = 81$.
• Split "8" + "1" = 9. YES!
• 9 is added.

5. Common mistakes candidates make

• Ignoring leading zeros: Treating "0" as something that doesn't contribute to the sum. In this problem, "0" is a valid part of the partition.
• Inefficient Partitioning: Using string slicing inside recursion instead of index-based pointers, which can slow down the execution.
• Redundant Calculation: Failing to pre-calculate or cache the "punishable" property for numbers if $n$ is used across multiple test cases.

6. Interview preparation tip

Practice partitioning problems! If you can solve "Word Break" or "Palindrome Partitioning," the core logic of this problem will feel very familiar. Mastering Recursion on strings is a vital skill for technical rounds.