'2025/02/15'에 해당되는 글 1건

Leetcode Problem:

• Find the Punishment Number of an Integer

Summary

• This problem requires finding the punishment number of a given positive integer n
• The punishment number is the sum of squares of all integers i such that 1 <= i <= n and the decimal representation of i*i can be partitioned into contiguous substrings with integer values summing up to i.

Approach

• The solution uses a recursive approach with backtracking to find all possible partitions of i*i into contiguous substrings with integer values summing up to i
• It starts from the smallest possible value of i and checks all possible partitions of i*i
• If a valid partition is found, it adds the square of i to the result and moves on to the next value of i.

Complexity

• O(n * 6^6) where n is the input number, due to the recursive backtracking and the loop that generates all possible partitions of i*i.

Solution Code:

class Solution {
public:
    bool check_punishment(int num,vector& nums, int depth, int goal_num){
        if(num == 0){
            if(nums[0] == goal_num) return false;
            int sum = 0;
            for(int i = 0 ; i < nums.size(); i++){
                sum += nums[i];
            }
            if(sum == goal_num){
                return true;
            } else{
                return false;
            }
        }
        int pow = 10;
        for(int i = 1; i <= 6; i++){
            nums.push_back(num % pow);
            if(check_punishment(num/pow, nums, depth+1, goal_num)){
                nums.pop_back();
                return true;
            }
            pow *= 10;
            nums.pop_back();
        }
        return false;
    }
    int punishmentNumber(int n) {
        vector nums;
        int ans = 0;
        for(int i = 1; i <= n; i++){
            int pow = 10;
            for(int j = 1; j <= 6; j++){
                int nn = i * i;
                nums.push_back(nn % pow);
                if(check_punishment(nn/pow, nums, 1, i)){
                    nums.pop_back();
                    ans += nn;
                    break;
                }
                pow *= 10;
                nums.pop_back();
            }
        }
        
        return ans + 1;
    }
};