'2025/04'에 해당되는 글 29건

Leetcode Problem:

• Find Numbers with Even Number of Digits

Summary

• Count numbers with even number of digits in an array

Approach

• The approach used is to iterate through each number in the array and calculate the number of digits in each number using a helper function
• If the number of digits is even, it increments the counter
• Finally, it returns the count of numbers with even number of digits.

Complexity

• O(n * log(max_num)) where n is the size of the array and max_num is the maximum number in the array

Explanation

• The solution iterates through each number in the array
• For each number, it calculates the number of digits using a helper function
• If the number of digits is even, it increments the counter
• The time complexity of the helper function is O(log(max_num)) and it is called for each number in the array
• Therefore, the overall time complexity is O(n * log(max_num)) where n is the size of the array and max_num is the maximum number in the array.

Solution Code:

class Solution {
public:
    int getDigitNum(int num){
        int cnt = 0;
        while(num){
            num/=10;
            cnt++;
        }
        return cnt;
    }
    int findNumbers(vector& nums) {
        int ans = 0;
        for(int num : nums){
            if(getDigitNum(num) % 2){
                continue;
            }
            ans++;
        }
        return ans;
    }
};

Leetcode Problem:

• Count Subarrays Where Max Element Appears at Least K Times

Summary

• The problem requires finding the number of subarrays in a given array where the maximum element appears at least k times.

Approach

• The approach used is to first identify the maximum element and its corresponding subarray
• Then, we iterate over the subarray and count the number of subarrays that contain the maximum element at least k times.

Complexity

• O(n), where n is the size of the input array.

Explanation

• The solution first creates a vector to store the indices of the maximum element in the subarray
• It then iterates over the array to find the maximum element and its indices
• After that, it calculates the number of subarrays that contain the maximum element at least k times by iterating over the vector and counting the subarrays.

Solution Code:

class Solution {
public:
    vector v;
    long long countSubarrays(vector& nums, int k) {
        int maxV = 0;
        for(int i = 0 ; i < nums.size(); i++){
            if(maxV < nums[i]){
                maxV = nums[i];
                v.clear();
                v.push_back(i);
            } else if (maxV == nums[i]){
                v.push_back(i);
            }
        }
        v.push_back(nums.size());
        
        long long ans = 0;
        for(int i = k-1; i < v.size()-1; i++){
            long long r = v[i];
            long long l = v[i - k+1];
            ans += (l+1) * (v[i+1]-r);
        }
        return ans;
    }
};

Leetcode Problem:

• Count Subarrays of Length Three With a Condition

Summary

• Given an integer array, return the number of subarrays of length 3 such that the sum of the first and third numbers equals exactly half of the second number.

Approach

• The approach used is to iterate over the array with three nested loops, but with a slight modification
• Instead of using three nested loops, we use two nested loops and check for the third element
• We then check if the sum of the first and third elements equals half of the second element, and if so, we increment the count.

Complexity

• O(n^2)

Explanation

• The solution iterates over the array with two nested loops, where the outer loop iterates over the first element and the inner loop iterates over the third element
• For each pair of elements, it checks if the sum of the first and third elements equals half of the second element
• If so, it increments the count
• The time complexity is O(n^2) because in the worst case, we need to check all pairs of elements.

Solution Code:

class Solution {
public:
    int countSubarrays(vector& nums) {
        int ans = 0;
        for(int i = 0 ; i < nums.size() - 2; i++){
            if((nums[i] + nums[i+2])*2 == nums[i+1]){
                ans++;
            }
        }
        return ans;
    }
};

Leetcode Problem:

• Count Subarrays With Fixed Bounds

Summary

• Count the number of fixed-bound subarrays in a given array where the minimum and maximum values are within a specified range.

Approach

• The approach used is to maintain two pointers (jmin and jmax) to track the minimum and maximum values within the current window, and another pointer (jbad) to track the first bad element
• The result is updated by summing up the number of valid subarrays that can be formed with the current window.

Complexity

• O(n)

Explanation

• The time complexity is O(n) because each element in the array is visited once
• The space complexity is O(1) because only a constant amount of space is used to store the pointers and the result.

Solution Code:

class Solution {
public:
        long long countSubarrays(vector& A, int minK, int maxK) {
        long res = 0, jbad = -1, jmin = -1, jmax = -1, n = A.size();
        for (int i = 0; i < n; ++i) {
            if (A[i] < minK || A[i] > maxK) jbad = i;
            if (A[i] == minK) jmin = i;
            if (A[i] == maxK) jmax = i;
            res += max(0L, min(jmin, jmax) - jbad);
        }
        return res;
    }
};

