Given three integers a, b and N. Find the total number of distinct pairs which can be formed by selecting one integer from 1 to a and other from 1 to b, such that their sum is divisible by N.
Examples:
Input : a = 4, b = 4, N = 4 Output : 4 Input : a = 5, b = 13, N = 3 Output : 22
Basic Approach: For a pair to be divisible by N it must contain one number from range 1 to a and other from 1 to b.
So, for this iterate over integers from 1 to a and for each integer (i), b/N numbers are there whose sum with i will be divisible by N. Also if (i%N + b%N) >= N then 1 more pair exists whose sum is divisible by N.
For example took a = 7, b = 6 and N = 4:
Let's check for i = 3:
- b/N = 6/4 = 1 => there is one integer from 1 to b,
whose sum with 3 is divisible by 4 i.e.(3, 1). - Also i%N + b%N = 3%4 + 6%4 = 3+2 = 5 > 4,
means one more integer exists from 1 to b
whose sum with 3 is divisible by 4 i.e.(3, 5).
Below is the implementation of the above approach:
C++
// C++ implementation of above approach#include <bits/stdc++.h>using namespace std;// Function to find the distinct pairs from// 1-a & 1-b such that their sum is divisible by n.int findCountOfPairs(int a, int b, int n){ int ans = 0; // Iterate over 1 to a to find distinct pairs for (int i = 1; i <= a; i++) { // For each integer from 1 to a // b/n integers exists such that pair // sum is divisible by n ans += b / n; // If (i%n +b%n ) >= n one more pair is possible ans += (i % n + b % n) >= n ? 1 : 0; } // Return answer return ans;}// Driver codeint main(){ int a = 5, b = 13, n = 3; cout << findCountOfPairs(a, b, n); return 0;} |
Java
// Java program for the above approachclass GFG{// Function to find the distinct pairs from// 1-a & 1-b such that their sum is divisible by n.static int findCountOfPairs(int a, int b, int n){ int ans = 0; // Iterate over 1 to a to find distinct pairs for (int i = 1; i <= a; i++) { // For each integer from 1 to a // b/n integers exists such that pair // sum is divisible by n ans += b / n; // If (i%n +b%n ) >= n one more pair is possible ans += (i % n + b % n) >= n ? 1 : 0; } // Return answer return ans;}// Driver codepublic static void main(String[] args) { int a = 5, b = 13, n = 3; System.out.println(findCountOfPairs(a, b, n));}}// This code has been contributed by 29AjayKumar |
Python3
# Python implementation of above approach# Function to find the distinct pairs from# 1-a & 1-b such that their sum is divisible by n.def findCountOfPairs(a, b, n): ans = 0 for i in range(1, a + 1): # For each integer from 1 to a # b/n integers exists such that pair # / sum is divisible by n ans += b//n # If (i%n +b%n ) >= n one more pair is possible ans += 1 if (i % n + b % n) >= n else 0 return ans# Driver codea = 5; b = 13; n = 3print(findCountOfPairs(a, b, n))# This code is contributed by Shrikant13 |
C#
// C# program for the above approachusing System;class GFG{ // Function to find the distinct pairs from// 1-a & 1-b such that their sum is divisible by n.static int findCountOfPairs(int a, int b, int n){ int ans = 0; // Iterate over 1 to a to find distinct pairs for (int i = 1; i <= a; i++) { // For each integer from 1 to a // b/n integers exists such that pair // sum is divisible by n ans += b / n; // If (i%n +b%n ) >= n one more pair is possible ans += (i % n + b % n) >= n ? 1 : 0; } // Return answer return ans;}// Driver codestatic public void Main (){ int a = 5, b = 13, n = 3; Console.WriteLine(findCountOfPairs(a, b, n));}}// This code has been contributed by ajit. |
PHP
<?php// PHP implementation of above approach// Function to find the distinct pairs from// 1-a & 1-b such that their sum is divisible by n.function findCountOfPairs($a, $b, $n){ $ans = 0; // Iterate over 1 to a to find // distinct pairs for ($i = 1; $i <= $a; $i++) { // For each integer from 1 to a // b/n integers exists such that pair // sum is divisible by n $ans += (int)($b / $n); // If (i%n +b%n ) >= n one more // pair is possible $ans += (($i % $n ) + ($b % $n)) >= $n ? 1 : 0; } // Return answer return $ans;}// Driver code$a = 5;$b = 13;$n = 3;echo findCountOfPairs($a, $b, $n);// This code is contributed by akt_mit.?> |
Javascript
<script> // Javascript program for the above approach // Function to find the distinct pairs from // 1-a & 1-b such that their sum is divisible by n. function findCountOfPairs(a, b, n) { let ans = 0; // Iterate over 1 to a to find distinct pairs for (let i = 1; i <= a; i++) { // For each integer from 1 to a // b/n integers exists such that pair // sum is divisible by n ans += parseInt(b / n, 10); // If (i%n +b%n ) >= n one more pair is possible ans += (i % n + b % n) >= n ? 1 : 0; } // Return answer return ans; } let a = 5, b = 13, n = 3; document.write(findCountOfPairs(a, b, n)); // This code is contributed by mukesh07. </script> |
Output:
22
Time complexity: O(N)
Auxiliary Space: O(1)
Second Approach:- This Approach Is a little Tricky. Here we find how much pair for a multiple of N.
First:- Keep (a<b), if not then make using swap.
Second:- Start a for loop from the lowest multiple of N and go through the multiple.
- Now Smallest element ( a ) is greater than or equally current multiple then we add ((Current_Multiple) – 1) pair to the ans.
- Now a is smaller But b is greater than or equally current multiple than we add a to the ans.
- Now if a and b both smaller than we count the remaining pair for add a – (current_multiple – b ) + 1.
- Break The Loop.
Below is the implementation of the above logic.
C++
// C++ implementation of above approach#include <bits/stdc++.h>using namespace std;// Function to find the distinct pairs from// 1-a & 1-b such that their sum is divisible by n.int findCountOfPairs(int a, int b, int n){ if (a > b) { // if first element is bigger than swap swap(a, b); } int temp = 1, count = 0; // count is store the number of pair. for (int i = n; temp > 0; i += n) { // we use temp for breaking a loop. if (a >= i) { // count when a is greater. temp = i - 1; } else if (b >= i) { // Count when a is smaller but // b is greater temp = a; } else if (i > b) { // Count when a and b both are smaller temp = a - (i - b) + 1; } if (temp > 0) //breaking condition { // For storing The pair in count. count += temp; } } // return the number of pairs. return count;}// Driver codeint main(){ int a = 5, b = 13, n = 3; cout << findCountOfPairs(a, b, n); return 0;}// contribute by Vivek Javiya |
Java
// Java implementation of // the above approachclass GFG{ // Function to find the // distinct pairs from// 1-a & 1-b such that // their sum is divisible by n.public static int findCountOfPairs(int a, int b, int n){ if (a > b) { // if first element is // bigger than swap int temp = a; a = b; b = temp; } int temp = 1, count = 0; // count is store the // number of pair. for (int i = n; temp > 0; i += n) { // we use temp for // breaking a loop. if (a >= i) { // count when a // is greater. temp = i - 1; } else if (b >= i) { // Count when a is // smaller but // b is greater temp = a; } else if (i > b) { // Count when a and b // both are smaller temp = a - (i - b) + 1; } //breaking condition if (temp > 0) { // For storing The // pair in count. count += temp; } } // return the number // of pairs. return count;} // Driver codepublic static void main(String[] args) { int a = 5, b = 13, n = 3; System.out.print(findCountOfPairs(a, b, n));}}// This code is contributed by divyeshrabadiya07 |
Python3
# Python implementation of above approach# Function to find the distinct pairs from# 1-a & 1-b such that their sum is divisible by n.def findCountOfPairs(a, b, n): if(a > b): # if first element is bigger than swap a, b = b, a temp = 1 count = 0 # count is store the number of pair. i = n while(temp > 0): # we use temp for breaking a loop. if(a >= i): # count when a is greater. temp = i - 1 elif(b >= i): # Count when a is smaller but # b is greater temp = a elif(i > b): # Count when a and b both are smaller temp = a - (i - b) + 1 if(temp > 0): # breaking condition # For storing The pair in count. count += temp i += n # return the number of pairs. return count# Driver codea = 5b = 13n = 3print(findCountOfPairs(a, b, n))# This code is contributed by avanitrachhadiya2155 |
C#
// C# implementation of // the above approachusing System;class GFG{ // Function to find the // distinct pairs from // 1-a & 1-b such that // their sum is divisible by n. static int findCountOfPairs(int a, int b, int n) { if (a > b) { // if first element is // bigger than swap int temp1 = a; a = b; b = temp1; } int temp = 1, count = 0; // count is store the // number of pair. for (int i = n; temp > 0; i += n) { // we use temp for // breaking a loop. if (a >= i) { // count when a // is greater. temp = i - 1; } else if (b >= i) { // Count when a is // smaller but // b is greater temp = a; } else if (i > b) { // Count when a and b // both are smaller temp = a - (i - b) + 1; } // breaking condition if (temp > 0) { // For storing The // pair in count. count += temp; } } // return the number // of pairs. return count; } // Driver code static void Main() { int a = 5, b = 13, n = 3; Console.WriteLine(findCountOfPairs(a, b, n)); }}// This code is contributed by divyesh072019 |
Javascript
<script> // Javascript implementation of // the above approach // Function to find the // distinct pairs from // 1-a & 1-b such that // their sum is divisible by n. function findCountOfPairs(a, b, n) { if (a > b) { // if first element is // bigger than swap let temp1 = a; a = b; b = temp1; } let temp = 1, count = 0; // count is store the // number of pair. for (let i = n; temp > 0; i += n) { // we use temp for // breaking a loop. if (a >= i) { // count when a // is greater. temp = i - 1; } else if (b >= i) { // Count when a is // smaller but // b is greater temp = a; } else if (i > b) { // Count when a and b // both are smaller temp = a - (i - b) + 1; } // breaking condition if (temp > 0) { // For storing The // pair in count. count += temp; } } // return the number // of pairs. return count; } let a = 5, b = 13, n = 3; document.write(findCountOfPairs(a, b, n)); </script> |
Output :
22
Time Complexity: O(n)
Auxiliary Space: O(1)
Efficient Approach: For solving the problem efficiently break it into four-part and solve as:
- Each integer from range 1 to N*(a/N) will have exactly b/N integers from 1 to N*(b/N) whose sum is divisible by N.
- There exist a/N integers from range 1 to N*(a/N) which can form pairs with b%N integer ranging from N*(b/N) to b.
- There exist a%N integers from range N*(a/N) to a which can form pairs with b/N integer ranging from 1 to N*(b/N).
- There exists (a%N + b%N)/N integers from range N*(a/N) to a and from N*(b/N) to b which can form pair whose sum is divisible by N.
Below is the implementation of the above approach:
C++
// C++ implementation of above approach#include <bits/stdc++.h>using namespace std;// Function to find the distinct pairs from// 1-a & 1-b such that their sum is divisible by n.int findCountOfPairs(int a, int b, int n){ int ans = 0; // pairs from 1 to n*(a/n) and 1 to n*(b/n) ans += n * (a / n) * (b / n); // pairs from 1 to n*(a/n) and n*(b/n) to b ans += (a / n) * (b % n); // pairs from n*(a/n) to a and 1 to n*(b/n) ans += (a % n) * (b / n); // pairs from n*(a/n) to a and n*(b/n) to b ans += ((a % n) + (b % n)) / n; // Return answer return ans;}// Driver codeint main(){ int a = 5, b = 13, n = 3; cout << findCountOfPairs(a, b, n); return 0;} |
Java
// Java implementation of above approachimport java.io.*;class GFG { // Function to find the distinct pairs from// 1-a & 1-b such that their sum is divisible by n.static int findCountOfPairs(int a, int b, int n){ int ans = 0; // pairs from 1 to n*(a/n) and 1 to n*(b/n) ans += n * (a / n) * (b / n); // pairs from 1 to n*(a/n) and n*(b/n) to b ans += (a / n) * (b % n); // pairs from n*(a/n) to a and 1 to n*(b/n) ans += (a % n) * (b / n); // pairs from n*(a/n) to a and n*(b/n) to b ans += ((a % n) + (b % n)) / n; // Return answer return ans;}// Driver codepublic static void main (String[] args) { int a = 5, b = 13, n = 3; System.out.println (findCountOfPairs(a, b, n));}}// This code is contributed by ajit.. |
Python3
# Python 3 implementation of above approach# Function to find the distinct pairs from# 1-a & 1-b such that their sum is divisible by n.def findCountOfPairs(a, b, n): ans = 0 # pairs from 1 to n*(a/n) and 1 to n*(b/n) ans += n * int(a / n) * int(b / n) # pairs from 1 to n*(a/n) and n*(b/n) to b ans += int(a / n) * (b % n) # pairs from n*(a/n) to a and 1 to n*(b/n) ans += (a % n) * int(b / n) # pairs from n*(a/n) to a and n*(b/n) to b ans += int(((a % n) + (b % n)) / n); # Return answer return ans# Driver codeif __name__ == '__main__': a = 5 b = 13 n = 3 print(findCountOfPairs(a, b, n))# This code is contributed by# Surendra_Gangwar |
C#
// C# implementation of above approachusing System;class GFG{ // Function to find the distinct pairs from// 1-a & 1-b such that their sum is divisible by n.static int findCountOfPairs(int a, int b, int n){ int ans = 0; // pairs from 1 to n*(a/n) and 1 to n*(b/n) ans += n * (a / n) * (b / n); // pairs from 1 to n*(a/n) and n*(b/n) to b ans += (a / n) * (b % n); // pairs from n*(a/n) to a and 1 to n*(b/n) ans += (a % n) * (b / n); // pairs from n*(a/n) to a and n*(b/n) to b ans += ((a % n) + (b % n)) / n; // Return answer return ans;}// Driver code static public void Main (){ int a = 5, b = 13, n = 3; Console.WriteLine(findCountOfPairs(a, b, n));}}// This code is contributed by @Tushil |
PHP
<?php// PHP implementation of above approach// Function to find the distinct pairs from// 1-a & 1-b such that their sum is divisible by n.function findCountOfPairs($a, $b, $n){ $ans = 0; // pairs from 1 to n*(a/n) and 1 to n*(b/n) $ans += $n * (int)($a / $n) * (int)($b / $n); // pairs from 1 to n*(a/n) and n*(b/n) to b $ans += (int)($a / $n) * ($b % $n); // pairs from n*(a/n) to a and 1 to n*(b/n) $ans += ($a % $n) * (int)($b / $n); // pairs from n*(a/n) to a and n*(b/n) to b $ans += (($a % $n) + (int)($b % $n)) / $n; // Return answer return $ans;}// Driver code$a = 5;$b = 13;$n = 3;echo findCountOfPairs($a, $b, $n);// This code is contributed by ajit.?> |
Javascript
<script> // Javascript implementation of above approach // Function to find the distinct pairs from // 1-a & 1-b such that their sum is divisible by n. function findCountOfPairs(a, b, n) { let ans = 0; // pairs from 1 to n*(a/n) and 1 to n*(b/n) ans += n * parseInt(a / n, 10) * parseInt(b / n, 10) // pairs from 1 to n*(a/n) and n*(b/n) to b ans += parseInt(a / n, 10) * parseInt(b % n, 10); // pairs from n*(a/n) to a and 1 to n*(b/n) ans += parseInt(a % n, 10) * parseInt(b / n, 10); // pairs from n*(a/n) to a and n*(b/n) to b ans += parseInt(((a % n) + (b % n)) / n, 10); // Return answer return ans; } let a = 5, b = 13, n = 3; document.write(findCountOfPairs(a, b, n)); </script> |
Output:
22
Time Complexity: O(1)
Auxiliary Space: O(1)
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!
