Make delicious recipes!

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




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:

Facebook comments:

Site Owner: Sachin Goyal