Check for an array element that is co-prime with all others
Given an array arr[] of positive integers where 2 ? arr[i] ? 106 for all possible values of i. The task is to check whether there exists at least one element in the given array that forms co-prime pair with all other elements of the array. If no such element exists then print No else print Yes.
Examples:
Input: arr[] = {2, 8, 4, 10, 6, 7}
Output: Yes
7 is co-prime with all the other elements of the arrayInput: arr[] = {3, 6, 9, 12}
Output: No
Naive approach: A simple solution is to check whether the gcd of every element with all other elements is equal to 1. Time complexity of this solution is O(n2).
Efficient approach: An efficient solution is to generate all the prime factors of integers in the given array. Using hash, store the count of every element which is a prime factor of any of the number in the array. If the element does not contain any common prime factor with other elements, it always forms a co-prime pair with other elements.
For generating prime factors please go through the article Prime Factorization using Sieve in O(log n)
Below is the implementation of the above approach:
C++
// C++ implementation of the approach #include <bits/stdc++.h> using namespace std; #define MAXN 1000001 // Stores smallest prime factor for every number int spf[MAXN]; // Hash to store prime factors count int hash1[MAXN] = { 0 }; // Function to calculate SPF (Smallest Prime Factor) // for every number till MAXN void sieve() { spf[1] = 1; for ( int i = 2; i < MAXN; i++) // Marking smallest prime factor for every // number to be itself spf[i] = i; // Separately marking spf for every even // number as 2 for ( int i = 4; i < MAXN; i += 2) spf[i] = 2; // Checking if i is prime for ( int i = 3; i * i < MAXN; i++) { // Marking SPF for all numbers divisible by i if (spf[i] == i) { for ( int j = i * i; j < MAXN; j += i) // Marking spf[j] if it is not // previously marked if (spf[j] == j) spf[j] = i; } } } // Function to store the prime factors after dividing // by the smallest prime factor at every step void getFactorization( int x) { int temp; while (x != 1) { temp = spf[x]; if (x % temp == 0) { // Storing the count of // prime factors in hash hash1[spf[x]]++; x = x / spf[x]; } while (x % temp == 0) x = x / temp; } } // Function that returns true if there are // no common prime factors between x // and other numbers of the array bool check( int x) { int temp; while (x != 1) { temp = spf[x]; // Checking whether it common // prime factor with other numbers if (x % temp == 0 && hash1[temp] > 1) return false ; while (x % temp == 0) x = x / temp; } return true ; } // Function that returns true if there is // an element in the array which is coprime // with all the other elements of the array bool hasValidNum( int arr[], int n) { // Using sieve for generating prime factors sieve(); for ( int i = 0; i < n; i++) getFactorization(arr[i]); // Checking the common prime factors // with other numbers for ( int i = 0; i < n; i++) if (check(arr[i])) return true ; return false ; } // Driver code int main() { int arr[] = { 2, 8, 4, 10, 6, 7 }; int n = sizeof (arr) / sizeof (arr[0]); if (hasValidNum(arr, n)) cout << "Yes" ; else cout << "No" ; return 0; } |
Java
// Java implementation of the approach class GFG { static int MAXN = 1000001 ; // Stores smallest prime factor for every number static int [] spf = new int [MAXN]; // Hash to store prime factors count static int [] hash1 = new int [MAXN]; // Function to calculate SPF (Smallest Prime Factor) // for every number till MAXN static void sieve() { spf[ 1 ] = 1 ; for ( int i = 2 ; i < MAXN; i++) // Marking smallest prime factor for every // number to be itself spf[i] = i; // Separately marking spf for every even // number as 2 for ( int i = 4 ; i < MAXN; i += 2 ) spf[i] = 2 ; // Checking if i is prime for ( int i = 3 ; i * i < MAXN; i++) { // Marking SPF for all numbers divisible by i if (spf[i] == i) { for ( int j = i * i; j < MAXN; j += i) // Marking spf[j] if it is not // previously marked if (spf[j] == j) spf[j] = i; } } } // Function to store the prime factors after dividing // by the smallest prime factor at every step static void getFactorization( int x) { int temp; while (x != 1 ) { temp = spf[x]; if (x % temp == 0 ) { // Storing the count of // prime factors in hash hash1[spf[x]]++; x = x / spf[x]; } while (x % temp == 0 ) x = x / temp; } } // Function that returns true if there are // no common prime factors between x // and other numbers of the array static boolean check( int x) { int temp; while (x != 1 ) { temp = spf[x]; // Checking whether it common // prime factor with other numbers if (x % temp == 0 && hash1[temp] > 1 ) return false ; while (x % temp == 0 ) x = x / temp; } return true ; } // Function that returns true if there is // an element in the array which is coprime // with all the other elements of the array static boolean hasValidNum( int []arr, int n) { // Using sieve for generating prime factors sieve(); for ( int i = 0 ; i < n; i++) getFactorization(arr[i]); // Checking the common prime factors // with other numbers for ( int i = 0 ; i < n; i++) if (check(arr[i])) return true ; return false ; } // Driver code public static void main (String[] args) { int []arr = { 2 , 8 , 4 , 10 , 6 , 7 }; int n = arr.length; if (hasValidNum(arr, n)) System.out.println( "Yes" ); else System.out.println( "No" ); } } // This code is contributed by chandan_jnu |
Python3
# Python3 implementation of the approach MAXN = 1000001 # Stores smallest prime factor for # every number spf = [i for i in range (MAXN)] # Hash to store prime factors count hash1 = [ 0 for i in range (MAXN)] # Function to calculate SPF (Smallest # Prime Factor) for every number till MAXN def sieve(): # Separately marking spf for # every even number as 2 for i in range ( 4 , MAXN, 2 ): spf[i] = 2 # Checking if i is prime for i in range ( 3 , MAXN): if i * i > = MAXN: break # Marking SPF for all numbers # divisible by i if (spf[i] = = i): for j in range (i * i, MAXN, i): # Marking spf[j] if it is not # previously marked if (spf[j] = = j): spf[j] = i # Function to store the prime factors # after dividing by the smallest prime # factor at every step def getFactorization(x): while (x ! = 1 ): temp = spf[x] if (x % temp = = 0 ): # Storing the count of # prime factors in hash hash1[spf[x]] + = 1 x = x / / spf[x] while (x % temp = = 0 ): x = x / / temp # Function that returns true if there # are no common prime factors between x # and other numbers of the array def check(x): while (x ! = 1 ): temp = spf[x] # Checking whether it common # prime factor with other numbers if (x % temp = = 0 and hash1[temp] > 1 ): return False while (x % temp = = 0 ): x = x / / temp return True # Function that returns true if there is # an element in the array which is coprime # with all the other elements of the array def hasValidNum(arr, n): # Using sieve for generating # prime factors sieve() for i in range (n): getFactorization(arr[i]) # Checking the common prime factors # with other numbers for i in range (n): if (check(arr[i])): return True return False # Driver code arr = [ 2 , 8 , 4 , 10 , 6 , 7 ] n = len (arr) if (hasValidNum(arr, n)): print ( "Yes" ) else : print ( "No" ) # This code is contributed by mohit kumar |
C#
// C# implementation of the approach using System; class GFG { static int MAXN=1000001; // Stores smallest prime factor for every number static int [] spf = new int [MAXN]; // Hash to store prime factors count static int [] hash1 = new int [MAXN]; // Function to calculate SPF (Smallest Prime Factor) // for every number till MAXN static void sieve() { spf[1] = 1; for ( int i = 2; i < MAXN; i++) // Marking smallest prime factor for every // number to be itself spf[i] = i; // Separately marking spf for every even // number as 2 for ( int i = 4; i < MAXN; i += 2) spf[i] = 2; // Checking if i is prime for ( int i = 3; i * i < MAXN; i++) { // Marking SPF for all numbers divisible by i if (spf[i] == i) { for ( int j = i * i; j < MAXN; j += i) // Marking spf[j] if it is not // previously marked if (spf[j] == j) spf[j] = i; } } } // Function to store the prime factors after dividing // by the smallest prime factor at every step static void getFactorization( int x) { int temp; while (x != 1) { temp = spf[x]; if (x % temp == 0) { // Storing the count of // prime factors in hash hash1[spf[x]]++; x = x / spf[x]; } while (x % temp == 0) x = x / temp; } } // Function that returns true if there are // no common prime factors between x // and other numbers of the array static bool check( int x) { int temp; while (x != 1) { temp = spf[x]; // Checking whether it common // prime factor with other numbers if (x % temp == 0 && hash1[temp] > 1) return false ; while (x % temp == 0) x = x / temp; } return true ; } // Function that returns true if there is // an element in the array which is coprime // with all the other elements of the array static bool hasValidNum( int []arr, int n) { // Using sieve for generating prime factors sieve(); for ( int i = 0; i < n; i++) getFactorization(arr[i]); // Checking the common prime factors // with other numbers for ( int i = 0; i < n; i++) if (check(arr[i])) return true ; return false ; } // Driver code static void Main() { int []arr = { 2, 8, 4, 10, 6, 7 }; int n = arr.Length; if (hasValidNum(arr, n)) Console.WriteLine( "Yes" ); else Console.WriteLine( "No" ); } } // This code is contributed by chandan_jnu |
PHP
<?php // PHP implementation of the approach $MAXN = 10001; // Stores smallest prime factor for every number $spf = array_fill (0, $MAXN , 0); // Hash to store prime factors count $hash1 = array_fill (0, $MAXN , 0); // Function to calculate SPF (Smallest Prime Factor) // for every number till MAXN function sieve() { global $spf , $MAXN , $hash1 ; $spf [1] = 1; for ( $i = 2; $i < $MAXN ; $i ++) // Marking smallest prime factor for every // number to be itself $spf [ $i ] = $i ; // Separately marking spf for every even // number as 2 for ( $i = 4; $i < $MAXN ; $i += 2) $spf [ $i ] = 2; // Checking if i is prime for ( $i = 3; $i * $i < $MAXN ; $i ++) { // Marking SPF for all numbers divisible by i if ( $spf [ $i ] == $i ) { for ( $j = $i * $i ; $j < $MAXN ; $j += $i ) // Marking spf[j] if it is not // previously marked if ( $spf [ $j ] == $j ) $spf [ $j ] = $i ; } } } // Function to store the prime factors after dividing // by the smallest prime factor at every step function getFactorization( $x ) { global $spf , $MAXN , $hash1 ; while ( $x != 1) { $temp = $spf [ $x ]; if ( $x % $temp == 0) { // Storing the count of // prime factors in hash $hash1 [ $spf [ $x ]]++; $x = (int)( $x / $spf [ $x ]); } while ( $x % $temp == 0) $x = (int)( $x / $temp ); } } // Function that returns true if there are // no common prime factors between x // and other numbers of the array function check( $x ) { global $spf , $MAXN , $hash1 ; while ( $x != 1) { $temp = $spf [ $x ]; // Checking whether it common // prime factor with other numbers if ( $x % $temp == 0 && $hash1 [ $temp ] > 1) return false; while ( $x % $temp == 0) $x = (int)( $x / $temp ); } return true; } // Function that returns true if there is // an element in the array which is coprime // with all the other elements of the array function hasValidNum( $arr , $n ) { global $spf , $MAXN , $hash1 ; // Using sieve for generating prime factors sieve(); for ( $i = 0; $i < $n ; $i ++) getFactorization( $arr [ $i ]); // Checking the common prime factors // with other numbers for ( $i = 0; $i < $n ; $i ++) if (check( $arr [ $i ])) return true; return false; } // Driver code $arr = array ( 2, 8, 4, 10, 6, 7 ); $n = count ( $arr ); if (hasValidNum( $arr , $n )) echo "Yes" ; else echo "No" ; // This code is contributed by chandan_jnu ?> |
Javascript
<script> // Javascript implementation of the approach let MAXN = 1000001; // Stores smallest prime factor for every number let spf = new Array(MAXN); // Hash to store prime factors count let hash1 = new Array(MAXN); // Function to calculate SPF (Smallest Prime Factor) // for every number till MAXN function sieve() { spf[1] = 1; for (let i = 2; i < MAXN; i++) // Marking smallest prime factor for // every number to be itself spf[i] = i; // Separately marking spf for every even // number as 2 for (let i = 4; i < MAXN; i += 2) spf[i] = 2; // Checking if i is prime for (let i = 3; i * i < MAXN; i++) { // Marking SPF for all numbers divisible by i if (spf[i] == i) { for (let j = i * i; j < MAXN; j += i) // Marking spf[j] if it is not // previously marked if (spf[j] == j) spf[j] = i; } } } // Function to store the prime factors // after dividing by the smallest prime // factor at every step function getFactorization(x) { let temp; while (x != 1) { temp = spf[x]; if (x % temp == 0) { // Storing the count of // prime factors in hash hash1[spf[x]]++; x = x / spf[x]; } while (x % temp == 0) x = x / temp; } } // Function that returns true if there are // no common prime factors between x // and other numbers of the array function check(x) { let temp; while (x != 1) { temp = spf[x]; // Checking whether it common // prime factor with other numbers if (x % temp == 0 && hash1[temp] > 1) return false ; while (x % temp == 0) x = x / temp; } return true ; } // Function that returns true if there is // an element in the array which is coprime // with all the other elements of the array function hasValidNum(arr, n) { // Using sieve for generating prime factors sieve(); for (let i = 0; i < n; i++) getFactorization(arr[i]); // Checking the common prime factors // with other numbers for (let i = 0; i < n; i++) if (check(arr[i])) return true ; return false ; } // Driver code let arr = [ 2, 8, 4, 10, 6, 7 ]; let n = arr.length; if (hasValidNum(arr, n)) document.write( "Yes" ); else document.write( "No" ); // This code is contributed by unknown2108 </script> |
Yes
Contact Us