Check If Array Pairs Are Divisible by k

Medium
1787.

Check If Array Pairs Are Divisible by k

Check If Array Pairs Are Divisible by k is a medium coding problem on arrays, hash table and counting, asked in Amazon and Google interviews.

You are given an integer array arr of even length n and an integer k.

You want to split arr into exactly n / 2 pairs, every element in exactly one pair, such that the sum of each pair is divisible by k.

Return true if such a split exists, and false otherwise.

Example 1

Input
arr = [-1,1,-2,2,3,7], k = 5
Output
true
Explanation
Pairs `(-1,1)`, `(-2,2)` and `(3,7)` sum to 0, 0 and 10, all divisible by 5.

Example 2

Input
arr = [4,4,4,6], k = 10
Output
false
Explanation
A 4 needs a partner leaving remainder 6, and there is only one 6 for three 4s.

Example 3

Input
arr = [5,5,5,5], k = 10
Output
true
Explanation
5 is exactly half of 10, so 5s pair with each other: `(5,5)` twice.

Constraints

  • arr.length == n
  • 1 <= n <= 10^5
  • n is even
  • -10^9 <= arr[i] <= 10^9
  • 1 <= k <= 10^5
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} arr
 * @param {number} k
 * @return {boolean}
 */
var canArrange = function(arr, k) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Check If Array Pairs Are Divisible by k — Problem & Solution

Check If Array Pairs Are Divisible by k solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Check If Array Pairs Are Divisible by k is a medium coding problem on arrays, hash table and counting, asked in Amazon and Google interviews.

  • Difficulty: Medium
  • Topics: Arrays, Hash Table, Counting
  • Asked at: Amazon, Google
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

You are given an integer array arr of even length n and an integer k.

You want to split arr into exactly n / 2 pairs, every element in exactly one pair, such that the sum of each pair is divisible by k.

Return true if such a split exists, and false otherwise.

Example 1

Input: arr = [-1,1,-2,2,3,7], k = 5
Output: true
Explanation: Pairs `(-1,1)`, `(-2,2)` and `(3,7)` sum to 0, 0 and 10, all divisible by 5.

Example 2

Input: arr = [4,4,4,6], k = 10
Output: false
Explanation: A 4 needs a partner leaving remainder 6, and there is only one 6 for three 4s.

Example 3

Input: arr = [5,5,5,5], k = 10
Output: true
Explanation: 5 is exactly half of 10, so 5s pair with each other: `(5,5)` twice.

Constraints

  • arr.length == n
  • 1 <= n <= 10^5
  • n is even
  • -10^9 <= arr[i] <= 10^9
  • 1 <= k <= 10^5

Hints for Check If Array Pairs Are Divisible by k

  1. Hint 1

    Whether a + b is divisible by k depends only on a mod k and b mod k.

  2. Hint 2

    An element with remainder r needs a partner with remainder k - r; remainder 0 needs another remainder 0.

  3. Hint 3

    Count elements per remainder (taking care with negative numbers) and compare count[r] with count[k - r].

How to solve Check If Array Pairs Are Divisible by k

Reduce every element to its non-negative remainder modulo k. Remainders r and k - r must be matched one to one, and the self-paired classes (0, and k / 2 when k is even) must each have an even size.

Approach

  1. Compute r = ((x % k) + k) % k for every element and count each remainder.
  2. If count[0] is odd, return false.
  3. For every other remainder r: if 2r == k, require count[r] to be even; otherwise require count[r] == count[k - r].
  4. Return true if every check passes.

Why it works

Two elements can pair only if their remainders add to 0 or k, so each class r can only pair with class k - r. When those classes are distinct, a perfect pairing exists exactly when their sizes match; when a class pairs with itself (r = 0 or r = k / 2), it needs an even size. These classes partition the array, so the conditions together are necessary and sufficient.

Complexity

  • Time — O(n)
  • Space — O(min(n, k))

Pitfalls

  • In most languages % of a negative number is negative: -1 % 5 is -1, so normalise with ((x % k) + k) % k.
  • Remainder k / 2 for even k pairs with itself — comparing count[r] with count[k - r] there is trivially true and misses an odd count.
  • With k = 1 every sum is divisible, and every remainder is 0.

Reference solution

Python

from typing import List
from collections import Counter

def canArrange(arr: List[int], k: int) -> bool:
    cnt = Counter(x % k for x in arr)
    for r, c in cnt.items():
        if r == 0 or 2 * r == k:
            if c % 2:
                return False
        elif cnt.get(k - r, 0) != c:
            return False
    return True

Java

public static boolean canArrange(int[] arr, int k) {
    Map<Integer, Integer> cnt = new HashMap<>();
    for (int x : arr) cnt.merge(((x % k) + k) % k, 1, Integer::sum);
    for (Map.Entry<Integer, Integer> e : cnt.entrySet()) {
        int r = e.getKey(), c = e.getValue();
        if (r == 0 || 2 * r == k) { if (c % 2 != 0) return false; }
        else if (cnt.getOrDefault(k - r, 0) != c) return false;
    }
    return true;
}

C++

bool canArrange(vector<int>& arr, int k) {
    unordered_map<int, int> cnt;
    for (int x : arr) cnt[((x % k) + k) % k]++;
    for (auto& e : cnt) {
        int r = e.first, c = e.second;
        if (r == 0 || 2 * r == k) { if (c % 2 != 0) return false; }
        else {
            auto it = cnt.find(k - r);
            if (it == cnt.end() || it->second != c) return false;
        }
    }
    return true;
}

JavaScript

var canArrange = function(arr, k) {
    var cnt = new Map();
    for (var i = 0; i < arr.length; i++) {
        var r = ((arr[i] % k) + k) % k;
        cnt.set(r, (cnt.get(r) || 0) + 1);
    }
    var ok = true;
    cnt.forEach(function(c, r) {
        if (r === 0 || 2 * r === k) { if (c % 2 !== 0) ok = false; }
        else if ((cnt.get(k - r) || 0) !== c) ok = false;
    });
    return ok;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets