Skip to main content
Talentd

Find the Punishment Number of an Integer - Solution & Explanation

MediumMathBacktracking21 min readAsked at: Amazon, Meta, Google +1
Practice this problem

Problem Statement

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.

 

Example 1:

Input: n = 10
Output: 182
Explanation: There are exactly 3 integers i 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.
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 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 <= 1000

Approach Overview

Problem Overview: You need the punishment number for an integer n. For every i from 1 to n, square the number (i * i) and check whether its digits can be partitioned into contiguous pieces whose sum equals i. If it works, add i^2 to the total. The final sum of all such squares is the punishment number.

Approach 1: Backtracking for Partitioning Squares (O(n * 2^d) time, O(d) space)

Convert i * i into a string and try every possible way to split it into contiguous substrings. Use backtracking to explore partitions: at each position, extend the current segment and recursively check whether the running sum plus that segment can still reach i. If the sum equals i exactly when the string ends, the square qualifies. The search space is bounded by the number of digits d in i^2 (at most 7 for typical constraints), so even though the theoretical branching is 2^d, the recursion stays small. This approach is straightforward and mirrors the problem definition.

Approach 2: Precomputation and Dynamic Validation (O(n * 2^d) preprocessing, O(n) query, O(1) extra space)

Instead of recomputing the partition check every time, precompute which integers satisfy the property. For each i, run the same partition validation on the digits of i^2. If valid, store the square or maintain a running prefix sum of valid values. After preprocessing, computing the punishment number for any n becomes a simple prefix lookup or iteration. This approach combines math operations with recursive partition validation and works well when multiple queries are expected or when the platform constraints cap n to a small range.

Recommended for interviews: The backtracking partition approach is what interviewers expect. It shows you recognize the partition search pattern and can implement recursive pruning. Precomputation is an optimization layered on top of the same logic and demonstrates awareness of repeated computation and practical performance improvements.

Approach 1: Backtracking for Partitioning Squares

This approach involves recursively checking every possible partition of the number formed by the square of each integer i, up to n. The key observation is to find a way to partition the square such that the sum of its partitions equals the integer i itself.

Backtracking is used here to explore all potential partitions, checking if any valid partition matches the criteria. If found, we include the square of i in our sum to calculate the punishment number.

This C solution leverages a helper function called `canPartition` which recursively tries to partition the string representation of a square and checks if the sum matches the original integer i. If it does, it adds the square to a running total which becomes the punishment number. The `canPartition` function explores every possible contiguous substring formation and their sums, employing a backtracking technique.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n * k), where n is the input integer and k is the average number of recursive calls made for each square partition (this can vary depending on the number of digits in i*i).

Space Complexity: O(d), where d is the depth of recursion, equivalent to the number of digits in the square of i (in the worst case scenarios).

Try this approach in the editor →

Approach 2: Precomputation and Dynamic Validation

In this approach, we try to optimize the solution by using precomputation and dynamic checking of the valid numbers whose square conforms to the partition rule. This method involves maintaining a list of valid squares till a certain number and using this as a lookup-table to quickly calculate the punishment number.

Here, the C solution uses dynamic programming to check valid partitioning of squares. A dp table keeps track of achievable sums using parts of the square. If we can construct the integer i by partitioning the square, its square is included in the punishment sum.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n * m * target), where n is the number of inputs, m the maximum length of squared numbers (digit count), and target the sum we're achieving.

Space Complexity: O(len * target), where len is max digits in squared numbers.

Try this approach in the editor →

Approach 3: Enumeration + DFS

We enumerate i, where 1 leq i leq n. For each i, we split the decimal representation string of x = i^2, and then check whether it meets the requirements of the problem. If it does, we add x to the answer.

After the enumeration ends, we return the answer.

The time complexity is O(n^{1 + 2 log_{10}^2}), and the space complexity is O(log n), where n is the given positive integer.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Backtracking for Partitioning Squares

Time Complexity: O(n * k), where n is the input integer and k is the average number of recursive calls made for each square partition (this can vary depending on the number of digits in i*i).

Space Complexity: O(d), where d is the depth of recursion, equivalent to the number of digits in the square of i (in the worst case scenarios).

Precomputation and Dynamic Validation

Time Complexity: O(n * m * target), where n is the number of inputs, m the maximum length of squared numbers (digit count), and target the sum we're achieving.

Space Complexity: O(len * target), where len is max digits in squared numbers.

Enumeration + DFS—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Backtracking for Partitioning SquaresO(n * 2^d)O(d)Single query scenario where you directly test each square's digit partitions
Precomputation and Dynamic ValidationO(n * 2^d) preprocessing, O(n) queryO(1)Multiple queries or platforms where valid punishment numbers can be cached

Video Solution

Find the Punishment Number of an Integer - Leetcode 2698 - Python • NeetCodeIO • 12,937 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Find the Punishment Number of an Integer easy or hard?
The problem is rated Medium because it requires recognizing a backtracking partition pattern. The implementation is short, but identifying that you must recursively split the digits of i² and prune invalid sums is the main challenge.
Find the Punishment Number of an Integer Python/Java solution
In Python or Java, convert i² to a string and recursively try splitting the string into substrings. Convert each substring to an integer, accumulate the sum, and stop exploring when the sum exceeds i. If a partition ends exactly with sum equal to i, include i² in the total.
How to solve Find the Punishment Number of an Integer in O(n)?
You can achieve near O(n) query time by precomputing which values satisfy the partition condition. Run the backtracking validation once for each i up to the maximum constraint and store the cumulative punishment sums. After preprocessing, answering a query for n only requires reading the stored prefix result.
What is the best approach for Find the Punishment Number of an Integer?
The most practical approach uses backtracking to test whether the digits of i² can be partitioned into contiguous numbers that sum to i. For each i from 1 to n, recursively try different substring splits while tracking the current sum. The complexity is roughly O(n * 2^d), where d is the number of digits in i², which stays small in practice.
Is Find the Punishment Number of an Integer asked at Google/Amazon/Meta?
Problems combining digit manipulation and backtracking appear frequently in interviews at companies like Amazon, Google, and Meta. While this exact problem may not always appear, the pattern of partitioning digits and validating sums is a common interview theme.
What data structure is used in Find the Punishment Number of an Integer?
The core solution relies on recursion with backtracking and simple string or digit processing. Some implementations also use arrays to store prefix sums when applying precomputation. No complex data structures are required beyond recursion state tracking.
What is the time complexity of Find the Punishment Number of an Integer?
The time complexity is O(n * 2^d). For each integer i from 1 to n, the algorithm explores possible partitions of the digits of i². Since the number of digits d is small (usually ≤7), the exponential partition exploration remains manageable.

Ready to solve this problem?

Practice Find the Punishment Number of an Integer with our built-in code editor and test cases.

Practice on FleetCode
Previous

Number of Great Partitions