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.

Try it yourself

Try solving this question here: