Check if an array can be divided into pairs whose sum is divisible by k | Python3 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 remainde ; 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
from collections import defaultdict NEW_LINE def canPairs ( arr , n , k ) : NEW_LINE INDENT if ( n & 1 ) : NEW_LINE INDENT return 0 NEW_LINE DEDENT freq = defaultdict ( lambda : 0 ) NEW_LINE for i in range ( 0 , n ) : NEW_LINE INDENT freq [ ( ( arr [ i ] % k ) + k ) % k ] += 1 NEW_LINE DEDENT for i in range ( 0 , n ) : NEW_LINE INDENT rem = ( ( arr [ i ] % k ) + k ) % k NEW_LINE if ( 2 * rem == k ) : NEW_LINE INDENT if ( freq [ rem ] % 2 != 0 ) : NEW_LINE INDENT return 0 NEW_LINE DEDENT DEDENT elif ( rem == 0 ) : NEW_LINE INDENT if ( freq [ rem ] & 1 ) : NEW_LINE INDENT return 0 NEW_LINE DEDENT DEDENT elif ( freq [ rem ] != freq [ k - rem ] ) : NEW_LINE INDENT return 0 NEW_LINE DEDENT DEDENT return 1 NEW_LINE DEDENT arr = [ 92 , 75 , 65 , 48 , 45 , 35 ] NEW_LINE k = 10 NEW_LINE n = len ( arr ) NEW_LINE if ( canPairs ( arr , n , k ) ) : NEW_LINE INDENT print ( " True " ) NEW_LINE DEDENT else : NEW_LINE INDENT print ( " False " ) NEW_LINE DEDENT