Find the Punishment Number of an Integer

Med

#2438Time: O(N * K), where `N` is the input `n`, and `K` is the cost of the `canPartition` check. The `dfs` function's complexity is exponential in the length of the string `s`, let's say `L`. `L = O(log(i^2)) = O(log i)`. The number of partitions of a string of length `L` is `2^(L-1)`. So, `K` is roughly `O(2^L)`. Given `N <= 1000`, `L` is at most 7, so this is feasible.Space: O(log N). The space complexity is determined by the maximum depth of the recursion stack for the `dfs` function. The depth is at most the length of the string representation of `i*i`, which is proportional to `log(i^2)` or `log N`.

Patterns

Math Backtracking

Prompt

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

Approaches

2 approaches with complexity analysis and trade-offs.

This approach iterates through each integer i from 1 to n. For each i, it first calculates its square, i*i, and converts it into a string. Then, a recursive backtracking function is used to determine if this string can be partitioned into substrings whose integer values sum up to i. If a valid partition exists, i*i is added to a running total. This method directly translates the problem statement into code.

Algorithm

Initialize punishmentSum = 0.
For i from 1 to n:
- Let s = String.valueOf(i * i).
- If a helper function canPartition(s, i) returns true, add i * i to punishmentSum.
Return punishmentSum.
The canPartition function uses a recursive depth-first search (dfs) to check the condition.
dfs(s, target, index, currentSum) function:
- Base Case: If index reaches the end of the string s, it means we have processed the entire string. Return true if currentSum equals target, otherwise false.
- Recursive Step: Iterate through all possible next substrings starting from index. For each substring:
  - Parse it to an integer num.
  - If currentSum + num exceeds target, we can prune this path and all subsequent paths from this index because numbers will only get larger.
  - Make a recursive call dfs(s, target, j + 1, currentSum + num) for the rest of the string.
  - If any recursive call returns true, it means a valid partition is found, so propagate true up the call stack.
- If the loop completes without finding a valid partition, return false.

Walkthrough

The main function punishmentNumber(n) initializes a sum to zero and then loops from i = 1 to n. Inside the loop, it calculates square = i * i and converts it to a String s. It then calls a helper function, canPartition(s, i), to check if s can be partitioned to sum to i. If canPartition returns true, square is added to the sum.

The canPartition function itself is a wrapper that initiates a recursive search. It calls a backtracking function dfs(s, target, index, currentSum) which explores all possible partitions of the string s starting from a given index to see if they can sum up to the target.

