👉 “Offer to drive, dig friends to accept! I am participating in the 2022 Spring Recruit Punch card activity click to see the details of the activity.

Check if array pairs are divisible by k

You are given an integer array arr and an integer k, where the array length is even and the value is n. Now you need to split the array into exactly n / 2 pairs so that the sum of each pair of numbers is divisible by k. Return True if such a partition exists; Otherwise, return False.

Example 1: * * * * input: arr =,2,3,4,5,10,6,7,8,9 [1], k = 5 output: true explanation: after dividing Numbers for (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: divided pairs are (1,6),(2,5), and (3,4). ** example 3: ** input: arr = [1,2,3,4,5,6], k = 10 output: false description: the sum of each pair of digits cannot be divisible by 10 while splitting the array into three pairs. 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: trueCopy the code

Tip:

  • arr.length == n
  • 1 <= n <= 10^5
  • N is even
  • -10^9 <= arr[i] <= 10^9
  • 1 <= k <= 10^5
How to solve the problem: remainder classification
  • Number theory knowledge :(a+b)%k = (a%k+b%k)%k
  • Modulo of a negative number in C++ yields a negative number, and arrays cannot have negative subscripts, so map it to [0,k-1] by (a%k+k)%k
  • Count the number of occurrences of the remainder
  • Calculate whether CNT [I] and CNT [k-i] are equal in the remainder interval of [1, k-1], if not, return false
  • If the remainder of 0 is even, return false if it is not

Discuss why, sentenced to remainder of 0, because when k is even, I and k – I will be equal, right now you need to see the CNT [0] is even, the specific example is as follows: k = 6 arr =,2,3,4,5,6,7,8,9,10,11,15 [1] notice: CNT [3]== CNT [6-3] at this point, the for cycle has been completed. If CNT [0] is not specially judged, it is incorrect, because CNT [0] is an odd number at this point, and one of them must be unmatched. It can be considered that the unmatched element is 15

remainder 0 1 2 3 4 5
1 2 3 4 5
6 7 8 9 10 11
15 
class Solution {
public:
    bool canArrange(vector<int>& arr, int k) {
        vector<int> cnt(k,0);
        for(int a : arr){
            cnt[(a%k+k)%k]++;
        }
        for(int i = 1; i <= k/2; ++i){ // Notice that the subscript must start at 1, otherwise CNT [k-0] array is out of bounds
            if(cnt[i] ! = cnt[k-i])return false;
        }
        return cnt[0] %2= =0; }};Copy the code