Given three integers L, R, and K. Consider an array arr[] consisting of all the elements from L to R, the task is to check whether the GCD of the array can be made greater than 1 using at most K operations. An operation is defined below:
- Choose any two numbers from the array
- Remove them from the array
- Insert their product back into the array
Examples:
Input: L = 4, R = 10, K = 3
Output: true
Explanation: Array will be arr[] = {4, 5, 6, 7, 8, 9, 10}
Choose arr[0], arr[1]: arr[] = {20, 6, 7, 8, 9, 10}
Choose arr[1], arr[2]: arr[] = {20, 42, 8, 9, 10}
Choose arr[2], arr[3]: arr[] = {20, 42, 72, 10}
GCD of the formed array = 2Input: L = 3, R = 5, K = 1
Output: false
Explanation: Array will be arr[] = {3, 4, 5}]
Operation on arr[0], arr[1]: arr[] = {12, 5}, GCD = 1, or
Operation on arr[1], arr[2]: arr[] = {3, 20}, GCD = 1, or
Operation on arr[0], arr[2]: arr[] = {4, 15}, GCD = 1
Approach: The task can be solved by converting all the odd array elements to even so that the overall GCD of the array becomes even i.e greater than 1. To check if it is possible or not follow the cases below:
- Case 1: if L = R = 1 then GCD will always be 1, return false
- Case 2: if L = R (and L≠1) then GCD = L, return true
- Case 3: if K is greater equal to the number of odds between range L and R then return true
- If any of the above cases didn’t imply then return false.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to find that GCD of array is// greater than 1 or// not after at most K operationsbool gcdOfArray(int L, int R, int K){ // Finding number of integers // between L and R int range = (R - L + 1); int even = 0; int odd = 0; // Finding number of odd and even integers // in the given range if (range % 2 == 0) { even = range / 2; odd = range - even; } else { if (L % 2 != 0 || R % 2 != 0) { odd = (range / 2) + 1; even = range - odd; } else { odd = range / 2; even = range - odd; } } // Case 1 if (L == R && L == 1) return false; // Case 2 if (L == R) return true; // Case 3 if (K >= odd) return true; // Otherwise not possible else return false;}// Driver Codeint main(){ int L = 4; int R = 10; int K = 3; bool isPossible = gcdOfArray(L, R, K); if (isPossible) cout << "true" << endl; else cout << "false" << endl; return 0;} |
Java
// JAVA program for the above approachimport java.util.*;class GFG { // Function to find that GCD of array is // greater than 1 or // not after at most K operations public static boolean gcdOfArray(int L, int R, int K) { // Finding number of integers // between L and R int range = (R - L + 1); int even = 0; int odd = 0; // Finding number of odd and even integers // in the given range if (range % 2 == 0) { even = range / 2; odd = range - even; } else { if (L % 2 != 0 || R % 2 != 0) { odd = (range / 2) + 1; even = range - odd; } else { odd = range / 2; even = range - odd; } } // Case 1 if (L == R && L == 1) return false; // Case 2 if (L == R) return true; // Case 3 if (K >= odd) return true; // Otherwise not possible else return false; } // Driver Code public static void main(String[] args) { int L = 4; int R = 10; int K = 3; boolean isPossible = gcdOfArray(L, R, K); if (isPossible) System.out.println("true"); else System.out.println("false"); }}// This code is contributed by Taranpreet |
Python3
# Python program for the above approach# Function to find that GCD of array is# greater than 1 or# not after at most K operationsdef gcdOfArray(L, R, K): # Finding number of integers # between L and R range = (R - L + 1) even = 0 odd = 0 # Finding number of odd and even integers # in the given range if (range % 2 == 0): even = range // 2 odd = range - even else: if (L % 2 != 0 or R % 2 != 0): odd = (range // 2) + 1 even = range - odd else: odd = range // 2 even = range - odd # Case 1 if (L == R and L == 1): return False # Case 2 if (L == R): return True # Case 3 if (K >= odd): return True # Otherwise not possible else: return False# Driver CodeL = 4R = 10K = 3isPossible = gcdOfArray(L, R, K)if (isPossible): print("true")else: print("false")# This code is contributed by gfgking |
C#
// C# program for the above approachusing System;public class GFG{ // Function to find that GCD of array is // greater than 1 or // not after at most K operations public static bool gcdOfArray(int L, int R, int K) { // Finding number of integers // between L and R int range = (R - L + 1); int even = 0; int odd = 0; // Finding number of odd and even integers // in the given range if (range % 2 == 0) { even = range / 2; odd = range - even; } else { if (L % 2 != 0 || R % 2 != 0) { odd = (range / 2) + 1; even = range - odd; } else { odd = range / 2; even = range - odd; } } // Case 1 if (L == R && L == 1) return false; // Case 2 if (L == R) return true; // Case 3 if (K >= odd) return true; // Otherwise not possible else return false; } // Driver Code static public void Main (){ int L = 4; int R = 10; int K = 3; bool isPossible = gcdOfArray(L, R, K); if (isPossible) Console.WriteLine("true"); else Console.WriteLine("false"); }}// This code is contributed by Shubham Singh |
Javascript
<script> // JavaScript program for the above approach // Function to find that GCD of array is // greater than 1 or // not after at most K operations const gcdOfArray = (L, R, K) => { // Finding number of integers // between L and R let range = (R - L + 1); let even = 0; let odd = 0; // Finding number of odd and even integers // in the given range if (range % 2 == 0) { even = parseInt(range / 2); odd = range - even; } else { if (L % 2 != 0 || R % 2 != 0) { odd = parseInt(range / 2) + 1; even = range - odd; } else { odd = parseInt(range / 2); even = range - odd; } } // Case 1 if (L == R && L == 1) return false; // Case 2 if (L == R) return true; // Case 3 if (K >= odd) return true; // Otherwise not possible else return false; } // Driver Code let L = 4; let R = 10; let K = 3; let isPossible = gcdOfArray(L, R, K); if (isPossible) document.write("true"); else document.write("false");// This code is contributed by rakeshsahni</script> |
Output
true
Time Complexity: O(1)
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Share your thoughts in the comments
