Overflow in intermediate arithmetic
Wrong move: Temporary multiplications exceed integer bounds.
Usually fails on: Large inputs wrap around unexpectedly.
Fix: Use wider types, modular arithmetic, or rearranged operations.
Move from brute-force thinking to an efficient approach using math strategy.
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 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 <= 1000Problem summary: 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.
Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.
Pattern signal: Math · Backtracking
10
37
number-of-great-partitions)Source-backed implementations are provided below for direct study and interview prep.
// Accepted solution for LeetCode #2698: Find the Punishment Number of an Integer
class Solution {
public int punishmentNumber(int n) {
int ans = 0;
for (int i = 1; i <= n; ++i) {
int x = i * i;
if (check(x + "", 0, i)) {
ans += x;
}
}
return ans;
}
private boolean check(String s, int i, int x) {
int m = s.length();
if (i >= m) {
return x == 0;
}
int y = 0;
for (int j = i; j < m; ++j) {
y = y * 10 + (s.charAt(j) - '0');
if (y > x) {
break;
}
if (check(s, j + 1, x - y)) {
return true;
}
}
return false;
}
}
// Accepted solution for LeetCode #2698: Find the Punishment Number of an Integer
func punishmentNumber(n int) (ans int) {
var check func(string, int, int) bool
check = func(s string, i, x int) bool {
m := len(s)
if i >= m {
return x == 0
}
y := 0
for j := i; j < m; j++ {
y = y*10 + int(s[j]-'0')
if y > x {
break
}
if check(s, j+1, x-y) {
return true
}
}
return false
}
for i := 1; i <= n; i++ {
x := i * i
s := strconv.Itoa(x)
if check(s, 0, i) {
ans += x
}
}
return
}
# Accepted solution for LeetCode #2698: Find the Punishment Number of an Integer
class Solution:
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
// Accepted solution for LeetCode #2698: Find the Punishment Number of an Integer
// Rust example auto-generated from java reference.
// Replace the signature and local types with the exact LeetCode harness for this problem.
impl Solution {
pub fn rust_example() {
// Port the logic from the reference block below.
}
}
// Reference (java):
// // Accepted solution for LeetCode #2698: Find the Punishment Number of an Integer
// class Solution {
// public int punishmentNumber(int n) {
// int ans = 0;
// for (int i = 1; i <= n; ++i) {
// int x = i * i;
// if (check(x + "", 0, i)) {
// ans += x;
// }
// }
// return ans;
// }
//
// private boolean check(String s, int i, int x) {
// int m = s.length();
// if (i >= m) {
// return x == 0;
// }
// int y = 0;
// for (int j = i; j < m; ++j) {
// y = y * 10 + (s.charAt(j) - '0');
// if (y > x) {
// break;
// }
// if (check(s, j + 1, x - y)) {
// return true;
// }
// }
// return false;
// }
// }
// Accepted solution for LeetCode #2698: Find the Punishment Number of an Integer
function punishmentNumber(n: number): number {
const check = (s: string, i: number, x: number): boolean => {
const m = s.length;
if (i >= m) {
return x === 0;
}
let y = 0;
for (let j = i; j < m; ++j) {
y = y * 10 + Number(s[j]);
if (y > x) {
break;
}
if (check(s, j + 1, x - y)) {
return true;
}
}
return false;
};
let ans = 0;
for (let i = 1; i <= n; ++i) {
const x = i * i;
const s = x.toString();
if (check(s, 0, i)) {
ans += x;
}
}
return ans;
}
Use this to step through a reusable interview workflow for this problem.
Generate every possible combination without any filtering. At each of n positions we choose from up to n options, giving nⁿ total candidates. Each candidate takes O(n) to validate. No pruning means we waste time on clearly invalid partial solutions.
Backtracking explores a decision tree, but prunes branches that violate constraints early. Worst case is still factorial or exponential, but pruning dramatically reduces the constant factor in practice. Space is the recursion depth (usually O(n) for n-level decisions).
Review these before coding to avoid predictable interview regressions.
Wrong move: Temporary multiplications exceed integer bounds.
Usually fails on: Large inputs wrap around unexpectedly.
Fix: Use wider types, modular arithmetic, or rearranged operations.
Wrong move: Mutable state leaks between branches.
Usually fails on: Later branches inherit selections from earlier branches.
Fix: Always revert state changes immediately after recursive call.