Leetcode Problem:

• Count of Interesting Subarrays

Summary

• This problem requires finding the count of subarrays that satisfy a certain condition based on the modulo and k.

Approach

• The solution uses a sliding window approach and a hashmap to keep track of the prefix sum and the count of interesting subarrays.

Complexity

• O(n)

Explanation

• The solution initializes a hashmap to store the prefix sum and its count
• It then iterates over the array, updating the prefix sum and the count of interesting subarrays
• The count of interesting subarrays is updated by adding the count of subarrays that end at the current position and have a prefix sum that satisfies the condition
• The solution returns the total count of interesting subarrays.

Solution Code:

class Solution {
public:
    long long countInterestingSubarrays(vector& nums, int modulo, int k) {
        int n = nums.size();
        unordered_map cnt;
        long long res = 0;
        int prefix = 0;
        cnt[0] = 1;
        for (int i = 0; i < n; i++) {
            prefix += nums[i] % modulo == k;
            res += cnt[(prefix - k + modulo) % modulo];
            cnt[prefix % modulo]++;
        }
        return res;
    }
};

Leetcode Problem:

• Count Complete Subarrays in an Array

Summary

• Count the number of complete subarrays in a given array of positive integers.

Approach

• The solution uses a sliding window approach with two unordered maps
• The first map stores the frequency of each element in the array, and the second map stores the frequency of each element in the current subarray
• The time complexity is O(n^2) due to the nested loops, where n is the size of the array.

Complexity

• O(n^2)

Explanation

• The solution first counts the frequency of each element in the array and stores it in the first unordered map
• Then, it iterates over the array with a sliding window approach
• For each window, it creates a new unordered map to store the frequency of each element in the current subarray
• If the size of the current subarray is equal to the size of the first unordered map, it increments the answer by the length of the current subarray plus one (to include the current element)
• Finally, it returns the answer.

Solution Code:

class Solution {
public:
    unordered_map m;
    int countCompleteSubarrays(vector& nums) {
        
        for(int i = 0 ; i < nums.size(); i++){
            m[nums[i]] = true;
        }
        int ans = 0;
        for(int i = 0 ; i < nums.size(); i++){
            unordered_map m2;
            for(int j = i; j >= 0; j--){
                m2[nums[j]] = true;
                if(m2.size() == m.size()){
                    ans += j + 1;
                    break;
                }
            }
        }
        return ans;
    }
};

Leetcode Problem:

• Count Largest Group

Summary

• Find the number of groups that have the largest size where each number from 1 to n is grouped according to the sum of its digits.

Approach

• The approach used is to calculate the sum of digits for each number from 1 to n, group the numbers by the sum of their digits, and then count the number of groups with the largest size.

Complexity

• O(n log n) due to the calculation of sum of digits for each number, where n is the input number.

Explanation

• The solution code first defines a helper function to calculate the sum of digits for a given number
• Then, it initializes an array to store the groups of numbers with the same sum of digits
• It iterates through each number from 1 to n, calculates the sum of its digits, and adds it to the corresponding group in the array
• If the size of the current group is larger than the largest group size found so far, it updates the largest group size and sets the answer to 1
• If the size of the current group is equal to the largest group size, it increments the answer
• Finally, it returns the answer, which represents the number of groups with the largest size.

Solution Code:

class Solution {
public:
    int getSum(int n){
        int s = 0;
        while(n){
            s += n % 10;
            n /= 10;
        }
        return s;
    }
    int countLargestGroup(int n) {
        vector groups[37];
        int largestGroupSize = 0;
        int ans = 0;
        for(int i = 1; i <= n; i++){
            int group = getSum(i);
            groups[group].push_back(i);
            if(largestGroupSize < groups[group].size()){
                largestGroupSize = groups[group].size();
                ans = 1;
            } else if(largestGroupSize == groups[group].size()){
                ans++;
            }
        }
        return ans;
    }
};

Leetcode Problem:

• Count the Number of Ideal Arrays

Summary

• The problem requires finding the number of distinct ideal arrays of length n, where an ideal array is defined as an array where every element is a value from 1 to maxValue, and every element is divisible by the previous element.

Approach

• The approach used is dynamic programming and prime factorization
• The solution first calculates the prime factors of each number from 1 to maxValue and stores them in a list
• Then, it uses a dynamic programming table to calculate the number of ideal arrays for each possible value of the first element
• Finally, it sums up the number of ideal arrays for each value and returns the result modulo 10^9 + 7.