1class Solution {2    public int punishmentNumber(int n) {3        int totalPunishment = 0;4        for (int i = 1; i <= n; i++) {5            String s = String.valueOf(i * i);6            if (canPartition(s, i)) {7                totalPunishment += i * i;8            }9        }10        return totalPunishment;11    }12 13    private boolean canPartition(String s, int target) {14        return dfs(s, target, 0, 0);15    }16 17    private boolean dfs(String s, int target, int index, int currentSum) {18        if (index == s.length()) {19            return currentSum == target;20        }21 22        for (int j = index; j < s.length(); j++) {23            String sub = s.substring(index, j + 1);24            int num = Integer.parseInt(sub);25 26            if (currentSum + num > target) {27                // Optimization: if current sum already exceeds target,28                // no need to check longer numbers from this index.29                break;30            }31 32            if (dfs(s, target, j + 1, currentSum + num)) {33                return true;34            }35        }36 37        return false;38    }39}

Complexity

Time

O(N * K), where `N` is the input `n`, and `K` is the cost of the `canPartition` check. The `dfs` function's complexity is exponential in the length of the string `s`, let's say `L`. `L = O(log(i^2)) = O(log i)`. The number of partitions of a string of length `L` is `2^(L-1)`. So, `K` is roughly `O(2^L)`. Given `N <= 1000`, `L` is at most 7, so this is feasible.

Space

O(log N). The space complexity is determined by the maximum depth of the recursion stack for the `dfs` function. The depth is at most the length of the string representation of `i*i`, which is proportional to `log(i^2)` or `log N`.

Trade-offs

Pros

Conceptually simple and a direct implementation of the problem requirements.
Does not require complex data structures.

Cons

Can be slow due to the exponential nature of the recursive partition check, especially for larger values of n (though feasible for the given constraints).
For multiple test cases (as in a competitive programming platform), it recomputes the same results for smaller n values repeatedly.

This approach leverages the constraint that n is at most 1000. Instead of calculating the result on-the-fly for each call, we can pre-compute the punishment numbers for all integers from 1 to 1000 and store them in a cache (e.g., an array). The main function then simply looks up the result from this cache. The expensive computation is performed only once, making subsequent calls for any n <= 1000 instantaneous.

Algorithm

Declare a static integer array cache of size 1001 (based on the constraint n <= 1000).
Use a static initializer block to perform a one-time pre-computation.
Inside the static block:
- Loop i from 1 to 1000.
- Let s = String.valueOf(i * i).
- Check if i is a punishable number by calling the same dfs(s, i, 0, 0) function from the previous approach.
- Calculate the cumulative punishment number: cache[i] = cache[i-1]. If i is punishable, add i*i to cache[i].
The main punishmentNumber(n) function simply returns the pre-computed value from cache[n].

Walkthrough

We use a static array, punishmentCache, of size 1001 to store the cumulative punishment numbers, where punishmentCache[i] will hold the punishment number for i. A static block is used to populate this cache when the class is loaded. This block iterates from i = 1 to 1000, and for each i, it applies the same recursive check as the brute-force method. The cumulative sum is maintained in the cache: punishmentCache[i] = punishmentCache[i-1] + (is_punishable ? i*i : 0). The main punishmentNumber(n) function, after the one-time initialization, just returns punishmentCache[n]. This approach is highly efficient for platforms that run multiple test cases, as the pre-computation cost is amortized.

1class Solution {2    private static final int MAX_N = 1000;3    private static final int[] punishmentCache = new int[MAX_N + 1];4 5    static {6        for (int i = 1; i <= MAX_N; i++) {7            String s = String.valueOf(i * i);8            punishmentCache[i] = punishmentCache[i - 1];9            if (canPartition(s, i)) {10                punishmentCache[i] += i * i;11            }12        }13    }14 15    private static boolean canPartition(String s, int target) {16        return dfs(s, target, 0, 0);17    }18 19    private static boolean dfs(String s, int target, int index, int currentSum) {20        if (index == s.length()) {21            return currentSum == target;22        }23 24        for (int j = index; j < s.length(); j++) {25            String sub = s.substring(index, j + 1);26            int num = Integer.parseInt(sub);27            28            if (currentSum + num > target) {29                break;30            }31 32            if (dfs(s, target, j + 1, currentSum + num)) {33                return true;34            }35        }36        return false;37    }38 39    public int punishmentNumber(int n) {40        return punishmentCache[n];41    }42}

Complexity

Time

O(1) for each call to `punishmentNumber(n)`. The one-time pre-computation cost is a fixed constant, calculated as `sum_{i=1 to 1000} O(2^(log i))`. This upfront cost is paid only once when the class is loaded.

Space

O(1) with respect to the input `n`, as the space used is constant. It's `O(MAX_N)` for the cache array (`1001 * 4` bytes) and `O(log(MAX_N))` for the recursion stack during the one-time pre-computation.

Trade-offs

Pros

Extremely fast query time (O(1)) for any given n after the initial setup.
Amortizes the computation cost over multiple test cases, making it very efficient in a typical online judge environment.

Cons

Requires extra space for the cache, which is O(MAX_N).
Incurs an upfront computation cost, which might be slightly inefficient if the function is guaranteed to be called only once with a very small n.

Solutions

Solution

1class Solution {2public3  int punishmentNumber(int n) {4    int ans = 0;5    for (int i = 1; i <= n; ++i) {6      int x = i * i;7      if (check(x + "", 0, i)) {8        ans += x;9      }10    }11    return ans;12  }13private14  boolean check(String s, int i, int x) {15    int m = s.length();16    if (i >= m) {17      return x == 0;18    }19    int y = 0;20    for (int j = i; j < m; ++j) {21      y = y * 10 + (s.charAt(j) - '0');22      if (y > x) {23        break;24      }25      if (check(s, j + 1, x - y)) {26        return true;27      }28    }29    return false;30  }31}

1class Solution {2public:3  int punishmentNumber(int n) {4    int ans = 0;5    for (int i = 1; i <= n; ++i) {6      int x = i * i;7      string s = to_string(x);8      if (check(s, 0, i)) {9        ans += x;10      }11    }12    return ans;13  }14  bool check(const string &s, int i, int x) {15    int m = s.size();16    if (i >= m) {17      return x == 0;18    }19    int y = 0;20    for (int j = i; j < m; ++j) {21      y = y * 10 + s[j] - '0';22      if (y > x) {23        break;24      }25      if (check(s, j + 1, x - y)) {26        return true;27      }28    }29    return false;30  }31};

1class Solution:2    def punishmentNumber(self, n: int) -> int: def check(s: str, i: int, x: int) -> bool: m = len(s) if i >= m: return x == 0 y = 0 for j in range(i, m): y = y * 10 + int(s[j]) if y > x: break if check(s, j + 1, x - y): return True return False ans = 0 for i in range(1, n + 1): x = i * i if check(str(x), 0, i): ans += x return ans

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem