Skip to content

1497. Check If Array Pairs Are Divisible by k

Description

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 <= 105
  • n is even.
  • -109 <= arr[i] <= 109
  • 1 <= k <= 105

Solutions

Solution 1: Counting Remainders

The sum of two numbers \(a\) and \(b\) is divisible by \(k\) if and only if the sum of their remainders when divided by \(k\) is divisible by \(k\).

Therefore, we can count the remainder of each number in the array when divided by \(k\), and record them in an array \(\textit{cnt}\). Then we traverse the array \(\textit{cnt}\). For each number \(i\) in the range \([1,..k-1]\), if the values of \(\textit{cnt}[i]\) and \(\textit{cnt}[k-i]\) are not equal, it means we cannot divide the numbers in the array into \(n/2\) pairs such that the sum of each pair is divisible by \(k\). Similarly, if the value of \(\textit{cnt}[0]\) is not even, it also means we cannot divide the numbers in the array into \(n/2\) pairs such that the sum of each pair is divisible by \(k\).

The time complexity is \(O(n)\), where \(n\) is the length of the array \(\textit{arr}\). The space complexity is \(O(k)\).

1
2
3
4
class Solution:
    def canArrange(self, arr: List[int], k: int) -> bool:
        cnt = Counter(x % k for x in arr)
        return cnt[0] % 2 == 0 and all(cnt[i] == cnt[k - i] for i in range(1, k))

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution {
    public boolean canArrange(int[] arr, int k) {
        int[] cnt = new int[k];
        for (int x : arr) {
            ++cnt[(x % k + k) % k];
        }
        for (int i = 1; i < k; ++i) {
            if (cnt[i] != cnt[k - i]) {
                return false;
            }
        }
        return cnt[0] % 2 == 0;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution {
public:
    bool canArrange(vector<int>& arr, int k) {
        vector<int> cnt(k);
        for (int& x : arr) {
            ++cnt[((x % k) + k) % k];
        }
        for (int i = 1; i < k; ++i) {
            if (cnt[i] != cnt[k - i]) {
                return false;
            }
        }
        return cnt[0] % 2 == 0;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
func canArrange(arr []int, k int) bool {
    cnt := make([]int, k)
    for _, x := range arr {
        cnt[(x%k+k)%k]++
    }
    for i := 1; i < k; i++ {
        if cnt[i] != cnt[k-i] {
            return false
        }
    }
    return cnt[0]%2 == 0
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
function canArrange(arr: number[], k: number): boolean {
    const cnt: number[] = Array(k).fill(0);
    for (const x of arr) {
        ++cnt[((x % k) + k) % k];
    }
    for (let i = 1; i < k; ++i) {
        if (cnt[i] !== cnt[k - i]) {
            return false;
        }
    }
    return cnt[0] % 2 === 0;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
impl Solution {
    pub fn can_arrange(arr: Vec<i32>, k: i32) -> bool {
        let k = k as usize;
        let mut cnt = vec![0; k];
        for &x in &arr {
            cnt[((x % k as i32 + k as i32) % k as i32) as usize] += 1;
        }
        for i in 1..k {
            if cnt[i] != cnt[k - i] {
                return false;
            }
        }
        cnt[0] % 2 == 0
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
/**
 * @param {number[]} arr
 * @param {number} k
 * @return {boolean}
 */
var canArrange = function (arr, k) {
    const cnt = Array(k).fill(0);
    for (const x of arr) {
        ++cnt[((x % k) + k) % k];
    }
    for (let i = 1; i < k; ++i) {
        if (cnt[i] !== cnt[k - i]) {
            return false;
        }
    }
    return cnt[0] % 2 === 0;
};

Comments