짬뽕얼큰하게의 맨땅에 헤딩 :: '2025/04/17 글 목록

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

Count Equal and Divisible Pairs in an Array

알고리즘 2025. 4. 17. 21:19

Leetcode Problem:

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

'알고리즘' 카테고리의 다른 글

Rabbits in Forest  (0) 2025.04.20
Count the Number of Fair Pairs  (0) 2025.04.19
Count the Number of Good Subarrays  (0) 2025.04.17
Count Good Triplets in an Array  (0) 2025.04.15
Count Good Triplets  (0) 2025.04.14
블로그 이미지

짬뽕얼큰하게

,

Count the Number of Good Subarrays

알고리즘 2025. 4. 17. 00:24

Leetcode Problem:

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

'알고리즘' 카테고리의 다른 글

Count the Number of Fair Pairs  (0) 2025.04.19
Count Equal and Divisible Pairs in an Array  (0) 2025.04.17
Count Good Triplets in an Array  (0) 2025.04.15
Count Good Triplets  (0) 2025.04.14
Count Good Numbers  (0) 2025.04.13
블로그 이미지

짬뽕얼큰하게

,

공지사항

글 보관함

달력

«   2025/04   »
일 월 화 수 목 금 토
1 2 3 4 5
6 7 8 9 10 11 12
13 14 15 16 17 18 19
20 21 22 23 24 25 26
27 28 29 30

티스토리툴바