Problem: Given an array having even number of integers.
Find if the array has N / 2 pairs of integers such that each pair is divisible by a given number k.

Example: A normal approach would be to try all the pairs possible and see if the array holds the above property.
However, that would be a very costly approach in terms of efficiency and an O(n) solution is possible for this problem.

Code:

public class CheckPairDivisibility
{
public static void main(String[] args)
{
boolean isPairs = checkPairs (new int []{12, 30, 20, 22}, 6);
System.out.println(isPairs);
}
static boolean checkPairs(int nums[], int k)
{
// Debug prints
System.out.println("k = " + k);
printArray (nums, "input ");
// initialize counts of modulus
int modulusCounts[] = new int[k];
for(int i = 0; i < k; i++)
modulusCounts[i] = 0;
// For each number in the array, calculate
// modulus and update relevant count
for (int num: nums)
modulusCounts[num %k]++;
if (modulusCounts[0] % 2 != 0) // As these will not form pair with anyone else
return false;
if (k % 2 == 0) {
if (modulusCounts[k/2] %2 != 0) // These will also not form pair with anyone else
return false;
}
printArray (modulusCounts, "modulus");
for (int i = 1; i <= k/2; i++)
if (modulusCounts[i] != modulusCounts[k-i])
return false;
return true;
}
static void printArray (int arr[], String msg)
{
System.out.print (msg+": ");
for (int i : arr)
System.out.print (i + ", ");
System.out.println();
}
}