Number of pairs from the first N natural numbers whose sum is divisible by K | Function to find the number of pairs from the set of natural numbers up to N whose sum is divisible by K ; Declaring a Hash to store count ; Storing the count of integers with a specific remainder in Hash array ; Check if K is even ; Count of pairs when both integers are divisible by K ; Count of pairs when one remainder is R and other remainder is K - R ; Count of pairs when both the remainders are K / 2 ; Count of pairs when both integers are divisible by K ; Count of pairs when one remainder is R and other remainder is K - R ; Driver code ; Print the count of pairs
function findPairCount ( N , K ) { var count = 0 ; var rem = Array . from ( { length : K } , ( _ , i ) => 0 ) ; rem [ 0 ] = parseInt ( N / K ) ; for ( i = 1 ; i < K ; i ++ ) rem [ i ] = parseInt ( ( N - i ) / K + 1 ) ; if ( K % 2 == 0 ) { count += parseInt ( ( rem [ 0 ] * ( rem [ 0 ] - 1 ) ) / 2 ) ; for ( i = 1 ; i < K / 2 ; i ++ ) count += rem [ i ] * rem [ K - i ] ; count += ( rem [ K / 2 ] * ( rem [ K / 2 ] - 1 ) ) / 2 ; } else { count += ( rem [ 0 ] * ( rem [ 0 ] - 1 ) ) / 2 ; for ( i = 1 ; i <= K / 2 ; i ++ ) count += rem [ i ] * rem [ K - i ] ; } return count ; } var N = 10 , K = 4 ; document . write ( findPairCount ( N , K ) ) ;