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
def findPairCount ( N , K ) : NEW_LINE INDENT count = 0 ; NEW_LINE rem = [ 0 ] * K ; NEW_LINE rem [ 0 ] = N // K ; NEW_LINE for i in range ( 1 , K ) : NEW_LINE INDENT rem [ i ] = ( N - i ) // K + 1 ; NEW_LINE DEDENT if ( K % 2 == 0 ) : NEW_LINE INDENT count += ( rem [ 0 ] * ( rem [ 0 ] - 1 ) ) // 2 ; NEW_LINE for i in range ( 1 , K // 2 ) : NEW_LINE INDENT count += rem [ i ] * rem [ K - i ] ; NEW_LINE DEDENT count += ( rem [ K // 2 ] * ( rem [ K // 2 ] - 1 ) ) // 2 ; NEW_LINE DEDENT else : NEW_LINE INDENT count += ( rem [ 0 ] * ( rem [ 0 ] - 1 ) ) // 2 ; NEW_LINE for i in rage ( 1 , K // 2 + 1 ) : NEW_LINE INDENT count += rem [ i ] * rem [ K - i ] ; NEW_LINE DEDENT DEDENT return count ; NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT N = 10 ; K = 4 ; NEW_LINE print ( findPairCount ( N , K ) ) ; NEW_LINE DEDENT