Check if an array can be divided into pairs whose sum is divisible by k | JAVA 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
import java . util . HashMap ; public class Divisiblepair { static boolean canPairs ( int ar [ ] , int k ) { if ( ar . length % 2 == 1 ) return false ; HashMap < Integer , Integer > hm = new HashMap < > ( ) ; for ( int i = 0 ; i < ar . length ; i ++ ) { int rem = ( ( ar [ i ] % k ) + k ) % k ; if ( ! hm . containsKey ( rem ) ) { hm . put ( rem , 0 ) ; } hm . put ( rem , hm . get ( rem ) + 1 ) ; } for ( int i = 0 ; i < ar . length ; i ++ ) { int rem = ( ( ar [ i ] % k ) + k ) % k ; if ( 2 * rem == k ) { if ( hm . get ( rem ) % 2 == 1 ) return false ; } else if ( rem == 0 ) { if ( hm . get ( rem ) % 2 == 1 ) return false ; } else { if ( hm . get ( k - rem ) != hm . get ( rem ) ) return false ; } } return true ; } public static void main ( String [ ] args ) { int arr [ ] = { 92 , 75 , 65 , 48 , 45 , 35 } ; int k = 10 ; boolean ans = canPairs ( arr , k ) ; if ( ans ) System . out . println ( " True " ) ; else System . out . println ( " False " ) ; } }