algoadvance

Leetcode 2176. Count Equal and Divisible Pairs in an Array

Problem Statement

You are given a 0-indexed integer array nums of length n and an integer k. Find the number of pairs (i, j) where 0 <= i < j < n, such that nums[i] == nums[j] and (i * j) is divisible by k.

Clarifying Questions

1. Range of nums and k: What are the constraints for the values in nums and the value of k?
   • nums can have positive or negative integers, including zero?
   • k is a positive integer?
2. Length of nums: What is the maximum length of the array nums?
   • Is it guaranteed that the array will contain at least two elements?
3. Special Cases: Any special cases to consider?
   • For example, what should be done if all elements in nums are distinct?

Strategy

1. Brute Force Approach:
   • Loop through all pairs (i, j) where i < j.
   • Check if nums[i] == nums[j] and if (i * j) % k == 0.
   • Count such valid pairs.
2. Optimization:
   • Since i < j, for a fixed j, we can try to use a hash map to store previously seen values and their corresponding indices, allowing for quick lookups and reducing the number of comparisons.

Code

Let’s start with the brute force approach for simplicity, and then consider any necessary optimizations based on the performance.

#include <vector>
#include <unordered_map>
using namespace std;

class Solution {
public:
    int countPairs(vector<int>& nums, int k) {
        int n = nums.size();
        int count = 0;
        
        // Brute force approach to check all pairs (i, j) where i < j.
        for (int i = 0; i < n; ++i) {
            for (int j = i + 1; j < n; ++j) {
                if (nums[i] == nums[j] && (i * j) % k == 0) {
                    ++count;
                }
            }
        }
        
        return count;
    }
};

Explanation

1. Initialization:
   • The function countPairs initializes n to the size of nums and count to 0.
   • We will use a nested loop, such that i moves from 0 to n-1 and j moves from i+1 to n.
2. Conditions:
   • For each pair (i, j), it checks if nums[i] == nums[j] and if (i * j) % k == 0.
   • If both conditions are met, it increments count.
3. Return:
   • Finally, it returns the count of valid pairs.

Time Complexity

• The brute force solution has a time complexity of (O(n^2)) due to the doubly nested loop where each element pair (i, j) is considered.
• This is feasible for small lists but may need optimization for larger datasets.

Potential Optimizations

To optimize, we can use additional data structures such as hash maps to store indices and precompute product divisibility conditions. This would reduce the number of checks per comparison:

• Use a hash map to store indices of elements as they are seen.
• For each new element and its index, combine previously stored indices of the same element, checking once if the product is divisible by k.

Would you like to see this optimized version as well?

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?