FastPrepCount Product-Divisible Pairs

Count Product-Divisible Pairs

Motive logoMotive● MediumFULLTIMEPHONE SCREEN
Learn

Problem statement

Given an integer array nums and a positive integer k, return the number of index pairs i < j such that nums[i] * nums[j] is divisible by k.

Function

countProductDivisiblePairs(nums: int[], k: int) → long

Examples

Example 1

nums = [1,2,3,4,5]k = 2return = 7

Example 2

nums = [1,2,3,4]k = 5return = 0

Constraints

  • 1 <= nums.length <= 100000.
  • 0 <= nums[i] <= 10^9.
  • 1 <= k <= 10^5.

More Motive problems

See Motive hiring insights
public long countProductDivisiblePairs(int[] nums, int k) {
  // write your code here
}
nums[1,2,3,4,5]
k2
expected7
Checking account…