Given an array arr[] of size N, the task is to count the number of indices in arr[] such that after changing the element of that index to any number, the GCD of the array is changed.
Examples:
Input: arr[] = {3, 6, 9}
Output: 3
Explanation: The GCD of the array is 3.
If we change 3 to 4, the GCD of arr[] becomes 1.
If we change 6 to 7, the GCD of arr[] becomes 1.
If we change 9 to 10, the GCD of arr[] becomes 1.
So, the output is 3.Input: arr[] = {3, 5, 11}
Output: 0
Approach: To solve the problem follow the below idea:
If the GCD of all the elements after removing the ith element is not 1, then we can change the GCD of the array by changing ith element to any prime. Otherwise, whatever we do, the GCD will always be a 1.
- Firstly, create a prefix and suffix array of GCD of array arr[].
- Now Run a loop and check for every index, that if after removing the element from index arr[], the GCD is greater than 1 or not.
- If the GCD after removing the ith index element is at least 2, it means the ith element is changeable to a prime number or something, so the GCD of arr[] becomes 1. So, increment Count by 1.
- But if the GCD after removing the ith index element is 1, it means that the GCD cannot be changed by changing the ith element, the GCD remains the same.
- Return the total count as the required answer.
Below is the implementation of the above approach:
C++
// C++ code to implement the above approach#include <bits/stdc++.h>#define ll long longusing namespace std;// Function to find GCD of two numbersll GCD(ll a, ll b){ if (!b) return a; return GCD(b, a % b);}// Function to find the GCD of array// without the element at index ill find(ll* prefix, ll* suffix, ll i, ll n){ // First Index if (i == 0) { return suffix[1]; } // Last Index if (i == n - 1) { return prefix[n - 2]; } // Middle Index else { return GCD(prefix[i - 1], suffix[i + 1]); }}// Function to find the countll findCount(ll* arr, ll n){ ll i, Count = 0; ll prefix[n]; ll suffix[n]; prefix[0] = arr[0]; suffix[n - 1] = arr[n - 1]; // Create Prefix array of GCD for (i = 1; i < n; i++) { prefix[i] = GCD(prefix[i - 1], arr[i]); } // Create Suffix array of GCD for (i = n - 2; i >= 0; i--) { suffix[i] = GCD(suffix[i + 1], arr[i]); } // Find if after removing that index // element the GCD is 1 or not for (i = 0; i < n; i++) { // If GCD is not 1 then we can change // the element at index i to a // prime number and the GCD of // array arr[] is changed to 1 if (find(prefix, suffix, i, n) > 1) Count++; } return Count;}// Driver Codeint main(){ ll arr[] = { 3, 6, 9 }; ll N = sizeof(arr) / sizeof(arr[0]); // Function Call cout << findCount(arr, N); return 0;} |
Java
// Java code to implement the above approachimport java.util.*;class GFG{// Function to find GCD of two numbersstatic int GCD(int a, int b){ if (b == 0) return a; return GCD(b, a % b);}// Function to find the GCD of array// without the element at index istatic int find(int[] prefix, int[] suffix, int i, int n){ // First Index if (i == 0) { return suffix[1]; } // Last Index if (i == n - 1) { return prefix[n - 2]; } // Middle Index else { return GCD(prefix[i - 1], suffix[i + 1]); }}// Function to find the countstatic int findCount(int []arr, int n){ int i, Count = 0; int []prefix = new int[n]; int []suffix = new int[n]; prefix[0] = arr[0]; suffix[n - 1] = arr[n - 1]; // Create Prefix array of GCD for (i = 1; i < n; i++) { prefix[i] = GCD(prefix[i - 1], arr[i]); } // Create Suffix array of GCD for (i = n - 2; i >= 0; i--) { suffix[i] = GCD(suffix[i + 1], arr[i]); } // Find if after removing that index // element the GCD is 1 or not for (i = 0; i < n; i++) { // If GCD is not 1 then we can change // the element at index i to a // prime number and the GCD of // array arr[] is changed to 1 if (find(prefix, suffix, i, n) > 1) Count++; } return Count;}// Driver Codepublic static void main(String[] args){ int arr[] = { 3, 6, 9 }; int N = arr.length; // Function Call System.out.print(findCount(arr, N));}}// This code is contributed by shikhasingrajput |
Python3
# python code to implement the above approach# Function to find GCD of two numbersdef GCD(a, b): if (not b): return a return GCD(b, a % b)# Function to find the GCD of array# without the element at index idef find(prefix, suffix, i, n): # First Index if (i == 0): return suffix[1] # Last Index if (i == n - 1): return prefix[n - 2] # Middle Index else: return GCD(prefix[i - 1], suffix[i + 1])# Function to find the countdef findCount(arr, n): i, Count = 0, 0 prefix = [0 for _ in range(n)] suffix = [0 for _ in range(n)] prefix[0] = arr[0] suffix[n - 1] = arr[n - 1] # Create Prefix array of GCD for i in range(1, n): prefix[i] = GCD(prefix[i - 1], arr[i]) # Create Suffix array of GCD for i in range(n-2, -1, -1): suffix[i] = GCD(suffix[i + 1], arr[i]) # Find if after removing that index # element the GCD is 1 or not for i in range(0, n): # If GCD is not 1 then we can change # the element at index i to a # prime number and the GCD of # array arr[] is changed to 1 if (find(prefix, suffix, i, n) > 1): Count += 1 return Count# Driver Codeif __name__ == "__main__": arr = [3, 6, 9] N = len(arr) # Function Call print(findCount(arr, N)) # This code is contributed by rakeshsahni |
C#
using System;public class GFG{ // Function to find GCD of two numbers public static long GCD(long a, long b) { if (b != 0) return a; return GCD(b, a % b); } // Function to find the GCD of array // without the element at index i public static long find(long[] prefix, long[] suffix, long i, long n) { // First Index if (i == 0) { return suffix[1]; } // Last Index if (i == n - 1) { return prefix[n - 2]; } // Middle Index else { return GCD(prefix[i - 1], suffix[i + 1]); } } // Function to find the count public static long findCount(long[] arr, long n) { long i; long Count = 0; long[] prefix = new long[n]; long[] suffix = new long[n]; prefix[0] = arr[0]; suffix[n - 1] = arr[n - 1]; // Create Prefix array of GCD for (i = 1; i < n; i++) { prefix[i] = GCD(prefix[i - 1], arr[i]); } // Create Suffix array of GCD for (i = n - 2; i >= 0; i--) { suffix[i] = GCD(suffix[i + 1], arr[i]); } // Find if after removing that index // element the GCD is 1 or not for (i = 0; i < n; i++) { // If GCD is not 1 then we can change // the element at index i to a // prime number and the GCD of // array arr[] is changed to 1 if (find(prefix, suffix, i, n) > 1) Count++; } return Count; } static public void Main (){ long[] arr = { 3, 6, 9 }; long N = arr.Length; // Function Call Console.WriteLine(findCount(arr, N)); }}// This code is contributed by akashish__ |
Javascript
<script>// JavaScript code to implement the above approach// Function to find GCD of two numbersfunction GCD(a, b){ if (!b) return a; return GCD(b, a % b);}// Function to find the GCD of array// without the element at index ifunction find(prefix,suffix,i, n){ // First Index if (i == 0) { return suffix[1]; } // Last Index if (i == n - 1) { return prefix[n - 2]; } // Middle Index else { return GCD(prefix[i - 1], suffix[i + 1]); }}// Function to find the countfunction findCount(arr, n){ let i, Count = 0; let prefix = new Array(n); let suffix=new Array(n); prefix[0] = arr[0]; suffix[n - 1] = arr[n - 1]; // Create Prefix array of GCD for (i = 1; i < n; i++) { prefix[i] = GCD(prefix[i - 1], arr[i]); } // Create Suffix array of GCD for (i = n - 2; i >= 0; i--) { suffix[i] = GCD(suffix[i + 1], arr[i]); } // Find if after removing that index // element the GCD is 1 or not for (i = 0; i < n; i++) { // If GCD is not 1 then we can change // the element at index i to a // prime number and the GCD of // array arr[] is changed to 1 if (find(prefix, suffix, i, n) > 1) Count++; } return Count;}// Driver Code let arr = [ 3, 6, 9 ]; let N = arr.length; // Function Call document.write(findCount(arr, N)); // This code is contributed by satwik4409. </script> |
Output
3
Time Complexity: O(N * log Max) where Max is the maximum element of the array
Auxiliary Space: O(N)
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
