Punishment Number of an Integer — Problem & Solution
Punishment Number of an Integer solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Punishment Number of an Integer is a medium coding problem on math and backtracking, asked in Amazon, Google and Microsoft interviews.
- Difficulty: Medium
- Topics: Math, Backtracking
- Asked at: Amazon, Google, Microsoft
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Call an integer i special if the decimal digits of i * i can be cut into contiguous pieces whose integer values add up to i (a piece may start with zeros, so "01" counts as 1).
The punishment number of n is the sum of i * i over all special i with 1 <= i <= n. Return it.
Example 1
Input: n = 9
Output: 82
Explanation: 1 (1 = 1) and 9 (81 = 8 + 1) are special: 1 + 81 = 82.
Example 2
Input: n = 36
Output: 1478
Explanation: Add 10 (100 = 10 + 0) and 36 (1296 = 1 + 29 + 6): 1 + 81 + 100 + 1296.
Example 3
Input: n = 1000
Output: 10804657
Constraints
1 <= n <= 1000
Hints for Punishment Number of an Integer
Hint 1
Test each
ifrom 1 tonindependently;i * ihas at most 7 digits.Hint 2
Backtrack: choose the first piece, subtract its value from the target, and recurse on the rest of the digits.
Hint 3
Prune when the remaining target goes negative, or when the remaining digits read as a whole number are already smaller than the target (splitting never increases a value).
How to solve Punishment Number of an Integer
For each i, search the ways to cut the digits of i² with a small backtracking routine; there are at most 2⁶ cuttings of a 7-digit square.
Approach
- Define
can(x, target): can the digits ofxbe split into pieces summing totarget? - If
target < 0orx < target, returnfalse; ifx == target, returntrue(keepxas one piece). - Otherwise, for
p = 10, 100, …whilep <= x: cut off the last digits as the piecex mod pand recurse oncan(x / p, target - x mod p). - Sum
i²over alli <= nwithcan(i², i).
Why it works
Every cutting of a digit string is a last piece plus a cutting of the prefix, and the last piece is x mod 10^k for some k (zeros allowed at its front) while the prefix is x / 10^k, so the recursion visits every cutting. Splitting never increases a value (a·10^k + b >= a + b), so x < target can never succeed and prunes safely.
Complexity
- Time —
O(n · 2^d) with d ≤ 7 digits — at most ~64 cuttings per i - Space —
O(d) recursion depth
Pitfalls
- Pieces may have leading zeros: 100 = 10 + 0 and 1000000 = 1000 + 0 + 0 + 0 … are fine.
- Sum the squares
i * i, not theivalues. - The total for n = 1000 is about 10^7 — it fits in 32 bits.
Reference solution
Python
def punishmentNumber(n: int) -> int:
def can(x, target):
if target < 0 or x < target:
return False
if x == target:
return True
p = 10
while p <= x:
if can(x // p, target - x % p):
return True
p *= 10
return False
total = 0
for i in range(1, n + 1):
if can(i * i, i):
total += i * i
return totalJava
public static int punishmentNumber(int n) {
int total = 0;
for (int i = 1; i <= n; i++) if (punishCan(i * i, i)) total += i * i;
return total;
}
private static boolean punishCan(int x, int target) {
if (target < 0 || x < target) return false;
if (x == target) return true;
for (int p = 10; p <= x; p *= 10) {
if (punishCan(x / p, target - x % p)) return true;
}
return false;
}C++
bool punishCan(int x, int target) {
if (target < 0 || x < target) return false;
if (x == target) return true;
for (int p = 10; p <= x; p *= 10) {
if (punishCan(x / p, target - x % p)) return true;
}
return false;
}
int punishmentNumber(int n) {
int total = 0;
for (int i = 1; i <= n; i++) if (punishCan(i * i, i)) total += i * i;
return total;
}JavaScript
var punishmentNumber = function(n) {
var can = function(x, target) {
if (target < 0 || x < target) return false;
if (x === target) return true;
for (var p = 10; p <= x; p *= 10) {
if (can(Math.floor(x / p), target - x % p)) return true;
}
return false;
};
var total = 0;
for (var i = 1; i <= n; i++) if (can(i * i, i)) total += i * i;
return total;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 337 math problems · the whole catalogue
Learn the technique: Backtracking