Count Array Pairs Divisible by k

Problem statement

Given a 0-indexed integer array nums of length n and an integer k, return the number of pairs (i, j) such that:

• 0 <= i < j <= n - 1 and
• nums[i] * nums[j] is divisible by k.

Java Approach 1 Frequency Counting

Output:

Code Explanation:

• The above Java code aims to count pairs in an array where the greatest common divisor (gcd) of the pair's elements is equal to a given value k. It uses a Map to store the count of gcd values and iterates through the array to populate this map.
• Then, it iterates through the map to find pairs with gcd equal to k and updates the result accordingly. The code employs BigInteger to calculate gcd for handling large numbers.

Time complexity:

• The time complexity of the provided code is approximately O(n^2), where n is the length of the input array nums. This is due to the nested loops iterating through the cnt map.
• The outer loop iterates through unique gcd values, and the inner loop compares and calculates pairs with gcd equal to k.

Space complexity:

• The space complexity is O(n) as the code uses a HashMap to store gcd frequencies, and in the worst case, it could have n unique gcd values.

Drawbacks:

• The code has drawbacks in terms of both time and space efficiency. It uses nested loops, resulting in a time complexity of O(n^2), which can be impractical for large inputs. Additionally, it employs a HashMap to store gcd frequencies, leading to O(n) space complexity.
• The inefficient pairwise comparison in the inner loop contributes to a less optimized algorithm.

Java Approach 2 Using Combination of Counting and Combinatorics

Output:

Code explanation:

• The code aims to count pairs in an array where the greatest common divisor (gcd) of the pair is equal to a given value k. It utilizes an array, cntgcd, to store frequencies of gcd values. The code iterates through the array, calculating gcd for each element, and then computes the count of pairs based on gcd values.
• The approach efficiently handles different cases, such as when the gcd is less than k or when k is divisible by the gcd.

Time complexity:

• The time complexity of the provided code is O(n), where n is the length of the input array nums. The code iterates through the array to calculate the gcd for each element, and later, it counts pairs based on gcd values.

Space complexity:

• The space complexity is O(k), where k is the given input value. It utilizes an array, cntgcd, to store the frequencies of gcd values, contributing to the overall space complexity.