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:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;// Function to find the number of pairs// from the set of natural numbers up to// N whose sum is divisible by Kint findPairCount(int N, int K){ int count = 0; for(int i=1;i<=N;i++) { for(int j=i+1;j<=N;j++) { if((i+j)%K==0) { count++; } } } return count;}// Driver codeint main(){ int N = 10, K = 4; // Print the count of pairs cout << findPairCount(N, K); return 0;} |
Java
public class Main { // Function to find the number of pairs // from the set of natural numbers up to // N whose sum is divisible by K public static int findPairCount(int N, int K) { int count = 0; for (int i = 1; i <= N; i++) { for (int j = i + 1; j <= N; j++) { if ((i + j) % K == 0) { count++; } } } return count; } // Driver code public static void main(String[] args) { int N = 10, K = 4; // Print the count of pairs System.out.println(findPairCount(N, K)); }}// This code is contributed by Prajwal Kandekar |
Python3
# Function to find the number of pairs# from the set of natural numbers up to# N whose sum is divisible by Kdef find_pair_count(N: int, K: int) -> int: count = 0 for i in range(1, N): for j in range(i+1, N+1): if (i+j) % K == 0: count += 1 return count# Driver codeN = 10K = 4# Print the count of pairsprint(find_pair_count(N, K)) |
C#
using System;class Program { // Function to find the number of pairs // from the set of natural numbers up to // N whose sum is divisible by K static int FindPairCount(int N, int K) { int count = 0; for (int i = 1; i <= N; i++) { for (int j = i + 1; j <= N; j++) { if ((i + j) % K == 0) { count++; } } } return count; } // Driver code static void Main(string[] args) { int N = 10, K = 4; // Print the count of pairs Console.WriteLine(FindPairCount(N, K)); }}// This code is contributed by sarojmcy2e |
Javascript
// JavaScript 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 Kfunction findPairCount(N, K) { let count = 0; for (let i = 1; i <= N; i++) { for (let j = i + 1; j <= N; j++) { if ((i + j) % K === 0) { count++; } } } return count;}// Driver codeconst N = 10,K = 4;// Print the count of pairsconsole.log(findPairCount(N, K)); |
Output
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.
- Start a for loop and traverse from 1 to K/2-1.
- 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:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;// Function to find the number of pairs// from the set of natural numbers up to// N whose sum is divisible by Kint findPairCount(int N, int K){ int count = 0; // Declaring a Hash to store count int rem[K]; rem[0] = N / K; // Storing the count of integers with // a specific remainder in Hash array for (int i = 1; i < K; i++) rem[i] = (N - i) / K + 1; // Check if K is even if (K % 2 == 0) { // Count of pairs when both // integers are divisible by K count += (rem[0] * (rem[0] - 1)) / 2; // Count of pairs when one remainder // is R and other remainder is K - R for (int i = 1; i < K / 2; i++) count += rem[i] * rem[K - i]; // Count of pairs when both the // remainders are K / 2 count += (rem[K / 2] * (rem[K / 2] - 1)) / 2; } else { // Count of pairs when both // integers are divisible by K count += (rem[0] * (rem[0] - 1)) / 2; // Count of pairs when one remainder is R // and other remainder is K - R for (int i = 1; i <= K / 2; i++) count += rem[i] * rem[K - i]; } return count;}// Driver codeint main(){ int N = 10, K = 4; // Print the count of pairs cout << findPairCount(N, K); return 0;} |
Java
// Java implementation of the approach class GfG{ // Function to find the number of pairs // from the set of natural numbers up to // N whose sum is divisible by K static int findPairCount(int N, int K) { int count = 0; // Declaring a Hash to store count int rem[] = new int[K]; rem[0] = N / K; // Storing the count of integers with // a specific remainder in Hash array for (int i = 1; i < K; i++) rem[i] = (N - i) / K + 1; // Check if K is even if (K % 2 == 0) { // Count of pairs when both // integers are divisible by K count += (rem[0] * (rem[0] - 1)) / 2; // Count of pairs when one remainder // is R and other remainder is K - R for (int i = 1; i < K / 2; i++) count += rem[i] * rem[K - i]; // Count of pairs when both the // remainders are K / 2 count += (rem[K / 2] * (rem[K / 2] - 1)) / 2; } else { // Count of pairs when both // integers are divisible by K count += (rem[0] * (rem[0] - 1)) / 2; // Count of pairs when one remainder is R // and other remainder is K - R for (int i = 1; i <= K / 2; i++) count += rem[i] * rem[K - i]; } return count; } // Driver code public static void main(String[] args) { int N = 10, K = 4; // Print the count of pairs System.out.println(findPairCount(N, K)); }} // This code is contributed by Prerna Saini |
Python3
# Python3 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 def findPairCount(N, K) : count = 0; # Declaring a Hash to store count rem = [0] * K; rem[0] = N // K; # Storing the count of integers with # a specific remainder in Hash array for i in range(1, K) : rem[i] = (N - i) // K + 1; # Check if K is even if (K % 2 == 0) : # Count of pairs when both # integers are divisible by K count += (rem[0] * (rem[0] - 1)) // 2; # Count of pairs when one remainder # is R and other remainder is K - R for i in range(1, K // 2) : count += rem[i] * rem[K - i]; # Count of pairs when both the # remainders are K / 2 count += (rem[K // 2] * (rem[K // 2] - 1)) // 2; else : # Count of pairs when both # integers are divisible by K count += (rem[0] * (rem[0] - 1)) // 2; # Count of pairs when one remainder is R # and other remainder is K - R for i in range(1, K//2 + 1) : count += rem[i] * rem[K - i]; return count; # Driver code if __name__ == "__main__" : N = 10 ; K = 4; # Print the count of pairs print(findPairCount(N, K)); # This code is contributed by Ryuga |
C#
// C# implementation of the approach class GfG{ // Function to find the number of pairs // from the set of natural numbers up to // N whose sum is divisible by K static int findPairCount(int N, int K) { int count = 0; // Declaring a Hash to store count int[] rem = new int[K]; rem[0] = N / K; // Storing the count of integers with // a specific remainder in Hash array for (int i = 1; i < K; i++) rem[i] = (N - i) / K + 1; // Check if K is even if (K % 2 == 0) { // Count of pairs when both // integers are divisible by K count += (rem[0] * (rem[0] - 1)) / 2; // Count of pairs when one remainder // is R and other remainder is K - R for (int i = 1; i < K / 2; i++) count += rem[i] * rem[K - i]; // Count of pairs when both the // remainders are K / 2 count += (rem[K / 2] * (rem[K / 2] - 1)) / 2; } else { // Count of pairs when both // integers are divisible by K count += (rem[0] * (rem[0] - 1)) / 2; // Count of pairs when one remainder is R // and other remainder is K - R for (int i = 1; i <= K / 2; i++) count += rem[i] * rem[K - i]; } return count; } // Driver code static void Main() { int N = 10, K = 4; // Print the count of pairs System.Console.WriteLine(findPairCount(N, K)); }} // This code is contributed by mits |
PHP
<?php// PHP 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 Kfunction findPairCount($N, $K){ $count = 0; // Declaring a Hash to store count $rem = array(0, $K, NULL); $rem[0] = intval($N / $K); // Storing the count of integers with // a specific remainder in Hash array for ($i = 1; $i < $K; $i++) $rem[$i] = intval(($N - $i) / $K ) + 1; // Check if K is even if ($K % 2 == 0) { // Count of pairs when both // integers are divisible by K $count += ($rem[0] * intval(($rem[0] - 1)) / 2); // Count of pairs when one remainder // is R and other remainder is K - R for ($i = 1; $i < intval($K / 2); $i++) $count += $rem[$i] * $rem[$K - $i]; // Count of pairs when both the // remainders are K / 2 $count += ($rem[intval($K / 2)] * intval(($rem[intval($K / 2)] - 1)) / 2); } else { // Count of pairs when both // integers are divisible by K $count += ($rem[0] * intval(($rem[0] - 1)) / 2); // Count of pairs when one remainder is R // and other remainder is K - R for ($i = 1; $i <= intval($K / 2); $i++) $count += $rem[$i] * $rem[$K - $i]; } return $count;}// Driver code$N = 10;$K = 4;// Print the count of pairsecho findPairCount($N, $K);// This code is contributed by ita_c?> |
Javascript
<script>// javascript 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 function findPairCount(N , K) { var count = 0; // Declaring a Hash to store count var rem = Array.from({length: K}, (_, i) => 0); rem[0] = parseInt(N / K); // Storing the count of integers with // a specific remainder in Hash array for (i = 1; i < K; i++) rem[i] = parseInt((N - i) / K + 1); // Check if K is even if (K % 2 == 0) { // Count of pairs when both // integers are divisible by K count += parseInt((rem[0] * (rem[0] - 1)) / 2); // Count of pairs when one remainder // is R and other remainder is K - R for (i = 1; i < K / 2; i++) count += rem[i] * rem[K - i]; // Count of pairs when both the // remainders are K / 2 count += (rem[K / 2] * (rem[K / 2] - 1)) / 2; } else { // Count of pairs when both // integers are divisible by K count += (rem[0] * (rem[0] - 1)) / 2; // Count of pairs when one remainder is R // and other remainder is K - R for (i = 1; i <= K / 2; i++) count += rem[i] * rem[K - i]; } return count; } // Driver code var N = 10, K = 4; // Print the count of pairs document.write(findPairCount(N, K)); // This code is contributed by Princi Singh </script> |
Output
10
Time Complexity: O(K).
Auxiliary Space: O(K)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
