Check if an array can be divided into pairs whose sum is divisible by k | A C ++ program to check if arr [ 0. . n - 1 ] can be divided in pairs such that every pair is divisible by k . ; Returns true if arr [ 0. . n - 1 ] can be divided into pairs with sum divisible by k . ; An odd length array cannot be divided into pairs ; Create a frequency array to count occurrences of all remainders when divided by k . ; Count occurrences of all remainders ; Traverse input array and use freq [ ] to decide if given array can be divided in pairs ; Remainder of current element ; If remainder with current element divides k into two halves . ; Then there must be even occurrences of such remainder ; If remainder is 0 , then there must be two elements with 0 remainder ; Then there must be even occurrences of such remainder ; Else number of occurrences of remainder must be equal to number of occurrences of k - remainder ; Driver code ; Function call
#include <bits/stdc++.h> NEW_LINE using namespace std ; bool canPairs ( int arr [ ] , int n , int k ) { if ( n & 1 ) return false ; unordered_map < int , int > freq ; for ( int i = 0 ; i < n ; i ++ ) freq [ ( ( arr [ i ] % k ) + k ) % k ] ++ ; for ( int i = 0 ; i < n ; i ++ ) { int rem = ( ( arr [ i ] % k ) + k ) % k ; if ( 2 * rem == k ) { if ( freq [ rem ] % 2 != 0 ) return false ; } else if ( rem == 0 ) { if ( freq [ rem ] & 1 ) return false ; } else if ( freq [ rem ] != freq [ k - rem ] ) return false ; } return true ; } int main ( ) { int arr [ ] = { 92 , 75 , 65 , 48 , 45 , 35 } ; int k = 10 ; int n = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; canPairs ( arr , n , k ) ? cout << " True " : cout << " False " ; return 0 ; }