Given two integers N and K where N, K > 0, the task is to find the total number of pairs (a, b) where 1 ? a, b ? N such that a % b = K.
Examples:
Input: N = 4, K = 2
Output: 2
Only valid pairs are (2, 3) and (2, 4).Input: N = 11, K = 5
Output: 7
Naive approach: Run two loops from 1 to n and count all the pairs (i, j) where i % j = K. The time complexity of this approach will be O(n2).
Efficient approach: Initially total count = N – K because all the numbers from the range which are > K will give K as the remainder after dividing it. After that, for all i > K there are exactly (N – K) / i numbers which will give the remainder as K after getting divided by i.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;// Function to return the count// of required pairsint CountAllPairs(int N, int K){ int count = 0; if (N > K) { // Initial count count = N - K; for (int i = K + 1; i <= N; i++) count = count + ((N - K) / i); } return count;}// Driver codeint main(){ int N = 11, K = 5; cout << CountAllPairs(N, K); return 0;} |
Java
// Java implementation of the approachimport java.io.*;class GFG { // Function to return the count // of required pairs static int CountAllPairs(int N, int K) { int count = 0; if (N > K) { // Initial count count = N - K; for (int i = K + 1; i <= N; i++) count = count + ((N - K) / i); } return count; } // Driver code public static void main(String[] args) { int N = 11, K = 5; System.out.println(CountAllPairs(N, K)); }} |
Python3
# Python3 implementation of the approachimport math# Function to return the count # of required pairsdef CountAllPairs(N, K): count = 0 if( N > K): # Initial count count = N - K for i in range(K + 1, N + 1): count = count + ((N - K) // i) return count # Driver codeN = 11K = 5print(CountAllPairs(N, K)) |
C#
// C# implementation of the approachusing System;class GFG { // Function to return the count // of required pairs static int CountAllPairs(int N, int K) { int count = 0; if (N > K) { // Initial count count = N - K; for (int i = K + 1; i <= N; i++) count = count + ((N - K) / i); } return count; } // Driver code public static void Main() { int N = 11, K = 5; Console.WriteLine(CountAllPairs(N, K)); }} |
PHP
<?php// PHP implementation of the approach// Function to return the count // of required pairsfunction CountAllPairs($N, $K){ $count = 0; if( $N > $K){ // Initial count $count = $N - $K; for($i = $K+1; $i <= $N ; $i++) { $x = ((($N - $K) / $i)); $count = $count + (int)($x); } } return $count;} // Driver code $N = 11; $K = 5; echo(CountAllPairs($N, $K));?> |
Javascript
<script>// JavaScript implementation of the approach // Function to return the count // of required pairs function CountAllPairs( N, K) { let count = 0; if (N > K) { // Initial count count = N - K; for (let i = K + 1; i <= N; i++) count = count + parseInt((N - K) / i); } return count; } // Driver code let N = 11, K = 5; document.write(CountAllPairs(N, K)); //contributed by sravan (171fa07058) </script> |
7
Time Complexity: O(N – K), where N and K are the given inputs.
Auxiliary Space: O(1), no extra space is required, so it is a constant.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
