Find The Punishment Number Of An Integer · Interview Problem

Leetcode

Medium

Math

Backtracking

Recursion

Find The Punishment Number Of An Integer

Compute the punishment number of an integer by checking which squares can be partitioned into decimal chunks that sum back to the original number.

Acceptance 0%

Start Practice

Also Available On

Other platform versions and source mappings for the same problem.

Punishment Number

gfg

Problem Statement

Given a positive integer $n$ , consider every integer $i$ from $1 $to$ n$.

For each $i$ , square it to get $i^2$ . If the decimal representation of $i^2$ can be split into one or more contiguous substrings such that the integer values of those substrings add up exactly to $i$ , then $i$ contributes $i^2$ to the answer.

Return the sum of the squares of all such valid integers $i$ in the range $[1, n]$ .

The task is to determine this total punishment number.

Input Format

A single integer $n$ .

Output Format

Return the punishment number of $n$ , defined as the sum of $i^2$ for all $1 \le i \le n$ whose square can be partitioned into decimal substrings summing to $i$ .

Constraints

$1 \le n$
The exact upper bound is not provided in the source context; solutions should work efficiently for the typical LeetCode range.
Only decimal substring partitions are allowed; substrings must be contiguous and use the digits of $i^2$ in order.

Examples

Sample cases returned by the problem API.

Example 1

Input

n = 10

Output

Explanation

Valid values are 1, 9, and 10.

$1^{2}$ = 1 -> [1] sums to 1
$9^{2}$ = 81 -> [8, 1] sums to 9
$10^{2}$ = 100 -> [10, 0] sums to 10

So the answer is 1 + 81 + 100 = 182.

Example 2

Input

n = 1

Output

Explanation

Only 1 is checked, and $1^{2}$ = 1 can be split as [1], which sums to 1.

Premium problem context

Unlock deeper context for this problem

Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.

Guided hints

Editorial and discussion links

Concept map and variants

Track your progress