We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Check If Array Pairs Are Divisible by k

Number: 1620

Difficulty: Medium

Paid? No

Companies: Amazon, Google, Microsoft, tcs

Problem Description

Given an array of integers arr of even length n and an integer k, determine if it is possible to divide the array into n / 2 pairs such that the sum of each pair is divisible by k.

Key Insights

  • Use the modulo operator to classify numbers by their remainder when divided by k.
  • For each number, the complementary remainder needed to form a valid pair is (k - remainder) mod k.
  • Special cases include:
    • Numbers with remainder 0 must appear in pairs (even count).
    • If k is even, numbers with remainder k/2 must also have an even count.
  • For any other remainder r, the frequency of r must equal the frequency of its complement (k - r).

Space and Time Complexity

Time Complexity: O(n + k) - We process n numbers and check conditions over at most k remainders. Space Complexity: O(k) - To store counts of remainders.

Solution

The solution counts the frequency of each remainder when the array elements are divided by k. For each number, we adjust the remainder if it is negative. The key idea is to ensure that the frequency of each remainder r equals the frequency of the remainder (k - r). Special attention is given to remainders 0 and k/2 (when k is even), as these values must occur in even numbers to form valid pairs. If all conditions hold, the array can be rearranged into valid pairs; otherwise, it cannot.

Code Solutions

def canArrange(arr, k):
    # Dictionary to store frequency of each remainder
    remainder_count = {}
    for num in arr:
        remainder = num % k
        # Adjust for negative numbers by adding k if needed
        if remainder < 0:
            remainder += k
        remainder_count[remainder] = remainder_count.get(remainder, 0) + 1

    # Special handling for numbers that are exactly divisible by k (remainder 0)
    if remainder_count.get(0, 0) % 2 != 0:
        return False

    # Check pairs for all other remainders
    for r in range(1, k):
        # For the exact half of k when k is even, the count must be even
        if r == k - r:
            if remainder_count.get(r, 0) % 2 != 0:
                return False
        else:
            if remainder_count.get(r, 0) != remainder_count.get(k - r, 0):
                return False
    return True

# Example usage:
print(canArrange([1,2,3,4,5,10,6,7,8,9], 5))  # Expected output: True
← Back to All Questions