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

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

Leetcode Problem:

• Count Good Triplets

Summary

• Find the number of good triplets in an array of integers given three integers a, b, and c.

Approach

• Three nested loops are used to iterate through the array and check each triplet against the conditions
• The absolute difference between each pair of numbers is calculated and compared to the given integers a, b, and c
• If all conditions are met, the triplet is counted.

Complexity

• O(n^3) where n is the size of the array

Explanation

• The solution uses three nested loops to iterate through the array
• The outer loop starts at the first element, the middle loop starts at the next element after the outer loop, and the inner loop starts at the next element after the middle loop
• The solution checks each triplet against the conditions and increments the count if all conditions are met.

Solution Code:

class Solution {
public:
    
    int countGoodTriplets(vector& arr, int a, int b, int c) {
        int ans = 0;
        for(int i = 0 ; i < arr.size(); i++){
            for(int j = i + 1; j < arr.size(); j++){
                for(int k = j + 1; k < arr.size(); k++){
                    if(abs(arr[i] - arr[j]) <= a &&
                       abs(arr[j] - arr[k]) <= b &&
                       abs(arr[k] - arr[i]) <= c){
                        ans++;
                       }
                }

            }
        }
        return ans;
    }
};

Leetcode Problem:

• Count Good Numbers

Summary

• The problem is to find the total number of good digit strings of length n, where a good digit string is defined as a string where the digits at even indices are even and the digits at odd indices are prime (2, 3, 5, or 7).

Approach

• The solution uses dynamic programming and modular arithmetic to calculate the total number of good digit strings
• It first calculates the number of good digit strings for even and odd indices separately and then combines them to get the final result.

Complexity

• The time complexity of the solution is O(log n) due to the use of modular exponentiation, where n is the length of the input string.

Explanation

• The solution first defines a helper function powpow to calculate the modular exponentiation of a number
• It then calculates the number of good digit strings for even and odd indices separately using this function
• The number of good digit strings for even indices is calculated as 5^a, where a is the number of even indices, and the number of good digit strings for odd indices is calculated as 4^b, where b is the number of odd indices
• The final result is obtained by multiplying these two numbers together and taking the result modulo 10^9 + 7.

Solution Code:

struct powRet{
    long long ret;
    long long n;
};
class Solution {
public:
    const int MOD = 1000000007;
    powRet powpow(long long n, long long num){
        powRet ret;
        long long pow = num;
        long long nn = 1;
        long long beforePow = pow;
        long long beforenn = nn;
        while(nn <= n){
            nn *= 2;
            pow *= pow;
            pow %= MOD;
            if(nn > n) break;
            beforePow = pow;
            beforenn = nn;
        }
        ret.ret = beforePow;
        ret.n = beforenn;
        return ret;
    }
    int countGoodNumbers(long long n) {
        long long ans= 1;
        long long a = (n + 1)/2;
        long long b = n - a;
        while(a){
            powRet ret = powpow(a, 5);
            ans *= ret.ret;
            ans %= MOD;
            a -= ret.n;
        }
        while(b){
            powRet ret = powpow(b, 4);
            ans *= ret.ret;
            ans %= MOD;
            b -= ret.n;
        }
        return ans;
    }
};