Given an array arr[] size N, the task is to find the smallest number which is not co-prime with any element of the given array.
Examples:
Input: arr[] = {3, 4, 6, 7, 8, 9, 10}
Output: 42
Explanation: The prime factorization of array elements are:
3 = 3
4 = 2 * 2
6 = 2 * 3
7 = 7
8 = 2 * 2 * 2
9 = 3 * 3
10 = 2 * 5
Considering prime factors {2, 3, 7} to get the number X (= 2 * 3 * 7 = 42), which is not co-prime with any other array element.Input: arr[] = {4, 3}
Output: 6
Explanation: The prime factorization of array elements are:
4 = 2 * 2
3 = 3
Considering prime factors {2, 3} to get the number X (= 2 * 3 = 6), which is not co-prime with any other array element.
Approach: The idea is based on the observation that the required number, say X, should not be co-prime with any array element arr[i]. There must exist some common factor, d ? 2 for each array element arr[i] which divides both arr[i] and X. The minimum d possible is a prime number. Hence, the idea is to consider the set of prime numbers such that their product is not co-prime with all array elements and find the minimum number possible. Follow the steps below to solve the problem:
- Initialize a variable, say ans, as INT_MAX to store the required result.
- Initialize an array, primes[] to store the prime numbers.
- Generate all the subsets of this array and for each subset, store its product in a variable, say P. Check whether it is not coprime with any of the array elements. If found be true, then update the value of ans.
- Otherwise, move to the next subset.
- After completing the above steps, print the value of ans as the result.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;#define ll long long int#define MAX 50// Function check if a// number is prime or notbool isPrime(ll n){ // Corner cases if (n <= 1) return false; if (n <= 3) return true; // Check if n is divisible by 2 or 3 if (n % 2 == 0 || n % 3 == 0) return false; // Check for every 6th number. The above // checking allows to skip middle 5 numbers for (ll i = 5; i * i <= n; i = i + 6) if (n % i == 0 || n % (i + 2) == 0) return false; return true;}// Function to store primes in an arrayvoid findPrime(vector<ll>& primes){ for (ll i = 2; i <= MAX; i++) { if (isPrime(i)) primes.push_back(i); }}// Function to calculate// GCD of two numbersll gcd(ll a, ll b){ if (b == 0) return a; else return gcd(b, a % b);}// Function to find the smallest// number which is not coprime with// any element of the array arr[]void findMinimumNumber(ll arr[], ll N){ // Store the prime numbers vector<ll> primes; // Function call to fill // the prime numbers findPrime(primes); // Stores the answer ll ans = INT_MAX; ll n = primes.size(); // Generate all non-empty // subsets of the primes[] array for (ll i = 1; i < (1 << n); i++) { // Stores product of the primes ll temp = 1; for (ll j = 0; j < n; j++) { if (i & (1 << j)) { temp *= primes[j]; } } // Checks if temp is coprime // with the array or not bool check = true; // Check if the product temp is // not coprime with the whole array for (ll k = 0; k < N; k++) { if (gcd(temp, arr[k]) == 1) { check = false; break; } } // If the product is not // co-prime with the array if (check) ans = min(ans, temp); } // Print the answer cout << ans;}// Driver Codeint main(){ // Given array ll arr[] = { 3, 4, 6, 7, 8, 9, 10 }; // Stores the size of the array ll N = sizeof(arr) / sizeof(arr[0]); findMinimumNumber(arr, N); return 0;} |
Java
// Java program for the above approachimport java.util.*;class GFG{ static long MAX = 50;// Function check if a// number is prime or notstatic boolean isPrime(long n){ // Corner cases if (n <= 1) return false; if (n <= 3) return true; // Check if n is divisible by 2 or 3 if (n % 2 == 0 || n % 3 == 0) return false; // Check for every 6th number. The above // checking allows to skip middle 5 numbers for(long i = 5; i * i <= n; i = i + 6) if (n % i == 0 || n % (i + 2) == 0) return false; return true;}// Function to store primes in an arraystatic void findPrime(ArrayList<Long> primes){ for(long i = 2; i <= MAX; i++) { if (isPrime(i)) primes.add(i); }}// Function to calculate// GCD of two numbersstatic long gcd(long a, long b){ if (b == 0) return a; else return gcd(b, a % b);}// Function to find the smallest// number which is not coprime with// any element of the array arr[]static void findMinimumNumber(long []arr, long N){ ArrayList<Long> primes = new ArrayList<Long>(); // Function call to fill // the prime numbers findPrime(primes); // Stores the answer long ans = 2147483647; int n = primes.size(); // Generate all non-empty // subsets of the primes[] array for(int i = 1; i < (1 << n); i++) { // Stores product of the primes long temp = 1; for(int j = 0; j < n; j++) { if ((i & (1 << j)) > 0) { temp *= primes.get(j); } } // Checks if temp is coprime // with the array or not boolean check = true; // Check if the product temp is // not coprime with the whole array for(long k = 0; k < N; k++) { if (gcd(temp, arr[(int)k]) == 1l) { check = false; break; } } // If the product is not // co-prime with the array if (check == true) ans = Math.min(ans, temp); } // Prlong the answer System.out.print(ans);}// Driver code public static void main (String[] args) { // Given array long []arr = { 3, 4, 6, 7, 8, 9, 10 }; // Stores the size of the array long N = arr.length; findMinimumNumber(arr, N);}}// This code is contributed by offbeat |
Python3
# Python 3 program for the above approachMAX = 50import sysfrom math import sqrt,gcd# Function check if a# number is prime or notdef isPrime(n): # Corner cases if (n <= 1): return False if (n <= 3): return True # Check if n is divisible by 2 or 3 if (n % 2 == 0 or n % 3 == 0): return False # Check for every 6th number. The above # checking allows to skip middle 5 numbers for i in range(5,int(sqrt(n))+1,6): if (n % i == 0 or n % (i + 2) == 0): return False return True# Function to store primes in an arraydef findPrime(primes): global MAX for i in range(2, MAX + 1, 1): if(isPrime(i)): primes.append(i)# Function to find the smallest# number which is not coprime with# any element of the array arr[]def findMinimumNumber(arr, N): # Store the prime numbers primes = [] # Function call to fill # the prime numbers findPrime(primes) # Stores the answer ans = sys.maxsize n = len(primes) # Generate all non-empty # subsets of the primes[] array for i in range(1, (1 << n), 1): # Stores product of the primes temp = 1 for j in range(n): if (i & (1 << j)): temp *= primes[j] # Checks if temp is coprime # with the array or not check = True # Check if the product temp is # not coprime with the whole array for k in range(N): if (gcd(temp, arr[k]) == 1): check = False break # If the product is not # co-prime with the array if (check): ans = min(ans, temp) # Print the answer print(ans)# Driver Codeif __name__ == '__main__': # Given array arr = [3, 4, 6, 7, 8, 9, 10] # Stores the size of the array N = len(arr) findMinimumNumber(arr, N) # This code is contributed by ipg2016107. |
C#
// C# program for the above approachusing System;using System.Collections.Generic;class GFG{static long MAX = 50;// Function check if a// number is prime or notstatic bool isPrime(long n){ // Corner cases if (n <= 1) return false; if (n <= 3) return true; // Check if n is divisible by 2 or 3 if (n % 2 == 0 || n % 3 == 0) return false; // Check for every 6th number. The above // checking allows to skip middle 5 numbers for(long i = 5; i * i <= n; i = i + 6) if (n % i == 0 || n % (i + 2) == 0) return false; return true;}// Function to store primes in an arraystatic void findPrime(List<long> primes){ for(long i = 2; i <= MAX; i++) { if (isPrime(i)) primes.Add(i); }}// Function to calculate// GCD of two numbersstatic long gcd(long a, long b){ if (b == 0) return a; else return gcd(b, a % b);}// Function to find the smallest// number which is not coprime with// any element of the array arr[]static void findMinimumNumber(long []arr, long N){ List<long> primes = new List<long>(); // Function call to fill // the prime numbers findPrime(primes); // Stores the answer long ans = 2147483647; int n = primes.Count; // Generate all non-empty // subsets of the primes[] array for(int i = 1; i < (1 << n); i++) { // Stores product of the primes long temp = 1; for(int j = 0; j < n; j++) { if ((i & (1 << j)) > 0) { temp *= primes[j]; } } // Checks if temp is coprime // with the array or not bool check = true; // Check if the product temp is // not coprime with the whole array for(long k = 0; k < N; k++) { if (gcd(temp, arr[k]) == 1) { check = false; break; } } // If the product is not // co-prime with the array if (check == true) ans = Math.Min(ans, temp); } // Prlong the answer Console.Write(ans);}// Driver Codepublic static void Main(){ // Given array long []arr = { 3, 4, 6, 7, 8, 9, 10 }; // Stores the size of the array long N = arr.Length; findMinimumNumber(arr, N);}}// This code is contributed by SURENDRA_GANGWAR |
Javascript
<script>// JavaScript program for the above approachlet MAX = 50let primes = [];// Function check if a// number is prime or notfunction isPrime(n){ // Corner cases if (n <= 1) return false; if (n <= 3) return true; // Check if n is divisible by 2 or 3 if (n % 2 == 0 || n % 3 == 0) return false; // Check for every 6th number. The above // checking allows to skip middle 5 numbers for (let i = 5; i * i <= n; i = i + 6) if (n % i == 0 || n % (i + 2) == 0) return false; return true;}// Function to store primes in an arrayfunction findPrime(){ for (let i = 2; i <= MAX; i++) { if (isPrime(i)) primes.push(i); }}// Function to calculate// GCD of two numbersfunction gcd(a, b){ if (b == 0) return a; else return gcd(b, a % b);}// Function to find the smallest// number which is not coprime with// any element of the array arr[]function findMinimumNumber(arr, N){ // Store the prime numbers // Function call to fill // the prime numbers findPrime(); // Stores the answer let ans = Number.MAX_SAFE_INTEGER; let n = primes.length; // Generate all non-empty // subsets of the primes[] array for (let i = 1; i < (1 << n); i++) { // Stores product of the primes let temp = 1; for (let j = 0; j < n; j++) { if (i & (1 << j)) { temp *= primes[j]; } } // Checks if temp is coprime // with the array or not let check = true; // Check if the product temp is // not coprime with the whole array for (let k = 0; k < N; k++) { if (gcd(temp, arr[k]) == 1) { check = false; break; } } // If the product is not // co-prime with the array if (check) ans = Math.min(ans, temp); } // Print the answer document.write(ans);}// Driver Code// Given arraylet arr = [ 3, 4, 6, 7, 8, 9, 10 ];// Stores the size of the arraylet N = arr.length;findMinimumNumber(arr, N);</script> |
Output:
42
Time Complexity: O(2M*N*log(X)), where M is the size of the array primes[] and X is the smallest element in the array arr[]
Auxiliary Space: O(M)
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!
