Today I have done leetcode's February LeetCoding Challenge with cpp.

February LeetCoding Challenge 15

Description

Find the Punishment Number of an Integer

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 in the range [1, 10] that satisfy the conditions in the statement:
- 1 since 1 * 1 = 1
- 9 since 9 * 9 = 81 and 81 can be partitioned into 8 and 1 with a sum equal to 8 + 1 == 9.
- 10 since 10 * 10 = 100 and 100 can be partitioned into 10 and 0 with a sum equal to 10 + 0 == 10.
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 in the range [1, 37] 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

Solution

bool isPunishment(int n, string s, int pos, int sum, int current) {
  if(pos == s.length()) return n == sum + current;
  return isPunishment(n, s, pos + 1, sum + current, s[pos] - '0') || isPunishment(n, s, pos + 1, sum, current * 10 + s[pos] - '0');
}
vector<int> result = []{
  vector<int> result(1001);
  for(int i = 1; i < 1001; ++i) {
    string si = to_string(i * i);
    if(isPunishment(i, si, 0, 0, 0)) {
      result[i] = i * i + result[i - 1];
    } else {
      result[i] = result[i - 1];
    }
  }
  return result;
}();
class Solution {
public:
  int punishmentNumber(int n) {
    return result[n];
  }
};

// Accepted
// 216/216 cases passed (0 ms)
// Your runtime beats 100 % of cpp submissions
// Your memory usage beats 70.03 % of cpp submissions (9.7 MB)