Number of pairs from the first N natural numbers whose sum is divisible by K

Given the integer values of N and K. The task is to find the number of pairs from the set of natural numbers up to N{1, 2, 3……N-1, N} whose sum is divisible by K. 
Note : 1 <= K <= N <= 10^6.
Examples: 

Input : N = 10, K = 5 
Output : 9 
Explanation : The possible pairs whose sum is divisible by 5 are (1, 4), (1, 9), (6, 4), (6, 9), (2, 3), (2, 8), (3, 7), (7, 8) and (5, 10). Hence the count is 9.
Input : N = 7, K = 3 
Output : 
Explanation : The possible pairs whose sum is divisible by 3 are (1, 2), (1, 5), (2, 4), (2, 7), (3, 6), (4, 5) and (5, 7). Hence the count is 7. 

Brute Force Approach: 

This is the naive approach. Here we go from 1 to N, and for each number, we check for a number in the range, on the addition of both, which gives a number divisible by k.

Steps that were to follow the above approach:

• Initialize a variable count to 0 to keep track of the number of pairs whose sum is divisible by K.
• Iterate over all pairs of numbers i and j from 1 to N such that i < j.
  • If (i+j) is divisible by K, increment the count.
• After iterating over all pairs, return the count as the result.

Below is the implementation of the above approach: 

10

Time Complexity: O(N^2)
Auxiliary Space: O(1)

Efficient Approach: An efficient approach is to use the basic Hashing technique.
Firstly, create array rem[K], where rem[i] contains the count of integers from 1 to N which gives the remainder i when divided by K. rem[i] can be calculated by the formula rem[i] = (N – i)/K + 1.
Secondly, the sum of two integers is divisible by K if: 
 

• Both the integers are divisible by K. The count of which is calculated by rem[0]*(rem[0]-1)/2.
• Remainder of first integer is R and remainder of other number is K-R. The count of which is calculated by rem[R]*rem[K-R], where R varies from 1 to K/2.
• K is even and both the remainders are K/2. The count of which is calculated by rem[K/2]*(rem[K/2]-1)/2.

The sum of counts of all these cases gives the required count of pairs such that their sum is divisible by K. 

Algorithm:

• Create a method named “findPairCount” with int return type which takes two integer values as input named “N” and “K”.
•  Create an in-variable named “count” and initialize it with 0.
• Create an array of integer types of K size.
•  Start a for loop and traverse from 1 to K-1.
  • Inside the loop, calculate the count of integers with the specific remainder i when divided by K and store it in rem[i].
•  Now check if K is even.
•  If K is even, calculate the count of pairs when both integers are divisible by K and add it to the “count” variable.
  • Start a for loop and traverse from 1 to K/2-1.
    •  Inside the loop, calculate the count of pairs when one integer has remainder i and the other integer has remainder K-i and add it to the “count” variable.
    •  Calculate the count of pairs when both integers have remainder K/2 and add it to the “count” variable.
•  if K is not even, calculate the count of pairs when both integers are divisible by K and add it to the “count” variable.
  •  Start a for loop and traverse from 1 to K/2.
  •  Inside the loop, calculate the count of pairs when one integer has remainder i and the other integer has remainder K-i and add it to the “count” variable.
• Not return the final value of the “count” variable.

Below is the implementation of the above approach: 
 

10

Time Complexity: O(K).
Auxiliary Space: O(K)