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 numberint spf[MAXN];// Hash to store prime factors countint hash1[MAXN] = { 0 };// Function to calculate SPF (Smallest Prime Factor)// for every number till MAXNvoid 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 stepvoid 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 arraybool 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 arraybool 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 codeint 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 approachclass GFG{ static int MAXN = 1000001;// Stores smallest prime factor for every numberstatic int[] spf = new int[MAXN];// Hash to store prime factors countstatic int[] hash1 = new int[MAXN];// Function to calculate SPF (Smallest Prime Factor)// for every number till MAXNstatic 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 stepstatic 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 arraystatic 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 arraystatic 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 codepublic 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 approachMAXN = 1000001# Stores smallest prime factor for # every numberspf = [i for i in range(MAXN)]# Hash to store prime factors counthash1 = [0 for i in range(MAXN)]# Function to calculate SPF (Smallest # Prime Factor) for every number till MAXNdef 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 stepdef 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 arraydef 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 arraydef 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 codearr = [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 approachusing System;class GFG{ static int MAXN=1000001;// Stores smallest prime factor for every numberstatic int[] spf = new int[MAXN];// Hash to store prime factors countstatic int[] hash1 = new int[MAXN];// Function to calculate SPF (Smallest Prime Factor)// for every number till MAXNstatic 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 stepstatic 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 arraystatic 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 arraystatic 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 codestatic 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 MAXNfunction 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 stepfunction 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 arrayfunction 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 arrayfunction 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 approachlet MAXN = 1000001;// Stores smallest prime factor for every numberlet spf = new Array(MAXN);// Hash to store prime factors countlet hash1 = new Array(MAXN);// Function to calculate SPF (Smallest Prime Factor)// for every number till MAXNfunction 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 stepfunction 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 arrayfunction 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 arrayfunction 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 codelet 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> |
Output:
Yes
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 zambiatek!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!
