Count Equal and Divisible Pairs in an Array

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

Example 1:

Input: nums = [3,1,2,2,2,1,3], k = 2
Output: 4
Explanation:
There are 4 pairs that meet all the requirements:
- nums[0] == nums[6], and 0 * 6 == 0, which is divisible by 2.
- nums[2] == nums[3], and 2 * 3 == 6, which is divisible by 2.
- nums[2] == nums[4], and 2 * 4 == 8, which is divisible by 2.
- nums[3] == nums[4], and 3 * 4 == 12, which is divisible by 2.

Example 2:

Input: nums = [1,2,3,4], k = 1
Output: 0
Explanation: Since no value in nums is repeated, there are no pairs (i,j) that meet all the requirements.

Constraints:

• 1 <= nums.length <= 100
• 1 <= nums[i], k <= 100

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

# Example 1
nums1 = [3, 1, 2, 2, 2, 1, 3]
k1 = 2
print(f"Example 1: {count_pairs(nums1, k1)}")  # Output: 4

# Example 2
nums2 = [1, 2, 3, 4]
k2 = 1
print(f"Example 2: {count_pairs(nums2, k2)}")  # Output: 0


# Brute Force Solution
# The above solution is already a brute force approach.
# It iterates through all possible pairs and checks the conditions.


# Optimized Solution
# While the problem constraints are small (n <= 100), the brute force solution is efficient enough.
# However, for larger arrays, we can potentially optimize by using a hash map to store the indices of each number.


def count_pairs_optimized(nums, k):
    n = len(nums)
    count = 0
    num_indices = {}
    for i in range(n):
        if nums[i] not in num_indices:
            num_indices[nums[i]] = []
        num_indices[nums[i]].append(i)

    for num in num_indices:
        indices = num_indices[num]
        for i in range(len(indices)):
            for j in range(i + 1, len(indices)):
                index1 = indices[i]
                index2 = indices[j]
                if (index1 * index2) % k == 0:
                    count += 1
    return count

print(f"Example 1 (Optimized): {count_pairs_optimized(nums1, k1)}")
print(f"Example 2 (Optimized): {count_pairs_optimized(nums2, k2)}")

# Big O Runtime Analysis:
# The brute force solution has a time complexity of O(n^2) because it iterates through all possible pairs of indices in the array.
# The optimized solution using a hash map also has a time complexity of O(n^2) in the worst case. Although we use a hash map to store the indices, we still need to iterate through all possible pairs of indices for each number, which results in O(n^2).

# Big O Space Usage Analysis:
# The brute force solution has a space complexity of O(1) because it uses a constant amount of extra space.
# The optimized solution has a space complexity of O(n) in the worst case, where n is the length of the array. This is because the hash map num_indices can store up to n key-value pairs, where each key is a number in the array and each value is a list of indices for that number.

# Edge Cases:
# 1. Empty array: If the input array is empty, the function should return 0.
# 2. k = 0: If k is 0, then (i * j) % k will raise a ZeroDivisionError. The problem statement says 1 <= k <= 100, so k cannot be 0.
# 3. All elements are the same: If all elements in the array are the same, the function should correctly count the number of pairs where (i * j) is divisible by k.
# 4. No pairs satisfy the condition: If no pairs satisfy the condition nums[i] == nums[j] and (i * j) % k == 0, the function should return 0.
# 5. Large array size: The problem statement says 1 <= nums.length <= 100, so the array size will not be very large. However, if the array size is very large, the time complexity of O(n^2) could become a problem. In that case, we may need to consider more advanced data structures and algorithms to optimize the solution.