Number of pairs from the first N natural numbers whose sum is divisible by K | C ++ implementation of the approach ; 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; int findPairCount ( int N , int K ) { int count = 0 ; int rem [ K ] ; rem [ 0 ] = N / K ; for ( int i = 1 ; i < K ; i ++ ) rem [ i ] = ( N - i ) / K + 1 ; if ( K % 2 == 0 ) { count += ( rem [ 0 ] * ( rem [ 0 ] - 1 ) ) / 2 ; for ( int 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 ( int i = 1 ; i <= K / 2 ; i ++ ) count += rem [ i ] * rem [ K - i ] ; } return count ; } int main ( ) { int N = 10 , K = 4 ; cout << findPairCount ( N , K ) ; return 0 ; }