'2025/04/11'에 해당되는 글 2건

Leetcode Problem:

• Count Symmetric Integers

Summary

• The problem is to find the number of symmetric integers in the given range [low, high].

Approach

• The solution checks for symmetry by comparing the sum of the first n digits with the sum of the last n digits for each integer in the range
• It also handles numbers with an odd number of digits by not including them in the count.

Complexity

• O(n) where n is the number of integers in the range, as it checks each integer once.

Explanation

• The solution iterates over each integer in the range and checks for symmetry
• For numbers with an even number of digits (4 or more), it calculates the sum of the first n digits and the sum of the last n digits
• If they are equal, it increments the count
• For numbers with 3 digits, it directly compares the two middle digits
• The time complexity is linear as it checks each integer once.

Solution Code:

class Solution {
public:
    int countSymmetricIntegers(int low, int high) {
        int ans = 0;
        for(int i = low; i <= high; i++){
            if(i / 1000){
                int a = i / 1000;
                int b = (i % 1000) / 100;
                int c = (i % 100) / 10;
                int d = (i % 10);
                if((a + b) == (c + d)){
                    ans++;
                }
            } else if( ((i/10) > 0) && ((i/10) < 10)){
                int a = i/10;
                int b = i%10;
                if(a == b) ans++;
            }
        }
        return ans;
    }
};

Leetcode Problem:

• Count the Number of Powerful Integers

Summary

• This problem requires finding the total number of powerful integers in a given range.

Approach

• The solution uses a recursive depth-first search (DFS) approach with memoization to efficiently count the powerful integers
• It aligns the digits of the start and finish numbers, and then recursively explores all possible combinations of digits that meet the conditions
• The memoization helps avoid redundant calculations and improves the performance of the solution.

Complexity

• O(n * limit) where n is the length of the finish number, and limit is the maximum allowed digit value.

Solution Code:

class Solution {
public:
    long long numberOfPowerfulInt(long long start, long long finish, int limit,
                                  string s) {
        string low = to_string(start);
        string high = to_string(finish);
        int n = high.size();
        low = string(n - low.size(), '0') + low;  // align digits
        int pre_len = n - s.size();               // prefix length

        vector memo(n, -1);
        function dfs =
            [&](int i, bool limit_low, bool limit_high) -> long long {
            // recursive boundary
            if (i == low.size()) {
                return 1;
            }

            if (!limit_low && !limit_high && memo[i] != -1) {
                return memo[i];
            }

            int lo = limit_low ? low[i] - '0' : 0;
            int hi = limit_high ? high[i] - '0' : 9;

            long long res = 0;
            if (i < pre_len) {
                for (int digit = lo; digit <= min(hi, limit); digit++) {
                    res += dfs(i + 1, limit_low && digit == lo,
                               limit_high && digit == hi);
                }
            } else {
                int x = s[i - pre_len] - '0';
                if (lo <= x && x <= min(hi, limit)) {
                    res =
                        dfs(i + 1, limit_low && x == lo, limit_high && x == hi);
                }
            }

            if (!limit_low && !limit_high) {
                memo[i] = res;
            }
            return res;
        };
        return dfs(0, true, true);
    }
};