Punishment Number of an Integer

Medium
1321.

Punishment Number of an Integer

Punishment Number of an Integer is a medium coding problem on math and backtracking, asked in Amazon, Google and Microsoft interviews.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number} n
 * @return {number}
 */
var punishmentNumber = function(n) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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

  1. Hint 1

    Test each i from 1 to n independently; i * i has at most 7 digits.

  2. Hint 2

    Backtrack: choose the first piece, subtract its value from the target, and recurse on the rest of the digits.

  3. 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

  1. Define can(x, target): can the digits of x be split into pieces summing to target?
  2. If target < 0 or x < target, return false; if x == target, return true (keep x as one piece).
  3. Otherwise, for p = 10, 100, … while p <= x: cut off the last digits as the piece x mod p and recurse on can(x / p, target - x mod p).
  4. Sum i² over all i <= n with can(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 the i values.
  • 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 total

Java

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