'알고리즘'에 해당되는 글 281건

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

Leetcode Problem:

• Count the Number of Fair Pairs

Summary

• The problem is to count the number of fair pairs in a given integer array, where a pair is considered fair if the sum of its elements falls within a specified range.

Approach

• The approach used is to first sort the array and then use a binary search approach to find the number of pairs that satisfy the condition
• The binary search is performed in two separate ranges, one for the lower bound and one for the upper bound, to ensure that the sum of each pair falls within the specified range.

Complexity

• O(n log n) due to the sorting operation, where n is the size of the array.

Explanation

• The code sorts the array and then iterates over each element
• For each element, it uses binary search to find the number of pairs that satisfy the condition
• The binary search is performed in two separate ranges, one for the lower bound and one for the upper bound
• The results of the binary searches are then combined to calculate the total number of fair pairs.

Solution Code:

class Solution {
public:
    long long countFairPairs(vector& nums, int lower, int upper) {
        sort(nums.begin(), nums.end());
        
        long long ans = 0;
        for(int i = 0 ; i < nums.size(); i++){
            int l = i+1;
            int r = nums.size() - 1;
            int low = 123456789;
            while(l <= r){
                int mid = (l + r ) / 2;
                if(nums[mid] + nums[i] >= lower){
                    r = mid - 1;
                    low = mid;
                }else{
                    l = mid + 1;
                }
            }
            l = i + 1;
            r = nums.size() - 1;
            int up = 0;
            while(l <= r){
                int mid = (l + r ) / 2;
                if(nums[mid] + nums[i] <= upper){
                    l = mid + 1;
                    up = mid;
                }else{
                    r = mid - 1;
                }
            }
            if(low<=up){
                ans += up - low + 1;
            }
            
        }
        return ans;
    }
};

Leetcode Problem:

• Count Equal and Divisible Pairs in an Array

Summary

• Given an integer array and an integer k, return the number of pairs where the product of indices is divisible by k.

Approach

• The approach is to use two nested loops to generate all possible pairs of indices in the array
• For each pair, we check if the elements at those indices are equal and if their product is divisible by k
• If both conditions are met, we increment the answer counter.

Complexity

• O(n^2) where n is the length of the input array

Explanation

• The time complexity is O(n^2) because we have two nested loops that iterate over the array
• The space complexity is O(1) because we only use a constant amount of space to store the answer and other variables.

Solution Code:

class Solution {
public:
    int countPairs(vector& nums, int k) {
        int ans = 0;
        for(int i = 0 ; i < nums.size(); i++){
            for(int j = i + 1; j < nums.size(); j++){
                if(nums[i] != nums[j]) continue;
                if((i*j)%k != 0) continue;
                ans++;
            }
        }
        return ans;
    }
};

Leetcode Problem:

• Count the Number of Good Subarrays

Summary

• This problem requires us to find the number of good subarrays in a given array
• A good subarray is a subarray that has at least k pairs of indices (i, j) such that i < j and arr[i] == arr[j].

Approach

• The solution uses a sliding window approach with two pointers, i and j, to traverse the array
• It also uses a hashmap to store the count of each element in the current window
• The time complexity of this approach is O(n), where n is the size of the array.

Complexity

• O(n)

Explanation

• The solution starts by initializing a hashmap to store the count of each element in the array
• It then traverses the array using two pointers, i and j
• For each element at index j, it increments the count of the element in the hashmap and subtracts 1 from the count of the element at index i
• If the count of the element at index j is greater than 0, it means that there is already a pair of indices (i, j) such that i < j and arr[i] == arr[j], so it increments the result by j
• If the count of the element at index j is 0, it means that there is no pair of indices (i, j) such that i < j and arr[i] == arr[j], so it increments the count of the element at index j and continues to the next element
• Finally, the solution returns the result.

Solution Code:

class Solution {
public:
    long long countGood(vector& A, int k) {
        long long res = 0;
        unordered_map count;
        for (int i = 0, j = 0; j < A.size(); ++j) {
            k -= count[A[j]]++;
            while (k <= 0)
                k += --count[A[i++]];
            res += i;
        }
        return res;
    }
};

Leetcode Problem:

• Count Good Triplets in an Array

Summary

• Given two 0-indexed arrays of length n, find the total number of good triplets which are in increasing order in both arrays.

Approach

• The approach used is to create a Fenwick Tree to efficiently calculate prefix sums, then for each value in the first array, calculate the number of good triplets by querying the Fenwick Tree for the number of elements to the left and right, and multiplying these counts together.

Complexity

• O(n log n) due to the Fenwick Tree operations, where n is the length of the input arrays.

Solution Code:

class FenwickTree {
private:
    vector tree;

public:
    FenwickTree(int size) : tree(size + 1, 0) {}

    void update(int index, int delta) {
        index++;
        while (index < tree.size()) {
            tree[index] += delta;
            index += index & -index;
        }
    }

    int query(int index) {
        index++;
        int res = 0;
        while (index > 0) {
            res += tree[index];
            index -= index & -index;
        }
        return res;
    }
};

class Solution {
public:
    long long goodTriplets(vector& nums1, vector& nums2) {
        int n = nums1.size();
        vector pos2(n), reversedIndexMapping(n);
        for (int i = 0; i < n; i++) {
            pos2[nums2[i]] = i;
        }
        for (int i = 0; i < n; i++) {
            reversedIndexMapping[pos2[nums1[i]]] = i;
        }
        FenwickTree tree(n);
        long long res = 0;
        for (int value = 0; value < n; value++) {
            int pos = reversedIndexMapping[value];
            int left = tree.query(pos);
            tree.update(pos, 1);
            int right = (n - 1 - pos) - (value - left);
            res += (long long)left * right;
        }
        return res;
    }
};