15_Find_the_Punishment_Number_of_an_Integer.cpp

// 2698. Find the Punishment Number of an Integer

// 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 * i can be partitioned into contiguous substrings such that the sum of the integer values of these substrings equals i.

// 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

class Solution
{
public:
    int punishmentNumber(int n)
    {
        vector<int> arr = {1, 9, 10, 36, 45, 55, 82, 91, 99, 100, 235, 297, 369, 370, 379, 414,
                           657, 675, 703, 756, 792, 909, 918, 945, 964, 990, 991, 999, 1000};
        int sum = 0;
        for (int i = 0; i < arr.size(); i++)
        {
            if (arr[i] <= n)
                sum += arr[i] * arr[i];
            else
                break;
        }
        return sum;
    }
};

/*
This code finds the punishment number for a given integer n. It uses a pre-computed array 'arr' containing all numbers from 1 to 1000 that satisfy the punishment number conditions. For each number in the array that is less than or equal to n, it adds its square to the sum. The final sum is the punishment number. This approach is more efficient than checking every number from 1 to n since it uses pre-computed valid numbers.
*/