Given a range i.e. L and R, the task is to find if we can form pairs such that GCD of every pair is 1. Every number in the range L-R should be involved exactly in one pair.
Examples:
Input: L = 1, R = 8
Output: Yes
{2, 7}, {4, 1}, {3, 8}, {6, 5}
All pairs have GCD as 1.
Input: L = 2, R = 4
Output: No
Approach: Since every number in the range(L, R) must be included exactly once in every pair. Hence if L-R is an even number, then it is not possible. If L-R is an odd number, then print all the adjacent pairs since adjacent pairs will always have GCD as 1.
Below is the implementation of the above approach:
C++
// C++ program to print all pairs#include <bits/stdc++.h>using namespace std;// Function to print all pairsbool checkPairs(int l, int r){ // check if even if ((l - r) % 2 == 0) return false; /* We can print all adjacent pairs for (int i = l; i < r; i += 2) { cout << "{" << i << ", " << i + 1 << "}, "; } */ return true;}// Driver Codeint main(){ int l = 1, r = 8; if (checkPairs(l, r)) cout << "Yes"; else cout << "No"; return 0;} |
Java
// Java program to print all pairsclass GFG{// Function to print all pairsstatic boolean checkPairs(int l, int r){ // check if even if ((l - r) % 2 == 0) return false; /* We can print all adjacent pairs for (int i = l; i < r; i += 2) { System.out.print("{"+i+", "+i + 1+"}, "); } */ return true;}// Driver Codepublic static void main(String[] args){ int l = 1, r = 8; if (checkPairs(l, r)) System.out.println("Yes"); else System.out.println("No");}}// This code is contributed by mits |
Python 3
# Python 3 program to print all pairs # Function to print all pairs def checkPairs(l, r) : # check if even if (l - r) % 2 == 0 : return False """ we can print all adjacent pairs for i in range(l,r,2) : print("{",i,",",i + 1, "},") """ return True# Driver Codeif __name__ == "__main__" : l, r = 1, 8 if checkPairs(l, r) : print("Yes") else : print("No") # This code is contributed by ANKITRAI1 |
C#
// C# program to print all pairsusing System;class GFG{// Function to print all pairsstatic bool checkPairs(int l, int r){ // check if even if ((l - r) % 2 == 0) return false; /* We can print all adjacent pairs for (int i = l; i < r; i += 2) { System.out.print("{"+i+", "+i + 1+"}, "); } */ return true;}// Driver Codestatic public void Main (){ int l = 1, r = 8; if (checkPairs(l, r)) Console.Write("Yes"); else Console.Write("No");}}// This code is contributed by Raj |
Javascript
<script>// JavaScript program to print all pairs // Function to print all pairs function checkPairs(l , r) { // check if even if ((l - r) % 2 == 0) return false; /* We can print all adjacent pairs for (i = l; i < r; i += 2) { document.write("{"+i+", "+i + 1+"], "); } */ return true; } // Driver Code var l = 1, r = 8; if (checkPairs(l, r)) document.write("Yes"); else document.write("No");// This code is contributed by todaysgaurav</script> |
PHP
<?php// PHP program to print all pairs // Function to print all pairs function checkPairs($l, $r) { // check if even if (($l - $r) % 2 == 0) return false; /* We can print all adjacent pairs for (int i = l; i < r; i += 2) { cout << "{" << i << ", " << i + 1 << "}, "; } */ return true; } // Driver Code $l = 1;$r = 8; if (checkPairs($l, $r)) echo ("Yes"); else echo ("No"); // This code is contributed // by Shivi_Aggarwal?> |
Yes
Time Complexity: O(N)
Auxiliary Space: O(1)
Approach#2: Using sieve of eratosthenes
This approach uses the Sieve of Eratosthenes algorithm to generate a list of prime numbers up to the square root of the maximum number in the range. It then checks each pair of consecutive numbers in the range and determines whether they have a common factor other than 1, by iterating over the prime numbers and checking if they divide both numbers. If such a common factor exists, the function returns “No” indicating that there are no pairs with GCD equal to one. If no such common factor is found, the function returns “Yes” indicating that there exist pairs with GCD equal to one.
Algorithm
1. Generate a list of all primes up to sqrt(R).
2. Iterate over all numbers in the given range and check if they are coprime with all the primes up to sqrt(R).
3. If there exists at least one pair of coprime numbers, return “Yes”, else return “No”.
C++
#include <iostream>#include <vector>#include <cmath>using namespace std;// Function to implement the Sieve of Eratosthenes algorithmvector<bool> sieve_of_eratosthenes(int n) { // Create a boolean vector to mark numbers as prime or not vector<bool> primes(n + 1, true); primes[0] = primes[1] = false; // Iterate from 2 to the square root of n for (int i = 2; i <= sqrt(n); i++) { if (primes[i]) { // Mark all multiples of the current prime as not prime for (int j = i * i; j <= n; j += i) { primes[j] = false; } } } return primes;}// Function to check if there are pairs with GCD equal to 1 in the given range [l, r]string pairs_with_gcd_one(int l, int r) { // Generate a boolean vector of primes using the Sieve of Eratosthenes vector<bool> primes = sieve_of_eratosthenes(sqrt(r)); // Iterate through numbers in the range [l, r) for (int i = l; i < r; i++) { // Iterate through prime numbers in the range [2, sqrt(r)] for (int j = 2; j <= sqrt(r); j++) { // Check if j is prime if (primes[j]) { // If i and i+1 are both divisible by j, their GCD is not 1 if (i % j == 0 && (i + 1) % j == 0) { return "No"; } } } } return "Yes";}int main() { int l = 1; int r = 8; cout << pairs_with_gcd_one(l, r) << endl; return 0;} |
Java
// Java codeimport java.io.*;import java.util.Arrays;public class GCDPairs { // Function to implement the Sieve of Eratosthenes algorithm public static boolean[] sieveOfEratosthenes(int n) { // Create a boolean array to mark numbers as prime or not boolean[] primes = new boolean[n + 1]; Arrays.fill(primes, true); primes[0] = primes[1] = false; // Iterate from 2 to the square root of n for (int i = 2; i * i <= n; i++) { if (primes[i]) { // Mark all multiples of the current prime as not prime for (int j = i * i; j <= n; j += i) { primes[j] = false; } } } return primes; } // Function to check if there are pairs with GCD equal to 1 in the given range [l, r] public static String pairsWithGCDOne(int l, int r) { // Generate a boolean array of primes using the Sieve of Eratosthenes boolean[] primes = sieveOfEratosthenes((int) Math.sqrt(r)); // Iterate through numbers in the range [l, r) for (int i = l; i < r; i++) { // Iterate through prime numbers in the range [2, sqrt(r)] for (int j = 2; j <= Math.sqrt(r); j++) { // Check if j is prime if (primes[j]) { // If i and i+1 are both divisible by j, their GCD is not 1 if (i % j == 0 && (i + 1) % j == 0) { return "No"; } } } } return "Yes"; } public static void main(String[] args) { int l = 1; int r = 8; System.out.println(pairsWithGCDOne(l, r)); }} |
Python3
def sieve_of_eratosthenes(n): primes = [True] * (n+1) primes[0] = primes[1] = False for i in range(2, int(n**0.5)+1): if primes[i]: for j in range(i*i, n+1, i): primes[j] = False return primesdef pairs_with_gcd_one(l, r): primes = sieve_of_eratosthenes(int(r**0.5)) for i in range(l, r): for j in range(2, int(r**0.5)+1): if primes[j]: if i % j == 0 and (i+1) % j == 0: return "No" return "Yes"l=1r=8print(pairs_with_gcd_one(l, r)) |
Yes
Time complexity: O((r-l)*sqrt(r)), where r and l are the range boundaries, due to the nested loops over the range and the primes.
Auxiliary Space: O(sqrt(r)), since we store the list of primes up to the square root of r.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
