All possible co-prime distinct element pairs within a range [L, R]
Given a range [L, R], the task is to find all possible co-prime pairs from the range such that an element doesn’t appear in more than a single pair.
Examples:
Input : L=1 ; R=6 Output : 3 The answer is 3 [(1, 2) (3, 4) (5, 6)], all these pairs have GCD 1. Input : L=2 ; R=4 Output : 1 The answer is 1 [(2, 3) or (3, 4)] as '3' can only be chosen for a single pair
Approach: The key observation of the problem is that the numbers with the difference of ‘1’ are always relatively prime to each other i.e. co-primes.
GCD of this pair is always ‘1’. So, the answer will be (R-L+1)/2 [ (total count of numbers in range) / 2 ]
- If R-L+1 is odd then there will be one element left which can not form a pair.
- If R-L+1 is even then all elements can form pairs.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach #include <bits/stdc++.h> using namespace std; // Function to count possible pairs void CountPair( int L, int R) { // total count of numbers in range int x = (R - L + 1); // Note that if 'x' is odd then // there will be '1' element left // which can't form a pair // printing count of pairs cout << x / 2 << "\n" ; } // Driver code int main() { int L, R; L = 1, R = 8; CountPair(L, R); return 0; } |
Java
// Java implementation of the approach import java.util.*; class solution { // Function to count possible pairs static void CountPair( int L, int R) { // total count of numbers in range int x = (R - L + 1 ); // Note that if 'x' is odd then // there will be '1' element left // which can't form a pair // printing count of pairs System.out.println(x / 2 + "\n" ); } // Driver code public static void main(String args[]) { int L, R; L = 1 ; R = 8 ; CountPair(L, R); } } //contributed by Arnab Kundu |
Python3
# Python3 implementation of # the approach # Function to count possible # pairs def CountPair(L,R): # total count of numbers # in range x = (R - L + 1 ) # Note that if 'x' is odd then # there will be '1' element left # which can't form a pair # printing count of pairs print (x / / 2 ) # Driver code if __name__ = = '__main__' : L,R = 1 , 8 CountPair(L,R) # This code is contributed by # Indrajit Sinha. |
C#
// C# implementation of the approach using System; class GFG { // Function to count possible pairs static void CountPair( int L, int R) { // total count of numbers in range int x = (R - L + 1); // Note that if 'x' is odd then // there will be '1' element left // which can't form a pair // printing count of pairs Console.WriteLine(x / 2 + "\n" ); } // Driver code public static void Main() { int L, R; L = 1; R = 8; CountPair(L, R); } } // This code is contributed // by inder_verma.. |
PHP
<?php // PHP implementation of the above approach // Function to count possible pairs function CountPair( $L , $R ) { // total count of numbers in range $x = ( $R - $L + 1); // Note that if 'x' is odd then // there will be '1' element left // which can't form a pair // printing count of pairs echo $x / 2, "\n" ; } // Driver code $L = 1; $R = 8; CountPair( $L , $R ); // This code is contributed by ANKITRAI1 ?> |
Javascript
<script> // Javascript implementation of the approach // Function to count possible pairs function CountPair(L, R) { // total count of numbers in range let x = (R - L + 1); // Note that if 'x' is odd then // there will be '1' element left // which can't form a pair // printing count of pairs document.write(x / 2 + "<br/>" ); } // driver code let L, R; L = 1; R = 8; CountPair(L, R); </script> |
Output
4
Time Complexity: O(1), since there is no loop or recursion.
Auxiliary Space: O(1), since no extra space has been taken.
Contact Us