Check if an array can be divided into pairs whose sum is divisible by k - GeeksforGeeks

Check if an array can be divided into pairs whose sum is divisible by k - GeeksforGeeks
Given an array of integers and a number k, write a function that returns true if given array can be divided into pairs such that sum of every pair is divisible by k.

Input: arr[] = {9, 7, 5, 3}, k = 6
Output: True
We can divide array into (9, 3) and (7, 5).
Sum of both of these pairs is a multiple of 6.

A Simple Solution is to iterate through every element arr[i]. Find if there is another not yet visited element that has remainder as (k – arr[i]%k). If there is no such element, return false. If a pair is found, then mark both elements as visited. Time complexity of this solution is O(n2 and it requires O(n) extra space.

An Efficient Solution is to use Hashing. O(N)

1) If length of  given array is odd, return false. An odd
   length array cannot be divided in pairs.
2) Traverse input array array and count occurrences of
   all remainders. 
      freq[arr[i] % k]++
3) Traverse input array again. 
   a) Find remainder of current element.
   b) If remainder divides k into two halves, then
      there must be even occurrences of it as it forms
      pair with itself only.
   c) Else, number of occurrences of current remainder 
      must be equal to number of occurrences of "k -
      current remainder".

// Returns true if arr[0..n-1] can be divided into pairs

// with sum divisible by k.

bool canPairs(int arr[], int n, int k)

{

    // An odd length array cannot be divided into pairs

    if (n & 1)

        return false;

 

    // Create a frequency array to count occurrences

    // of all remainders when divided by k.

    map<int, int> freq;

 

    // Count occurrences of all remainders

    for (int i = 0; i < n; i++)

        freq[arr[i] % k]++;

 

    // Traverse input array and use freq[] to decide

    // if given array can be divided in pairs

    for (int i = 0; i < n; i++)

    {

        // Remainder of current element

        int rem = arr[i] % k;

 

        // If remainder with current element divides

        // k into two halves.

        if  (2*rem == k)

        {

            // Then there must be even occurrences of

            // such remainder

            if (freq[rem] % 2 != 0)

                return false;

        }

 

        // Else number of occurrences of remainder

        // must be equal to number of occurrences of

        // k - remainder

        else if (freq[rem] != freq[k - rem])

            return false;

    }

    return true;

}

It seems you don't need to traverse whole array, that will do a bunch of duplicated computation. Only need to traverse the map, it will work too.
http://code.geeksforgeeks.org/6uWYyP
Read full article from Check if an array can be divided into pairs whose sum is divisible by k - GeeksforGeeks