We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Find the Punishment Number of an Integer

Number: 2802

Difficulty: Medium

Paid? No

Companies: Google, Amazon, Bloomberg

Problem Description

Given a positive integer n, compute the punishment number of n. The punishment number is defined as the sum of the squares of all integers i (1 <= i <= n) such that the decimal representation of i * i can be partitioned into contiguous substrings with the property that the sum of the integer values of these substrings equals i.

Key Insights

  • For each integer i, square it to get i*i and convert that result to a string.
  • Use backtracking (DFS) to generate all possible partitions of the string representing i*i.
  • Accumulate the sum of the numbers represented in each partition. If any partition sums exactly to i, then i qualifies.
  • Add i*i to the overall total if i qualifies.
  • The main challenge is to efficiently explore all possible substring partitions and to prune paths where the accumulated sum already exceeds i.

Space and Time Complexity

Time Complexity: O(n * 2^d)

  • n is the given number, and d is the number of digits in the squared number i*i (each digit position offers a partition or not, leading to 2^(d-1) possibilities). Space Complexity: O(d)
  • d is used for the recursion depth (storing the current path of partitions).

Solution

The solution iterates over each integer i from 1 to n. For each integer, compute the square ii and convert it to a string. A recursive backtracking function is used to explore all ways of partitioning this string into substrings. The function accumulates the sum of the parsed integers and checks if it equals i when all digits have been used. If the condition is met, ii is added to the punishment number. The backtracking includes a pruning step: if the current accumulated sum exceeds i, further exploration along that path is halted.

Code Solutions

def punishmentNumber(n: int) -> int:
    def can_partition(s: str, target: int, idx: int = 0, current_sum: int = 0) -> bool:
        # Base case: if we've used all digits, check if the current sum equals the target.
        if idx == len(s):
            return current_sum == target
        num = 0
        # Try all possible partitions starting from idx.
        for j in range(idx, len(s)):
            num = num * 10 + int(s[j])
            # Prune if the accumulated sum exceeds the target.
            if current_sum + num > target:
                break
            if can_partition(s, target, j + 1, current_sum + num):
                return True
        return False

    total = 0
    for i in range(1, n + 1):
        square_str = str(i * i)
        if can_partition(square_str, i):
            total += i * i
    return total

# Example usage:
print(punishmentNumber(10))  # Expected output: 182
print(punishmentNumber(37))  # Expected output: 1478
← Back to All Questions