2698: Find-the-Punishment-Number-of-an-Integer
Medium

code

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;
    }
};

2698: Find-the-Punishment-Number-of-an-Integer
Medium

table of contents

code

complexity

learnings

time taken

2698: Find-the-Punishment-Number-of-an-Integer Medium

table of contents

code

complexity

learnings

time taken

2698: Find-the-Punishment-Number-of-an-Integer
Medium