Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/1497.html

1497. Check If Array Pairs Are Divisible by k (Medium)

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.

Example 4:

Input: arr = [-10,10], k = 2
Output: true

Example 5:

Input: arr = [-1,1,-2,2,-3,3,-4,4], k = 3
Output: true

 

Constraints:

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

Related Topics:
Array, Math, Greedy

Solution 1.

Use a map to store the frequencies of remainders and check if each remainder satisfies the requirement.

  1. If there are odd number 0 remainders, return false
  2. For 1 <= i < k / 2, if m[i] != m[k - i], return false.

If k is an even number, we can return false if m[k / 2] % 2 != 0 but it’s not needed because if m[k / 2] is odd, one of the above conditions above must be false.

// OJ: https://leetcode.com/problems/check-if-array-pairs-are-divisible-by-k/
// Time: O(N + K)
// Space: O(K)
class Solution {
public:
    bool canArrange(vector<int>& A, int k) {
        unordered_map<int, int> m;
        for (int n : A) m[(n % k + k) % k]++;
        if (m[0] % 2) return false;
        for (int i = 1; i < k / 2; ++i) {
            if (m[i] != m[k - i]) return false;
        }
        return true;
    }
};

Solution 2.

// OJ: https://leetcode.com/problems/check-if-array-pairs-are-divisible-by-k/
// Time: O(N)
// Space: O(K)
class Solution {
public:
    bool canArrange(vector<int>& A, int k) {
        unordered_map<int, int> m;
        for (int &n : A) {
            n = (n % k + k) % k;
            m[n]++;
        }
        for (int n : A) {
            if ((n == 0 && m[n] % 2) || (n && m[n] != m[k - n])) return false;
        }
        return true;
    }
};
  • class Solution {
        public boolean canArrange(int[] arr, int k) {
            int length = arr.length;
            if (length % 2 != 0)
                return false;
            Map<Integer, Integer> map = new HashMap<Integer, Integer>();
            for (int num : arr) {
                int remainder = num % k;
                if (remainder < 0)
                    remainder += k;
                int count = map.getOrDefault(remainder, 0) + 1;
                map.put(remainder, count);
            }
            int count0 = map.getOrDefault(0, 0);
            if (count0 % 2 != 0)
                return false;
            if (k % 2 == 0) {
                int countHalf = map.getOrDefault(k / 2, 0);
                if (countHalf % 2 != 0)
                    return false;
            }
            int half = k / 2;
            for (int i = 1; i <= half; i++) {
                int count1 = map.getOrDefault(i, 0);
                int count2 = map.getOrDefault(k - i, 0);
                if (count1 != count2)
                    return false;
            }
            return true;
        }
    }
    
    ############
    
    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;
        }
    }
    
  • // OJ: https://leetcode.com/problems/check-if-array-pairs-are-divisible-by-k/
    // Time: O(N + K)
    // Space: O(K)
    class Solution {
    public:
        bool canArrange(vector<int>& A, int k) {
            unordered_map<int, int> m;
            for (int n : A) m[(n % k + k) % k]++;
            if (m[0] % 2) return false;
            for (int i = 1; i < k / 2; ++i) {
                if (m[i] != m[k - i]) return false;
            }
            return true;
        }
    };
    
  • class Solution:
        def canArrange(self, arr: List[int], k: int) -> bool:
            mod = [0] * k
            for v in arr:
                mod[v % k] += 1
            return all(mod[i] == mod[k - i] for i in range(1, k)) and mod[0] % 2 == 0
    
    
    
  • 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
    }
    

All Problems

All Solutions