Jobs

Interviews

Discussions

Check If Array Pairs Are Divisible by k

Medium

Asked by:

More companies

24 views

Topics:

Arrays

Given an array of integers arr of even length n and an integer k.

We want to divide the array into exactly n / 2 pairs such that the sum of each pair is divisible by k.

Return true If you can find a way to do that or false otherwise.

Example 1:

Input: arr = [1,2,3,4,5,10,6,7,8,9], k = 5
Output: true
Explanation: Pairs are (1,9),(2,8),(3,7),(4,6) and (5,10).

Example 2:

Input: arr = [1,2,3,4,5,6], k = 7
Output: true
Explanation: Pairs are (1,6),(2,5) and(3,4).

Example 3:

Input: arr = [1,2,3,4,5,6], k = 10
Output: false
Explanation: You can try all possible pairs to see that there is no way to divide arr into 3 pairs each with sum divisible by 10.

Constraints:

arr.length == n
1 <= n <= 10⁵
n is even.
-10⁹ <= arr[i] <= 10⁹
1 <= k <= 10⁵

Try coding it in LeetCode

Check If Array Pairs Are Divisible by k

Medium

Asked by:

24 views

Topics:

Arrays

Given an array of integers arr of even length n and an integer k.

We want to divide the array into exactly n / 2 pairs such that the sum of each pair is divisible by k.

Return true If you can find a way to do that or false otherwise.

Example 1:

Input: arr = [1,2,3,4,5,10,6,7,8,9], k = 5
Output: true
Explanation: Pairs are (1,9),(2,8),(3,7),(4,6) and (5,10).

Example 2:

Input: arr = [1,2,3,4,5,6], k = 7
Output: true
Explanation: Pairs are (1,6),(2,5) and(3,4).

Example 3:

Input: arr = [1,2,3,4,5,6], k = 10
Output: false
Explanation: You can try all possible pairs to see that there is no way to divide arr into 3 pairs each with sum divisible by 10.

Constraints:

arr.length == n
1 <= n <= 10⁵
n is even.
-10⁹ <= arr[i] <= 10⁹
1 <= k <= 10⁵

Try coding it in LeetCode

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 integers, zero, or only positive integers?
If the array cannot be divided into pairs whose sum is divisible by `k`, what should I return?
Are duplicate numbers allowed in the input array `nums`?
Do I need to handle the case where the input array `nums` is empty or null?

Brute Force Solution

Approach

The brute force method to solve this involves checking every single possible pairing of numbers. We want to see if, for every pair we pick, their sum is nicely divisible by a given number. This approach guarantees we'll find the answer, albeit slowly, by simply trying all combinations.

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

