Find the Punishment Number of an Integer

Because of the light constraints, I realised you can just recurse over all the possible partitions.

To do this:

I iterated through all the integers from 1 to n (as any of these values can be valid).

Let this integer be i.

taking the square of i, notice that between any 2 numbers, we can either choose to partition or not to partition the square of i at this point.

if we keep a running sum of all the possible partitions, eventually we will exhaust all possible sums and partitions of the square of i

then, we can compare the currrent_sum with the target_sum to find out if they match

then, just keep another running sum, ans, of all the square values that make up the punishment number

code

class Solution {
public:
    int checkForSum(int current_sum, int target_sum, int sqbare) {
        int power = 0;
        int ans = 0;
        while (square > 0) {
            current_sum += (square%10)*pow(10, power);
            square /= 10;
            if (current_sum == target_sum && square == 0) {
                return 1;
            } else if (current_sum <= target_sum) {
                ans |= checkForSum(current_sum, target_sum, square);
            }
            ++power;
        }
        return ans;
    }
    int punishmentNumber(int n) {
        int ans = 0;
        for (int i = 1; i <= n; ++i) {
            int square = i*i;
            if (checkForSum(0, i, square) == 1) {
                ans += square;
            }
        }
        return ans;
    }
};

complexity

Time: O(n * 2^(log_10 n))

Space: O(log_10 n)

learnings

changing from int to string can be quite time consuming; consider just manipulating the integer directly.

time taken

it was like ~18 minutes

took me too long to realise you were just meant to brute-force all cases