Complexity

• O(n * maxValue * log(maxValue))

Explanation

• The solution first calculates the prime factors of each number from 1 to maxValue and stores them in a list
• Then, it uses a dynamic programming table to calculate the number of ideal arrays for each possible value of the first element
• The dynamic programming table is initialized with c[i][j] = 1, where c[i][j] represents the number of ideal arrays of length i with j prime factors
• Then, for each prime factor p, it updates the dynamic programming table with c[i][j] = (c[i][j] + c[i - 1][j - 1]) % MOD, where c[i - 1][j - 1] represents the number of ideal arrays of length i - 1 with j - 1 prime factors
• Finally, it sums up the number of ideal arrays for each value and returns the result modulo 10^9 + 7.

Solution Code:

const int MOD = 1e9 + 7, MAX_N = 1e4 + 10,
          MAX_P = 15;  // There are up to 15 prime factors
int c[MAX_N + MAX_P][MAX_P + 1];
vector ps[MAX_N];  // List of prime factor counts
int sieve[MAX_N];       // Minimum prime factor

class Solution {
public:
    Solution() {
        if (c[0][0]) {
            return;
        }
        for (int i = 2; i < MAX_N; i++) {
            if (sieve[i] == 0) {
                for (int j = i; j < MAX_N; j += i) {
                    sieve[j] = i;
                }
            }
        }
        for (int i = 2; i < MAX_N; i++) {
            int x = i;
            while (x > 1) {
                int p = sieve[x];
                int cnt = 0;
                while (x % p == 0) {
                    x /= p;
                    cnt++;
                }
                ps[i].push_back(cnt);
            }
        }
        c[0][0] = 1;
        for (int i = 1; i < MAX_N + MAX_P; i++) {
            c[i][0] = 1;
            for (int j = 1; j <= min(i, MAX_P); j++) {
                c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % MOD;
            }
        }
    }
    int idealArrays(int n, int maxValue) {
        long long ans = 0;
        for (int x = 1; x <= maxValue; x++) {
            long long mul = 1;
            for (int p : ps[x]) {
                mul = mul * c[n + p - 1][p] % MOD;
            }
            ans = (ans + mul) % MOD;
        }
        return ans;
    }
};

Leetcode Problem:

• Count the Hidden Sequences

Summary

• This problem is about finding the number of possible hidden sequences given the differences between consecutive integers, a lower bound, and an upper bound.

Approach

• The approach used is to calculate the maximum and minimum possible values of the hidden sequence by summing the differences, then checking if the difference between the maximum and minimum possible values is within the given range
• If it is, the number of possible sequences is the difference between the upper and lower bounds plus one.

Complexity

• O(n), where n is the number of differences

Explanation

• The solution iterates through the differences, calculating the cumulative sum and updating the maximum and minimum possible values
• It then checks if the difference between the maximum and minimum possible values is within the given range
• If it is, the number of possible sequences is calculated by subtracting the difference from the difference between the upper and lower bounds and adding one.

Solution Code:

class Solution {
public:
    int numberOfArrays(vector& differences, int lower, int upper) {
        long long maxV = 0;
        long long minV = 0;
        long long cur = 0;
        for(int i = 0; i < differences.size(); i++){
            cur += differences[i];
            maxV = max(maxV, cur);
            minV = min(minV, cur);
        }
        int diff1 = maxV - minV;
        int diff2 = upper - lower;
        if(diff1 > diff2){
            return 0;
        } else{
            return diff2 - diff1 + 1;
        }
    }
};

Leetcode Problem:

• Rabbits in Forest

Summary

• Find the minimum number of rabbits in the forest given the answers to the question about the number of rabbits of the same color.

Approach

• The solution uses an array to count the frequency of each color of rabbit
• It then iterates over the array, adding the number of rabbits of each color to the total answer
• If a color has no rabbits, it is skipped
• The solution assumes that the number of rabbits of a color is a multiple of the number of rabbits that answered the question.

Complexity

• O(n), where n is the number of rabbits that answered the question, because each rabbit is counted once.

Solution Code:

class Solution {
public:
    int sameCnt[1001];
    int numRabbits(vector& answers) {
        for(int i = 0 ; i < answers.size(); i++){
            sameCnt[answers[i]]++;
        }
        int ans = sameCnt[0];
        for(int i = 1 ; i < 1000; i++){
            if(sameCnt[i] == 0) continue;
            ans += (i+1)*((sameCnt[i] - 1)/ (i + 1) + 1);
        }
        return ans;
    }
};