Take the first number in the list.
Pair it with every other number in the list, one at a time.
For each of these pairs, add the two numbers together.
Check if that sum can be divided evenly by the given number (meaning there's no remainder).
If it can't be divided evenly, that pair doesn't work.
Once you've paired the first number with every other number, move on to the second number.
Repeat the process of pairing it with every remaining number in the list (avoiding duplicates).
Keep doing this until you've considered all possible pairs from the list.
If, at any point, you find a pair that doesn't add up to a multiple of the given number, you know it's impossible to make the pairs work.
If you go through every single possible pair and they all add up to a multiple of the given number, then you've found a successful arrangement.

Code Implementation

def check_if_array_pairs_are_divisible_by_k_brute_force(
    numbers, divisor
):    # Iterate through all possible pairs in the list
    for first_index in range(len(numbers)):
        for second_index in range(first_index + 1, len(numbers)):            # Calculate the sum of the current pair
            current_sum = numbers[first_index] + numbers[second_index]

            # If the sum is not divisible, it's impossible
            if current_sum % divisor != 0:
                return False

    # All pairs are divisible by k
    return True

Big(O) Analysis

Time Complexity

O(n²) – The described brute force approach iterates through all possible pairs in the array. For each of the n elements, it compares that element with roughly n other elements to form a pair. This creates nested iterations where for each element, we are potentially visiting the remaining elements to check if their sum is divisible by k. The total number of pair checks will be approximately n * (n-1) / 2, which simplifies to a time complexity of O(n²).

Space Complexity

O(1) – The brute force algorithm described checks pairs of numbers in the input array. It only uses a few integer variables for indexing into the array and calculating the sum and remainder. No auxiliary data structures like lists or hashmaps are used to store intermediate results or visited elements. Therefore, the space used remains constant regardless of the input array's size, denoted as N.

Optimal Solution

Approach

The goal is to pair numbers from a list so that the sum of each pair is evenly divisible by a given number. We can avoid checking every possible pair by focusing on how each number behaves when divided by the given number, and pairing remainders.

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

First, for each number in the list, find its remainder when divided by the given number. This remainder is the key to finding a suitable partner.
Next, keep track of how many times each remainder appears in the list of numbers. For instance, how many numbers have a remainder of 0, 1, 2, and so on.
Now, examine the counts of each remainder and its 'complement' (the number that, when added to the remainder, results in the given number). For example, if the given number is 5, and we have a remainder of 2, its complement is 3.
If the count of a remainder and its complement are not equal, we can't form pairs where the sum is divisible by the given number, and we can stop right away.
A special case exists when the remainder is zero or exactly half the given number. If the count for these remainders is not an even number, we cannot form valid pairs.
If all remainders satisfy the above conditions, then every number can be paired with another so their sum is divisible by the given number.

Code Implementation

def check_if_array_pairs_are_divisible_by_k(numbers, divisor):
    remainder_counts = {}
    for number in numbers:
        remainder = number % divisor
        if remainder not in remainder_counts:
            remainder_counts[remainder] = 0
        remainder_counts[remainder] += 1

    # Iterate through the remainders to find their complements.
    for remainder, count in remainder_counts.items():
        complement = (divisor - remainder) % divisor

        # Need to treat remainder 0 and k/2 as special cases.
        if remainder == 0 or remainder == divisor / 2:
            if count % 2 != 0:
                return False

        # If remainder and complement counts do not match, it is impossible to pair
        elif remainder_counts.get(complement, 0) != count:
            return False

    return True

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the input array nums of size n once to calculate the remainders (nums[i] % k) and store the counts of each remainder in a hash map. Subsequently, it iterates through the distinct remainders (at most k), comparing the count of each remainder r with the count of its complement (k - r). Each of these operations takes constant time. Since the loop for calculating remainders is proportional to the size of the array, the overall time complexity is O(n), while iterating through the distinct remainders is bound by k, which can be considered a constant if k is significantly smaller than n or unrelated to n.

Space Complexity

O(k) – The solution uses a dictionary (or hash map) to keep track of the counts of each remainder when dividing by k. In the worst case, if all numbers have distinct remainders from 0 to k-1, the dictionary will store k key-value pairs. Therefore, the space used by the dictionary grows linearly with k. Thus, the auxiliary space complexity is O(k).

Edge Cases

Case	How to Handle
Null or empty input array	Return true if the array is null or empty, as it trivially satisfies the condition (no pairs to check).
Array with an odd number of elements	Return false if the array has an odd number of elements, as it is impossible to form pairs.
k is zero	Throw an IllegalArgumentException or return false, as division by zero is undefined and no sum can be divisible by zero.
Array with all elements equal to 0 and k != 0	Return true if all elements are 0, since the sum of any pair will be 0, which is divisible by any non-zero k.
Array with mixed positive and negative numbers	Ensure the modulo operation handles negative numbers correctly (e.g., by adding k until the result is non-negative) when calculating remainders.
Large input array with potential integer overflow when summing pairs	The problem specifies sums divisible by k, not the sum itself needing to be stored, so overflow is less of a concern, and using long to store sums temporarily mitigates risks.
Array contains duplicate values that are modular inverses of each other	The hashmap stores counts of each remainder and ensures there are enough pairs of each modular inverse.
k is a large prime number and the array contains large numbers	The modulo operation mitigates issues of large numbers and prime k values, as we are concerned with remainders, not the large number itself.

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 integers, zero, or only positive integers?
If the array cannot be divided into pairs whose sum is divisible by `k`, what should I return?
Are duplicate numbers allowed in the input array `nums`?
Do I need to handle the case where the input array `nums` is empty or null?

Brute Force Solution

Approach

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

Take the first number in the list.
Pair it with every other number in the list, one at a time.
For each of these pairs, add the two numbers together.
Check if that sum can be divided evenly by the given number (meaning there's no remainder).
If it can't be divided evenly, that pair doesn't work.
Once you've paired the first number with every other number, move on to the second number.
Repeat the process of pairing it with every remaining number in the list (avoiding duplicates).
Keep doing this until you've considered all possible pairs from the list.
If, at any point, you find a pair that doesn't add up to a multiple of the given number, you know it's impossible to make the pairs work.
If you go through every single possible pair and they all add up to a multiple of the given number, then you've found a successful arrangement.

Code Implementation

def check_if_array_pairs_are_divisible_by_k_brute_force(
    numbers, divisor
):    # Iterate through all possible pairs in the list
    for first_index in range(len(numbers)):
        for second_index in range(first_index + 1, len(numbers)):            # Calculate the sum of the current pair
            current_sum = numbers[first_index] + numbers[second_index]

            # If the sum is not divisible, it's impossible
            if current_sum % divisor != 0:
                return False

    # All pairs are divisible by k
    return True

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 list, find its remainder when divided by the given number. This remainder is the key to finding a suitable partner.
Next, keep track of how many times each remainder appears in the list of numbers. For instance, how many numbers have a remainder of 0, 1, 2, and so on.
Now, examine the counts of each remainder and its 'complement' (the number that, when added to the remainder, results in the given number). For example, if the given number is 5, and we have a remainder of 2, its complement is 3.
If the count of a remainder and its complement are not equal, we can't form pairs where the sum is divisible by the given number, and we can stop right away.
A special case exists when the remainder is zero or exactly half the given number. If the count for these remainders is not an even number, we cannot form valid pairs.
If all remainders satisfy the above conditions, then every number can be paired with another so their sum is divisible by the given number.

Code Implementation

def check_if_array_pairs_are_divisible_by_k(numbers, divisor):
    remainder_counts = {}
    for number in numbers:
        remainder = number % divisor
        if remainder not in remainder_counts:
            remainder_counts[remainder] = 0
        remainder_counts[remainder] += 1

    # Iterate through the remainders to find their complements.
    for remainder, count in remainder_counts.items():
        complement = (divisor - remainder) % divisor

        # Need to treat remainder 0 and k/2 as special cases.
        if remainder == 0 or remainder == divisor / 2:
            if count % 2 != 0:
                return False

        # If remainder and complement counts do not match, it is impossible to pair
        elif remainder_counts.get(complement, 0) != count:
            return False

    return True

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty input array	Return true if the array is null or empty, as it trivially satisfies the condition (no pairs to check).
Array with an odd number of elements	Return false if the array has an odd number of elements, as it is impossible to form pairs.
k is zero	Throw an IllegalArgumentException or return false, as division by zero is undefined and no sum can be divisible by zero.
Array with all elements equal to 0 and k != 0	Return true if all elements are 0, since the sum of any pair will be 0, which is divisible by any non-zero k.
Array with mixed positive and negative numbers	Ensure the modulo operation handles negative numbers correctly (e.g., by adding k until the result is non-negative) when calculating remainders.
Large input array with potential integer overflow when summing pairs	The problem specifies sums divisible by k, not the sum itself needing to be stored, so overflow is less of a concern, and using long to store sums temporarily mitigates risks.
Array contains duplicate values that are modular inverses of each other	The hashmap stores counts of each remainder and ensures there are enough pairs of each modular inverse.
k is a large prime number and the array contains large numbers	The modulo operation mitigates issues of large numbers and prime k values, as we are concerned with remainders, not the large number itself.