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 <= ni * 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 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. 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 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 <= 1000This approach involves recursively checking every possible partition of the number formed by the square of each integer i, up to n. The key observation is to find a way to partition the square such that the sum of its partitions equals the integer i itself.
Backtracking is used here to explore all potential partitions, checking if any valid partition matches the criteria. If found, we include the square of i in our sum to calculate the punishment number.
This C solution leverages a helper function called `canPartition` which recursively tries to partition the string representation of a square and checks if the sum matches the original integer i. If it does, it adds the square to a running total which becomes the punishment number. The `canPartition` function explores every possible contiguous substring formation and their sums, employing a backtracking technique.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n * k), where n is the input integer and k is the average number of recursive calls made for each square partition (this can vary depending on the number of digits in i*i).
Space Complexity: O(d), where d is the depth of recursion, equivalent to the number of digits in the square of i (in the worst case scenarios).
In this approach, we try to optimize the solution by using precomputation and dynamic checking of the valid numbers whose square conforms to the partition rule. This method involves maintaining a list of valid squares till a certain number and using this as a lookup-table to quickly calculate the punishment number.
Here, the C solution uses dynamic programming to check valid partitioning of squares. A dp table keeps track of achievable sums using parts of the square. If we can construct the integer i by partitioning the square, its square is included in the punishment sum.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n * m * target), where n is the number of inputs, m the maximum length of squared numbers (digit count), and target the sum we're achieving.
Space Complexity: O(len * target), where len is max digits in squared numbers.
| Approach | Complexity |
|---|---|
| Backtracking for Partitioning Squares | Time Complexity: O(n * k), where n is the input integer and k is the average number of recursive calls made for each square partition (this can vary depending on the number of digits in i*i). Space Complexity: O(d), where d is the depth of recursion, equivalent to the number of digits in the square of i (in the worst case scenarios). |
| Precomputation and Dynamic Validation | Time Complexity: O(n * m * target), where n is the number of inputs, m the maximum length of squared numbers (digit count), and target the sum we're achieving. Space Complexity: O(len * target), where len is max digits in squared numbers. |
Find the Punishment Number of an Integer - Leetcode 2698 - Python • NeetCodeIO • 12,079 views views
Watch 9 more video solutions →Practice Find the Punishment Number of an Integer with our built-in code editor and test cases.
Practice on FleetCode