Find the Punishment Number of an Integer

Problem Statement

Given a positive integer n, the task is to compute what is termed as the punishment number of n. The punishment number for any integer n is calculated as follows:

• Identify all integers i ranging from 1 to n both inclusive.
• For each integer i, compute the square, i*i.
• If the result (i.e., i*i) can be split into contiguous sub-numbers whose sum totals back to i, that square value (i*i) contributes to the punishment number.
• Sum up all such squares to get the final punishment number of n.

Examples

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 = 182

Example 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

Approach and Intuition

1. The task can be approached by iterating through all numbers from 1 up to n.
2. For each number i:
   • Compute the square of i (i*i).
   • Check if the digits of i*i can be split into multiple contiguous numbers that sum to i.
   • To perform the check, consider all possible partitions of the number i*i. For each partition, sum the numbers and compare with i.
3. Accumulate the values of i*i for which the above condition holds true to obtain the final punishment number.

Insight from Examples:

• First Example (n = 10):
  • The numbers are 1, 9, and 10 each fulfilling the condition with their squares being 1, 81, and 100 respectively. These can be partitioned as demonstrated in the problem statement. Thus, the punishment number sums up to 182.
• Second Example (n = 37):
  • The numbers are 1, 9, 10, and 36. With squares 1, 81, 100, and 1296 respectively. When partitioned correctly they fulfill the sum back to the original number, adding up to a punishment number of 1478.

These examples illustrate verifying partitions and accumulation of values methodically, which is integral for solving bigger inputs as defined by the constraints (1 <= n <= 1000). The approach will thus consist of iterating across this range, checking possible partitions for each square, and summing those that qualify.

Solutions

class Solution {
public:
    bool isPartitionPossible(int number, int sum) {
        if (sum < 0 || number < sum) {
            return false;
        }
    
        if (number == sum) {
            return true;
        }
    
        return isPartitionPossible(number / 10, sum - number % 10) ||
               isPartitionPossible(number / 100, sum - number % 100) ||
               isPartitionPossible(number / 1000, sum - number % 1000);
    }
    
    int calculateTotalPenalty(int limit) {
        int totalPenalty = 0;
    
        for (int i = 1; i <= limit; i++) {
            int square = i * i;
    
            if (isPartitionPossible(square, i)) {
                totalPenalty += square;
            }
        }
        return totalPenalty;
    }
};