Count of pairs of (i, j) such that ((n % i) % j) % n is maximized
Given an integer n, the task is to count the number of pairs (i, j) such that ((n % i) % j) % n is maximized where 1 ? i, j ? n
Examples:
Input: n = 5
Output: 3
(3, 3), (3, 4) and (3, 5) are the only valid pairs.
Input: n = 55
Output: 28
Naive Approach: To obtain the maximum remainder value, n has to be divided by (n / 2) + 1. Store max = n % ((n / 2) + 1), now check for all possible values of i and j. If ((n % i) % j) % n = max then update count = count + 1. Print the count in the end.
C++
// CPP implementation of the approach #include<bits/stdc++.h> using namespace std; // Function to return the count of required pairs int countPairs( int n) { // Number which will give the max value // for ((n % i) % j) % n int num = ((n / 2) + 1); // To store the maximum possible value of // ((n % i) % j) % n int max = n % num; // To store the count of possible pairs int count = 0; // Check all possible pairs for ( int i = 1; i <= n; i++) { for ( int j = 1; j <= n; j++) { // Calculating the value of ((n % i) % j) % n int val = ((n % i) % j) % n; // If value is equal to maximum if (val == max) count++; } } // Return the number of possible pairs return count; } // Driver code int main() { int n = 5; cout << (countPairs(n)); } // This code is contributed by // Surendra_Gangwar |
Java
// Java implementation of the approach class GFG { // Function to return the count of required pairs public static int countPairs( int n) { // Number which will give the max value // for ((n % i) % j) % n int num = ((n / 2 ) + 1 ); // To store the maximum possible value of // ((n % i) % j) % n int max = n % num; // To store the count of possible pairs int count = 0 ; // Check all possible pairs for ( int i = 1 ; i <= n; i++) { for ( int j = 1 ; j <= n; j++) { // Calculating the value of ((n % i) % j) % n int val = ((n % i) % j) % n; // If value is equal to maximum if (val == max) count++; } } // Return the number of possible pairs return count; } // Driver code public static void main(String[] args) { int n = 5 ; System.out.println(countPairs(n)); } } |
Python3
# Python3 implementation of the approach # Function to return the count of # required pairs def countPairs(n): # Number which will give the Max # value for ((n % i) % j) % n num = ((n / / 2 ) + 1 ) # To store the Maximum possible value # of ((n % i) % j) % n Max = n % num # To store the count of possible pairs count = 0 # Check all possible pairs for i in range ( 1 , n + 1 ): for j in range ( 1 , n + 1 ): # Calculating the value of # ((n % i) % j) % n val = ((n % i) % j) % n # If value is equal to Maximum if (val = = Max ): count + = 1 # Return the number of possible pairs return count # Driver code n = 5 print (countPairs(n)) # This code is contributed # by Mohit Kumar |
C#
// C# implementation of the above approach using System; class GFG { // Function to return the count of required pairs static int countPairs( int n) { // Number which will give the max // value for ((n % i) % j) % n int num = ((n / 2) + 1) ; // To store the maximum possible value // of ((n % i) % j) % n int max = n % num; // To store the count of possible pairs int count = 0; // Check all possible pairs for ( int i = 1; i <= n; i++) { for ( int j = 1; j <= n; j++) { // Calculating the value of // ((n % i) % j) % n int val = ((n % i) % j) % n; // If value is equal to maximum if (val == max) count++; } } // Return the number of possible pairs return count; } // Driver code public static void Main() { int n = 5; Console.WriteLine(countPairs(n)); } } // This code is contributed by Ryuga |
PHP
<?php // PHP implementation of the // approach Function to return // the count of required pairs function countPairs( $n ) { // Number which will give the max // value for ((n % i) % j) % n $num = (( $n / 2) + 1); // To store the maximum possible // value of ((n % i) % j) % n $max = $n % $num ; // To store the count of possible pairs $count = 0; // Check all possible pairs for ( $i = 1; $i <= $n ; $i ++) { for ( $j = 1; $j <= $n ; $j ++) { // Calculating the value // of ((n % i) % j) % n $val = (( $n % $i ) % $j ) % $n ; // If value is equal to maximum if ( $val == $max ) $count ++; } } // Return the number of possible pairs return $count ; } // Driver code $n = 5; echo (countPairs( $n )); // This code is contributed by ajit.. ?> |
Javascript
<script> // JavaScript implementation of the above approach // Function to return the count of required pairs function countPairs(n) { // Number which will give the max // value for ((n % i) % j) % n let num = (parseInt(n / 2, 10) + 1) ; // To store the maximum possible value // of ((n % i) % j) % n let max = n % num; // To store the count of possible pairs let count = 0; // Check all possible pairs for (let i = 1; i <= n; i++) { for (let j = 1; j <= n; j++) { // Calculating the value of // ((n % i) % j) % n let val = ((n % i) % j) % n; // If value is equal to maximum if (val == max) count++; } } // Return the number of possible pairs return count; } let n = 5; document.write(countPairs(n)); </script> |
3
Time Complexity: O(n2) since two nested loops are used the time taken by the algorithm to complete all operation is quadratic.
Auxiliary Space: O(1) since no extra array is used so the space taken by the algorithm is constant
Efficient Approach: Get the maximum value for remainder i.e. max = n % num where num = ((n / 2) + 1). Now i has to be chosen as num in order to obtain the maximum value and j can be chosen as any value from the range [max, n] because we don’t need to reduce the maximum value calculated and choosing j > max will not affect the previous value obtained. So the total pairs will be n – max.
This approach will not work for n = 2. This is because, for n = 2, maximum remainder will be 0 and n – max will give 2 but we know that the answer is 4. All possible pairs in this case are (1, 1), (1, 2), (2, 1) and (2, 2).
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 pairs int countPairs( int n) { // Special case if (n == 2) return 4; // Number which will give the max value // for ((n % i) % j) % n int num = ((n / 2) + 1); // To store the maximum possible value // of ((n % i) % j) % n int max = n % num; // Count of possible pairs int count = n - max; return count; } // Driver code int main() { int n = 5; cout << countPairs(n); } // This code is contributed by Code_Mech. |
Java
// Java implementation of the approach class GFG { // Function to return the count of required pairs public static int countPairs( int n) { // Special case if (n == 2 ) return 4 ; // Number which will give the max value // for ((n % i) % j) % n int num = ((n / 2 ) + 1 ); // To store the maximum possible value of // ((n % i) % j) % n int max = n % num; // Count of possible pairs int count = n - max; return count; } // Driver code public static void main(String[] args) { int n = 5 ; System.out.println(countPairs(n)); } } |
Python3
# Python3 implementation of the approach # Function to return the count of required pairs def countPairs(n): # Special case if (n = = 2 ): return 4 # Number which will give the max value # for ((n % i) % j) % n num = ((n / / 2 ) + 1 ); # To store the maximum possible value # of ((n % i) % j) % n max = n % num; # Count of possible pairs count = n - max ; return count # Driver code if __name__ = = "__main__" : n = 5 ; print (countPairs(n)); # This code is contributed by Code_Mech |
C#
// C# implementation of above approach using System; class GFG { // Function to return the count of required pairs static int countPairs( int n) { // Special case if (n == 2) return 4; // Number which will give the max value // for ((n % i) % j) % n int num = ((n / 2) + 1); // To store the maximum possible value of // ((n % i) % j) % n int max = n % num; // Count of possible pairs int count = n - max; return count; } // Driver code static public void Main () { int n = 5; Console.WriteLine(countPairs(n)); } } // This code is contributed by Tushil.. |
PHP
<?php // PHP implementation of the approach // Function to return the count // of required pairs function countPairs( $n ) { // Special case if ( $n == 2) return 4; // Number which will give the max // value. for ((n % i) % j) % n $num = ((int)( $n / 2) + 1); // To store the maximum possible // value of((n % i) % j) % n $max = $n % $num ; // Count of possible pairs $count = ( $n - $max ); return $count ; } // Driver code $n = 5; echo (countPairs( $n )); // This code is contributed by ajit ?> |
Javascript
<script> // Javascript implementation of the approach // Function to return the count of // required pairs function countPairs(n) { // Special case if (n == 2) return 4; // Number which will give the max value // for ((n % i) % j) % n let num = (parseInt(n / 2, 10) + 1); // To store the maximum possible value // of ((n % i) % j) % n let max = n % num; // Count of possible pairs let count = n - max; return count; } let n = 5; document.write(countPairs(n)); </script> |
3
Time Complexity: O(1) since no loop is used the algorithm takes up constant time to perform the operations
Auxiliary Space: O(1) since no extra array is used so the space taken by the algorithm is constant
Contact Us