Check if GCD of [L, R] can be made >1 by replacing pairs with their product at most K times
Given a range [L, R] and an integer K, the task is to check if it is possible to make the GCD of all integers in the given range more than 1 using at most K operations wherein each operation replace any two integers in the range with their product.
Examples:
Input: L = 1, R = 5, K = 3 .
Output: Yes
Explanation: All the integers in the given range are {1, 2, 3, 4, 5}. In first operation, replace the first two elements with their product. Hence, the remaining elements become {2, 3, 4, 5}. Similarly, {2, 3, 4, 5} => {2, 3, 20} => {2, 60}. Hence, in three operations the given range can be reduced to {2, 60} such that its GCD is greater than 1.Input: L = 1, R = 2, K = 0
Output: No
Approach: The given problem can be solved using a greedy approach. The idea is to find the most common prime factor among all the integers in the range so that other elements can be merged with them. It can be observed that the most common prime factor in all cases will be 2. Hence, the most optimal choice is to multiply all odd integers with their nearest even integer. Therefore, if the count of odd integers if more than K, it is possible otherwise not.
Below is the implementation of the above approach:
C++
// C++ program of the above approach #include <iostream> using namespace std; // Function to check if it is possible // to make GCD of all integers in the // given range more than 1 with the // help of at most K operations bool gcdGreaterThanOne( int L, int R, int K) { // Case where the range // has only one integer if (L == R) { if (L == 1) return false ; else return true ; } // Stores the count of // odd integers in [L, R] int odd = (R - L + 1) - (R / 2 - ((L - 1) / 2)); return (odd > K) ? false : true ; } // Driver function int main() { int L = 1; int R = 5; int K = 3; if (gcdGreaterThanOne(L, R, K)) cout << "Yes" ; else cout << "No" ; return 0; } |
Java
// Java program for the above approach import java.io.*; import java.lang.*; import java.util.*; class GFG { // Function to check if it is possible // to make GCD of all integers in the // given range more than 1 with the // help of at most K operations static Boolean gcdGreaterThanOne( int L, int R, int K) { // Case where the range // has only one integer if (L == R) { if (L == 1 ) return false ; else return true ; } // Stores the count of // odd integers in [L, R] int odd = (R - L + 1 ) - (R / 2 - ((L - 1 ) / 2 )); return (odd > K) ? false : true ; } // Driver function public static void main (String[] args) { int L = 1 ; int R = 5 ; int K = 3 ; if (gcdGreaterThanOne(L, R, K)) System.out.println( "Yes" ); else System.out.println( "No" ); } } // This code is contributed by hrithikgarg03188. |
Python3
# Function to check if it is possible # to make GCD of all integers in the # given range more than 1 with the # help of at most K operations def gcdGreaterThanOne(L, R, K): # Case where the range # has only one integer if (L = = R): if (L = = 1 ): return false else : return true # Stores the count of # odd integers in [L, R] odd = (R - L + 1 ) - (R / 2 - ((L - 1 ) / 2 )) return (odd < = K) # Driver function L = 1 R = 5 K = 3 if (gcdGreaterThanOne(L, R, K)): print ( "Yes" ) else : print ( "No" ) # This code is contributed by khatriharsh281 |
C#
// C# implementation for the above approach using System; class GFG{ // Function to check if it is possible // to make GCD of all integers in the // given range more than 1 with the // help of at most K operations static Boolean gcdGreaterThanOne( int L, int R, int K) { // Case where the range // has only one integer if (L == R) { if (L == 1) return false ; else return true ; } // Stores the count of // odd integers in [L, R] int odd = (R - L + 1) - (R / 2 - ((L - 1) / 2)); return (odd > K) ? false : true ; } // Driver code static public void Main (){ int L = 1; int R = 5; int K = 3; if (gcdGreaterThanOne(L, R, K)) Console.Write( "Yes" ); else Console.Write( "No" ); } } // This code is contributed by sanjoy_62. |
Javascript
<script> // JavaScript code for the above approach // Function to check if it is possible // to make GCD of all integers in the // given range more than 1 with the // help of at most K operations function gcdGreaterThanOne(L, R, K) { // Case where the range // has only one integer if (L == R) { if (L == 1) return false ; else return true ; } // Stores the count of // odd integers in [L, R] let odd = (R - L + 1) - (R / 2 - ((L - 1) / 2)); return (odd > K) ? false : true ; } // Driver function let L = 1; let R = 5; let K = 3; if (gcdGreaterThanOne(L, R, K)) document.write( "Yes" ); else document.write( "No" ); // This code is contributed by Potta Lokesh </script> |
Yes
Time Complexity: O(1)
Auxiliary Space: O(1)