LeetCode 2698: Find the Punishment Number of an Integer
Problem Description
Explanation
To solve this problem, we iterate from 1 to n and for each i, we check if the square of i can be partitioned into contiguous substrings such that their sum equals i. If it satisfies the condition, we add i^2 to the punishment number. We can determine if a number can be partitioned by converting it to a string and checking all possible partitions of the string to sum up the integer values.
Time Complexity: O(n * m), where n is the input integer n and m is the number of digits in the square of n.
Space Complexity: O(m), where m is the number of digits in the square of n.
Solutions
class Solution {
public int findPunishmentNumber(int n) {
int punishmentNumber = 0;
for (int i = 1; i <= n; i++) {
int square = i * i;
String squareStr = String.valueOf(square);
int sum = 0;
int j = 0;
while (j < squareStr.length()) {
String numStr = "";
while (j < squareStr.length() && Character.isDigit(squareStr.charAt(j))) {
numStr += squareStr.charAt(j);
j++;
}
if (!numStr.isEmpty()) {
sum += Integer.parseInt(numStr);
}
j++;
}
if (sum == i) {
punishmentNumber += square;
}
}
return punishmentNumber;
}
}Loading editor...