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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Find the Punishment Number of an Integer

Difficulty: Medium

Problem Description

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.

Key Insights

  • The problem requires checking each integer i from 1 to n.
  • For each i, compute i * i and check if it can be partitioned into substrings that add up to i.
  • This involves generating all possible partitions of the string representation of i * i.
  • The punishment number is the sum of squares of valid integers.

Space and Time Complexity

Time Complexity: O(n * m^2) where n is the input number and m is the number of digits in i * i. Space Complexity: O(m) for storing the partitions.

Solution

The solution involves iterating through all integers from 1 to n, calculating their squares, and checking if those squares can be broken down into parts that sum to the integer itself. We can use a backtracking approach to explore all substring partitions and check their sums against the integer.

Code Solutions

def is_partition_valid(i):
    square = str(i * i)
    n = len(square)
    
    def backtrack(start, current_sum):
        if start == n:
            return current_sum == i
        
        for end in range(start + 1, n + 1):
            num = int(square[start:end])
            if backtrack(end, current_sum + num):
                return True
        return False
    
    return backtrack(0, 0)

def punishment_number(n):
    total_sum = 0
    for i in range(1, n + 1):
        if is_partition_valid(i):
            total_sum += i * i
    return total_sum

# Example usage:
print(punishment_number(10))  # Output: 182
← Back to All Questions