Check if given Array can be grouped into N/2 pairs with equal sum

Given an array A[] of integers whose length is N, (where N is even) the task is to check if A[] can be grouped into N/2 pairs having equal sum.

Examples: 

Input: N = 6, A[] = {4, 5, 3, 1, 2, 6}
Output: True
Explanation: Consider the pairs {1, 6}, {5, 2} and {4, 3}. 
All 3 of them are having sum = 7. 
Hence, the given array can be divided into N/2 i.e. 3 pairs having equal sum.

Input : N = 8, A[] = {1, 1, 1, 1, 1, 1, 2, 3}
Output: False

Approach: The idea to solve the problem is by using two pointer approach following the below observation.

 If there exist N/2 pairs having equal sum, then the sum of each pair must be equal to min + max, where min is the minimum element of the array and max is the maximum element of the array.

Follow the steps mentioned below to solve the problem based on the above observation:

• Sort the given array.
• Initialize a variable (say target) equal to the sum of the first and the last element of the sorted array.
• Initialize two pointers pointing at the first and the last element.
  • Increment and decrement the pointers simultaneously and check if the sum of elements at the pointers is equal to target.
  • If so, continue iteration.
  • Else return false.
• After the iteration is complete return true.

Below is the implementation of the above approach.

Time Complexity: O(N * logN)
Auxiliary Space: O(1)