Count Equal And Divisible Pairs In An Array - Leetcode Solution

Problem Statement:

Given an array of integers nums, return the number of pairs (i, j) where i < j that satisfy both of the following conditions:

1. nums[i] == nums[j]
2. nums[i] / nums[j] == k for some integer k (i.e., k is an integer)

Constraints:

1. 1 <= nums.length <= 1000
2. -10^9 <= nums[i] <= 10^9
3. 2 <= k <= 10^9

Solution:

We can solve this problem using two approaches. The first approach is the brute-force approach, which has a time complexity of O(n^2). In the worst-case scenario, the input array can have 1000 integers, so the time complexity can be too high. Therefore, we will implement a second approach, which has a time complexity of O(n).

1. Brute Force Approach:

In this approach, we will iterate over the array using two nested loops. For every pair (i, j) where i < j, we will check if nums[i] == nums[j] and nums[i] / nums[j] == k for some integer k. If both conditions are true, we will increment a counter. Finally, we will return the counter.

Here is the Python code for the brute force approach:

def countPairs(nums): count = 0 n = len(nums) for i in range(n): for j in range(i+1, n): if nums[i] == nums[j] and nums[i] % nums[j] == 0: count += 1 return count

This approach will give the correct result, but it has a high time complexity. Therefore, we will implement a second approach to optimize the solution.

2. Optimized Approach:

In this approach, we will use a hash map to store the frequency of each integer in the array. Then, we will iterate over the array and for each integer x, we will check if x/k is present in the hash map and add its frequency to the answer.

Here is the Python code for the optimized approach:

def countPairs(nums, k): freq = {} for x in nums: freq[x] = freq.get(x, 0) + 1

count = 0
for x in freq:
    if x * k in freq:
        count += freq[x] * freq[x * k]
return count

We can test our solution using the following code:

nums = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] k = 2 print(countPairs(nums, k))

The output of the above code will be 9, which is the correct answer.

Explanation:

In the above code, we first create an empty hash map freq to store the frequency of each integer in nums. Then, we iterate over nums and for each integer x, we increment its frequency in freq using the get() method.

Next, we initialize a counter count to zero and iterate over the keys of freq using the for loop. For each key x, we check if x * k is present in freq. If it is, we add freq[x] * freq[x * k] to count.

Finally, we return the count, which is the number of pairs in nums that satisfy the given conditions.

1