6Companies30days

Array Pairs

Given an array of integers arr of even length n and an integer k. We want to divide the array into exactly n / 2 pairs such that the sum of each pair is divisible by k. Return true If you can find a way to do that or false otherwise.

Example

Input: arr = [1,2,3,4,5,10,6,7,8,9], k = 5
Output: true
Explanation: Pairs are (1,9),(2,8),(3,7),(4,6) and (5,10).

Solution

Big Idea -

• 7k+3+7m+4 = 7(k+m) + 7
• Sum of two numbers are divisible by a number if sum of their modulos are divisible by the number
• In cpp extra care need to be taken for modulo of negative numbers

bool canArrange(vector<int>& arr, int k) {
        
        vector < vector <int> > modulos(k);
        
        for( int num : arr ){
            int temp = num%k;
            if(temp < 0 ) temp = k + temp; 
            if( temp >= 0 ) modulos[temp].push_back(num);
        }
        
        
        
        if( modulos[0].size()%2 != 0 ) return false;
        
        for( int num : arr ){
            int x = num%k;
            if(x < 0 ) x = k+x ;
            int comp = k - x;
            
            if( comp == k ) continue;
            
            if( comp > 0 and modulos[comp].size() == 0 ) return false;
            
            if(comp > 0 ) modulos[comp].pop_back();  
        }

     
    return true;
}