Count of pairs from first N natural numbers with remainder at least K
Given two positive integers N and K, the task is to find the number of pairs (a, b) over the range [1, N] such that a%b is at least K.
Examples:
Input: N = 5, K = 2
Output: 7
Explanation:
Following are the all possible pairs satisfying the given criteria:
- (2, 3): The value of 2%3 = 2(>= K).
- (5, 3): The value of 5%3 = 2(>= K).
- (2, 4): The value of 2%4 = 2(>= K).
- (3, 4): The value of 3%4 = 3(>= K).
- (2, 5): The value of 2%5 = 2(>= K).
- (3, 5): The value of 3%5 = 3(>= K).
- (4, 5): The value of 4%5 = 4(>= K).
Therefore, the total count of pairs is 7.
Input: N = 6, K = 0
Output: 36
Naive Approach: The simplest approach to solve the given problem is to generate all possible pairs (a, b) over the range [1, N] and if the value of a%b is at least K, then count this pair. After checking for all the pairs, print the total pairs obtained.
Time Complexity: O(N2)
Auxiliary Space: O(1)
Efficient Approach: The above approach can also be optimized by iterating over the range [1, N] and fix the second number in the pair, i.e., b. For each fixed b there will be a period of N/b and every period can be combined with (b ā K) elements. So, a total of (N/b)*(b ā K) elements will be there. Now for the remaining elements that are N%b there will be max(0, n%b ā k + 1) pairs. Follow the steps below to solve the problem:
- If the value of K is 0, then print N2 as the resultant number of valid pairs.
- Initialize the variable, say ans as 0 that stores the resultant count of pairs.
- Iterate over the range [K + 1, N] using the variable b and perform the following steps:
- Add the value of (N/b)*(b ā K) to the variable ans.
- Add the value of the maximum of (N % b ā K + 1) or 0 to the variable ans.
- After performing the above steps, print the value of ans as the resultant count of pairs.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to count the number of pairs // (a, b) such that a%b is at least K int countTotalPairs( int N, int K) { // Base Case if (K == 0) { return N * N; } // Stores resultant count of pairs int ans = 0; // Iterate over the range [K + 1, N] for ( int b = K + 1; b <= N; b++) { // Find the cycled elements ans += (N / b) * (b - K); // Find the remaining elements ans += max(N % b - K + 1, 0); } // Return the resultant possible // count of pairs return ans; } // Driver Code int main() { int N = 5, K = 2; cout << countTotalPairs(N, K); return 0; } |
Java
/*package whatever //do not write package name here */ import java.io.*; class GFG { // Function to count the number of pairs // (a, b) such that a%b is at least K public static int countTotalPairs( int N, int K) { // Base case if (K == 0 ) { return N * N; } // Stores resultant count of pairs int ans = 0 ; // Iterate over the range [K + 1, N] for ( int i = K + 1 ; i <= N; i++) { // Find the cycled element ans += (N / i) * (i - K); if ((N % i) - K + 1 > 0 ) { // Find the remaining element ans += (N % i) - K + 1 ; } } // Return the resultant possible // count of pairs return ans; } // Driver code public static void main(String[] args) { int N = 5 , K = 2 ; System.out.println(countTotalPairs(N, K)); } } // This code is contributed by maddler. |
Python3
# Python program for the above approach; # Function to count the number of pairs # (a, b) such that a%b is at least K def countTotalPairs(N, K): # Base Case if (K = = 0 ) : return N * N # Stores resultant count of pairs ans = 0 # Iterate over the range [K + 1, N] for b in range (K + 1 , N + 1 ) : # Find the cycled elements ans + = (N / / b) * (b - K) # Find the remaining elements ans + = max (N % b - K + 1 , 0 ) # Return the resultant possible # count of pairs return ans # Driver Code N = 5 K = 2 print (countTotalPairs(N, K)) # This code is contributed by _saurabh_jaiswal |
C#
// C# program for the above approach using System; using System.Collections.Generic; class GFG{ // Function to count the number of pairs // (a, b) such that a%b is at least K static int countTotalPairs( int N, int K) { // Base Case if (K == 0) { return N * N; } // Stores resultant count of pairs int ans = 0; // Iterate over the range [K + 1, N] for ( int b = K + 1; b <= N; b++) { // Find the cycled elements ans += (N / b) * (b - K); // Find the remaining elements ans += Math.Max(N % b - K + 1, 0); } // Return the resultant possible // count of pairs return ans; } // Driver Code public static void Main() { int N = 5, K = 2; Console.Write(countTotalPairs(N, K)); } } // This code is contributed by ipg2016107. |
Javascript
<script> // JavaScript program for the above approach; // Function to count the number of pairs // (a, b) such that a%b is at least K function countTotalPairs(N, K) { // Base Case if (K == 0) { return N * N; } // Stores resultant count of pairs let ans = 0; // Iterate over the range [K + 1, N] for (let b = K + 1; b <= N; b++) { // Find the cycled elements ans += Math.floor((N / b) * (b - K)); // Find the remaining elements ans += Math.max(N % b - K + 1, 0); } // Return the resultant possible // count of pairs return ans; } // Driver Code let N = 5, K = 2; document.write(countTotalPairs(N, K)); // This code is contributed by Potta Lokesh </script> |
7
Time Complexity: O(N)
Auxiliary Space: O(1)