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
< ? php function findPairCount ( $ N , $ K ) { $ count = 0 ; $ rem = array ( 0 , $ K , NULL ) ; $ rem [ 0 ] = intval ( $ N / $ K ) ; for ( $ i = 1 ; $ i < $ K ; $ i ++ ) $ rem [ $ i ] = intval ( ( $ N - $ i ) / $ K ) + 1 ; if ( $ K % 2 == 0 ) { $ count += ( $ rem [ 0 ] * intval ( ( $ rem [ 0 ] - 1 ) ) / 2 ) ; for ( $ i = 1 ; $ i < intval ( $ K / 2 ) ; $ i ++ ) $ count += $ rem [ $ i ] * $ rem [ $ K - $ i ] ; $ count += ( $ rem [ intval ( $ K / 2 ) ] * intval ( ( $ rem [ intval ( $ K / 2 ) ] - 1 ) ) / 2 ) ; } else { $ count += ( $ rem [ 0 ] * intval ( ( $ rem [ 0 ] - 1 ) ) / 2 ) ; for ( $ i = 1 ; $ i <= intval ( $ K / 2 ) ; $ i ++ ) $ count += $ rem [ $ i ] * $ rem [ $ K - $ i ] ; } return $ count ; } $ N = 10 ; $ K = 4 ; echo findPairCount ( $ N , $ K ) ; ? >