Jobs

Interviews

Discussions

Count Array Pairs Divisible by K

Hard

PayPal

0 views

Topics:

ArraysTwo Pointers

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.

Example 1:

Input: nums = [1,2,3,4,5], k = 2
Output: 7
Explanation: 
The 7 pairs of indices whose corresponding products are divisible by 2 are
(0, 1), (0, 3), (1, 2), (1, 3), (1, 4), (2, 3), and (3, 4).
Their products are 2, 4, 6, 8, 10, 12, and 20 respectively.
Other pairs such as (0, 2) and (2, 4) have products 3 and 15 respectively, which are not divisible by 2.

Example 2:

Input: nums = [1,2,3,4], k = 5
Output: 0
Explanation: There does not exist any pair of indices whose corresponding product is divisible by 5.

Constraints:

1 <= nums.length <= 10⁵
1 <= nums[i], k <= 10⁵

Count Array Pairs Divisible by K

Hard

PayPal

0 views

Topics:

ArraysTwo Pointers

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.

Example 1:

Input: nums = [1,2,3,4,5], k = 2
Output: 7
Explanation: 
The 7 pairs of indices whose corresponding products are divisible by 2 are
(0, 1), (0, 3), (1, 2), (1, 3), (1, 4), (2, 3), and (3, 4).
Their products are 2, 4, 6, 8, 10, 12, and 20 respectively.
Other pairs such as (0, 2) and (2, 4) have products 3 and 15 respectively, which are not divisible by 2.

Example 2:

Input: nums = [1,2,3,4], k = 5
Output: 0
Explanation: There does not exist any pair of indices whose corresponding product is divisible by 5.

Constraints:

1 <= nums.length <= 10⁵
1 <= nums[i], k <= 10⁵

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the constraints on the size of the input array `nums` and the value of `k`?
Can the elements in the `nums` array be negative, zero, or non-integer values?
If no pairs satisfy the condition, what should I return?
Are there any specific considerations for large values of `nums[i] * nums[j]` that could lead to integer overflow?
Can `k` be zero? If so, how should I handle it?

Brute Force Solution

Approach

The problem asks us to find pairs of numbers within a group that, when multiplied together, can be perfectly divided by a specific number. The brute force way is to simply try out every possible pair and see if it fits the condition. This means checking each number against every other number.

Here's how the algorithm would work step-by-step:

Take the first number in the group.
Multiply it by the second number in the group.
Check if the result of that multiplication can be perfectly divided by the specified number. If it can, count it as a valid pair.
Multiply the first number by the third number, then the fourth, and so on, checking divisibility each time and counting the valid pairs.
Once you've checked the first number against all the others, move to the second number.
Multiply the second number by the third, then the fourth, and so on (you don't need to check it with the first number again, since you already did that).
Keep repeating this process, pairing each number with all the numbers that come after it in the group.
Add up the total number of valid pairs you found during this process. That's your answer.

Code Implementation

def count_array_pairs_divisible_by_k(numbers, divisor):
    count_divisible_pairs = 0

    # Iterate through the array to choose the first number in each pair
    for first_index in range(len(numbers)):
        # Iterate from the next element to avoid duplicate pairs

        for second_index in range(first_index + 1, len(numbers)):
            # This condition avoids checking against elements already checked

            product_of_numbers = numbers[first_index] * numbers[second_index]

            # Check if the product is divisible by the divisor
            if product_of_numbers % divisor == 0:
                count_divisible_pairs += 1

    return count_divisible_pairs

Big(O) Analysis

Time Complexity

O(n²) – The provided solution iterates through each element of the input array of size n. For each element, it iterates through the remaining elements to check for divisibility after multiplying the pair. This nested iteration results in (n-1) + (n-2) + ... + 1 operations, which is the sum of an arithmetic series. The total number of operations is proportional to n * (n-1) / 2, which simplifies to O(n²).

Space Complexity

O(1) – The provided brute force solution iterates through pairs of numbers within the input array, but it does not utilize any auxiliary data structures to store intermediate results or track visited elements. The algorithm solely relies on a counter variable to accumulate the number of divisible pairs. Therefore, the space complexity is constant, independent of the input array size N.

Optimal Solution

Approach

The efficient solution avoids checking every single pair of numbers. Instead, it focuses on finding the remainders when each number is divided by the given divisor, and cleverly uses math to figure out which pairs of remainders would result in a number divisible by the divisor.

Here's how the algorithm would work step-by-step:

First, for each number in the given list, calculate the remainder after dividing it by the given divisor.
Then, count how many times each unique remainder appears in the list of remainders.
Next, for each possible remainder value, determine which other remainder value(s) can be paired with it so that when you add those remainders together, the result is perfectly divisible by the given divisor. Think about complementary remainders - remainders that add up to the divisor.
Finally, use the counts of the remainders to calculate how many pairs can be made using the complementary remainders you identified. You may need to handle cases where a remainder can be paired with itself.

Code Implementation

def count_array_pairs_divisible_by_k(numbers, divisor):
    remainders = [number % divisor for number in numbers]

    remainder_counts = {}
    for remainder in remainders:
        remainder_counts[remainder] = remainder_counts.get(remainder, 0) + 1

    pair_count = 0
    for remainder in remainder_counts:
        # Find the complementary remainder.
        complementary_remainder = (divisor - remainder) % divisor

        # If the remainder is its own complement.
        if remainder == complementary_remainder:
            # Use combination formula to avoid double counting.
            pair_count += remainder_counts[remainder] * (remainder_counts[remainder] - 1) // 2
        # Ensure each pair is counted only once.
        elif remainder < complementary_remainder:
            # Count pairs using complementary remainders.
            if complementary_remainder in remainder_counts:
                pair_count += remainder_counts[remainder] * remainder_counts[complementary_remainder]

    return pair_count

Big(O) Analysis

Time Complexity

O(n + k) – The algorithm first iterates through the input array of size n to calculate the remainders when each number is divided by k. This takes O(n) time. Next, it counts the occurrences of each remainder. Because remainders can only range from 0 to k-1, this step takes O(k) time. Finally, it iterates through these possible remainders to find complementary pairs, which also takes O(k) time. The overall time complexity is therefore O(n + k + k), which simplifies to O(n + k).

Space Complexity

O(K) – The auxiliary space is dominated by the storage needed to count the occurrences of each remainder. Since we are taking the remainder after dividing by K, there can be at most K distinct remainders (0 to K-1). Therefore, we use a hash map or array of size K to store these counts. This means that the space required grows linearly with K, so the space complexity is O(K).

Edge Cases

Case	How to Handle
Empty input array nums	Return 0 immediately as no pairs can be formed.
Input array nums has only one element	Return 0 immediately as no pairs can be formed.
k is 1	Every pair will be divisible by 1, so return the number of possible pairs (n * (n - 1) / 2).
k is a large prime number and no product of elements in nums is divisible by k	Return 0 since no pairs satisfy the condition.
nums contains very large numbers such that the product of two numbers may cause an integer overflow.	Use a data type that can handle larger numbers, like long long in C++ or convert to GCD problem.
nums contains negative numbers	The product can be negative or positive, so the divisibility check should handle both cases (e.g., using the modulo operator correctly).
k is zero	Division by zero error; must be handled by returning 0, or throwing an error, depending on requirements.
Large input array nums, potentially leading to time limit exceed issues	Optimize for time complexity, such as using a HashMap based on the greatest common divisor (GCD) with K, and iterating up to the sqrt(K).

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the constraints on the size of the input array `nums` and the value of `k`?
Can the elements in the `nums` array be negative, zero, or non-integer values?
If no pairs satisfy the condition, what should I return?
Are there any specific considerations for large values of `nums[i] * nums[j]` that could lead to integer overflow?
Can `k` be zero? If so, how should I handle it?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Take the first number in the group.
Multiply it by the second number in the group.
Check if the result of that multiplication can be perfectly divided by the specified number. If it can, count it as a valid pair.
Multiply the first number by the third number, then the fourth, and so on, checking divisibility each time and counting the valid pairs.
Once you've checked the first number against all the others, move to the second number.
Multiply the second number by the third, then the fourth, and so on (you don't need to check it with the first number again, since you already did that).
Keep repeating this process, pairing each number with all the numbers that come after it in the group.
Add up the total number of valid pairs you found during this process. That's your answer.

Code Implementation

def count_array_pairs_divisible_by_k(numbers, divisor):
    count_divisible_pairs = 0

    # Iterate through the array to choose the first number in each pair
    for first_index in range(len(numbers)):
        # Iterate from the next element to avoid duplicate pairs

        for second_index in range(first_index + 1, len(numbers)):
            # This condition avoids checking against elements already checked

            product_of_numbers = numbers[first_index] * numbers[second_index]

            # Check if the product is divisible by the divisor
            if product_of_numbers % divisor == 0:
                count_divisible_pairs += 1

    return count_divisible_pairs

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

First, for each number in the given list, calculate the remainder after dividing it by the given divisor.
Then, count how many times each unique remainder appears in the list of remainders.
Next, for each possible remainder value, determine which other remainder value(s) can be paired with it so that when you add those remainders together, the result is perfectly divisible by the given divisor. Think about complementary remainders - remainders that add up to the divisor.
Finally, use the counts of the remainders to calculate how many pairs can be made using the complementary remainders you identified. You may need to handle cases where a remainder can be paired with itself.

Code Implementation

def count_array_pairs_divisible_by_k(numbers, divisor):
    remainders = [number % divisor for number in numbers]

    remainder_counts = {}
    for remainder in remainders:
        remainder_counts[remainder] = remainder_counts.get(remainder, 0) + 1

    pair_count = 0
    for remainder in remainder_counts:
        # Find the complementary remainder.
        complementary_remainder = (divisor - remainder) % divisor

        # If the remainder is its own complement.
        if remainder == complementary_remainder:
            # Use combination formula to avoid double counting.
            pair_count += remainder_counts[remainder] * (remainder_counts[remainder] - 1) // 2
        # Ensure each pair is counted only once.
        elif remainder < complementary_remainder:
            # Count pairs using complementary remainders.
            if complementary_remainder in remainder_counts:
                pair_count += remainder_counts[remainder] * remainder_counts[complementary_remainder]

    return pair_count

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty input array nums	Return 0 immediately as no pairs can be formed.
Input array nums has only one element	Return 0 immediately as no pairs can be formed.
k is 1	Every pair will be divisible by 1, so return the number of possible pairs (n * (n - 1) / 2).
k is a large prime number and no product of elements in nums is divisible by k	Return 0 since no pairs satisfy the condition.
nums contains very large numbers such that the product of two numbers may cause an integer overflow.	Use a data type that can handle larger numbers, like long long in C++ or convert to GCD problem.
nums contains negative numbers	The product can be negative or positive, so the divisibility check should handle both cases (e.g., using the modulo operator correctly).
k is zero	Division by zero error; must be handled by returning 0, or throwing an error, depending on requirements.
Large input array nums, potentially leading to time limit exceed issues	Optimize for time complexity, such as using a HashMap based on the greatest common divisor (GCD) with K, and iterating up to the sqrt(K).