Data Structuresand Algorithms Good OldJava AdvancedInterview Topics Cloud andDatabases Web Designand Development Must-knowTools Good ToKnow

## Check pairs divisible by K

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 % 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();
}
}

```

Sample Execution:

```k = 6
input  : 12, 30, 20, 22,
modulus: 2, 0, 1, 0, 1, 0,
true

k = 7
input  : 12, 30, 20, 22,
modulus: 0, 1, 1, 0, 0, 1, 1,
true

k = 8
input  : 12, 30, 20, 22,
modulus: 0, 0, 0, 0, 2, 0, 2, 0,
false

```

Like us on Facebook to remain in touch
with the latest in technology and tutorials!

Got a thought to share or found a
bug in the code?
We'd love to hear from you:

 Name: Email: (Your email is not shared with anybody) Comment: