hard Count Array Pairs Divisible by K

Problem Statement

Given an integer array nums containing n elements 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.

Examples

• Example 1:

  • Input: nums = [8, 4, 6, 12], k = 4
  • Expected Output: 6
  • Justification: The pairs that satisfy the conditions are (8, 4), (8, 6), (8, 12), (4, 6), (4, 12), and (6, 12). The products of these pairs are divisible by 4.

• Example 2:

  • Input: nums = [10, 5, 2, 6], k = 5
  • Expected Output: 5
  • Justification: The valid pairs are (10, 5), (10, 2), (5, 2), (5, 6), and (10, 6). Each product of these pairs is divisible by 5.

• Example 3:

  • Input: nums = [4, 7, 9, 11, 23], k = 3
  • Expected Output: 4
  • Justification: The pairs are (4, 9), (7, 9), (9, 11), and (9, 23). The products of these pairs are divisible by 3.

Solution

To solve this problem, we adopt a mathematical and hash map-based approach that focuses on the properties of divisibility and the Greatest Common Divisor (GCD). The core idea hinges on the fact that if the product of two numbers is divisible by k, then the GCD of each number with k must also meet certain divisibility conditions.

Specifically, for two numbers a and b, if gcd(a, k) * gcd(b, k) is divisible by k, then a * b is divisible by k. This insight allows us to transform the problem into one of counting pairs based on their GCDs with k, significantly reducing the problem's complexity from potentially quadratic to more manageable levels. We leverage a hash map to efficiently count and pair up elements with compatible GCDs, ensuring a thorough yet efficient examination of all possible pairings without direct multiplication, thus optimizing both performance and scalability.

Step-by-Step Algorithm

1. Initialize a result variable: This variable will hold the final count of pairs whose product is divisible by k.

2. Create a hash map (gcdMap): This map will store the greatest common divisor (GCD) of the elements in the array with k as keys, and the frequency of these GCDs as values.

3. Iterate through the array:

   • For each element in the array, calculate the GCD of the element and k.
   • For every GCD value calculated, iterate through the keys in gcdMap:
     • If the product of the current GCD and any GCD in the map is divisible by k (checking (long) gcd * num % k == 0 to avoid integer overflow), add the frequency of that GCD in the map to the result. This step effectively counts pairs formed by the current element and elements previously processed.
   • Update gcdMap with the current GCD, incrementing its frequency by 1. If the GCD is already a key in the map, its value is increased; otherwise, it is added to the map with a frequency of 1.

4. Return the result: After iterating through all elements in the array and updating the result based on the conditions checked, return the final count of pairs.

Algorithm Walkthrough

Let's consider the Input: nums= [10, 5, 2, 6], k = 5.

1. Initialization: Start with an empty gcdMap and result set to 0.

2. First element (10):

   • Compute gcd(10, 5) = 5.
   • No existing keys in gcdMap, so nothing to add to the result yet. result = 0.
   • Update gcdMap to {5: 1}.

3. Second element (5):

   • Compute gcd(5, 5) = 5.
   • Existing key 5 in gcdMap with frequency 1. Since 5 * 5 % 5 == 0, add 1 to the result. result = 1.
   • Update gcdMap to {5: 2} (since 5 appears twice now).

4. Third element (2):

   • Compute gcd(2, 5) = 1.
   • For existing key 5 in gcdMap: 5 * 1 % 5 == 0, add 2 to the result (because there are 2 elements with GCD 5 so far). result = 3.
   • Update gcdMap to {5: 2, 1: 1}.

5. Fourth element (6):

   • Compute gcd(6, 5) = 1.
   • For existing key 5 in gcdMap: 5 * 1 % 5 == 0, add 2 to the result. result = 5.
   • For existing key 1 in gcdMap: 1 * 1 % 5 == 4. So, don't need to add anything in result.
   • Update gcdMap to {5: 2, 1: 2}.

6. Final result: The total count of valid pairs is 5.

Code

import java.util.HashMap;
import java.util.Map;

public class Solution {

  // Counts pairs in nums where the product of each pair is divisible by k
  public long countPairs(int[] nums, int k) {
    long result = 0; // Initialize result to store the final count
    Map<Integer, Integer> gcdMap = new HashMap<>(); // Map to store gcd values and their frequencies

    // Iterate over each element in the array
    for (int i = 0; i < nums.length; i++) {
      int gcd = findGcd(nums[i], k); // Find gcd of current element and k

      // Check if the product of gcd of current element with each previously seen gcd is divisible by k
      for (int num : gcdMap.keySet()) {
        if (((long) gcd * num) % k == 0) { // Cast to long to prevent integer overflow
          result += gcdMap.get(num); // If divisible, add the frequency of the gcd to the result
        }
      }

      // Update the gcdMap with the current gcd, incrementing its frequency
      gcdMap.put(gcd, gcdMap.getOrDefault(gcd, 0) + 1);
    }
    return result; // Return the total count of divisible pairs
  }

  // Helper method to find gcd of two numbers
  private int findGcd(int x, int y) {
    if (x < y) {
      return findGcd(y, x); // Ensure the larger number is the first parameter
    }
    // Recursive call to find gcd using Euclidean algorithm
    return y == 0 ? x : findGcd(y, x % y);
  }

  // Main method to test the countPairs method with given examples
  public static void main(String[] args) {
    Solution sol = new Solution();

    // Example 1
    int[] nums1 = { 8, 4, 6, 12 };
    int k1 = 4;
    System.out.println("Example 1 Output: " + sol.countPairs(nums1, k1)); // Expected Output: 6

    // Example 2
    int[] nums2 = { 10, 5, 2, 6 };
    int k2 = 5;
    System.out.println("Example 2 Output: " + sol.countPairs(nums2, k2)); // Expected Output: 5

    // Example 3
    int[] nums3 = { 4, 7, 9, 11, 23 };
    int k3 = 3;
    System.out.println("Example 3 Output: " + sol.countPairs(nums3, k3)); // Expected Output: 4
  }
}

Complexity Analysis

• Time Complexity: , where n is the number of elements in the input array, log(k) is the complexity of calculating the GCD of an element with k, and D(k) represents the number of distinct divisors of k. This accounts for iterating through each element, calculating the GCD, and checking divisibility conditions with all entries in a map.

• Space Complexity: , which is determined by the number of distinct GCD values stored in the map, corresponding to the number of distinct divisors of k. This space is used to track the frequency of each GCD value among the elements of the array.