Given an array arr[] of size N, the task is to find the maximum number of sub-arrays such that the GCD(Greatest Common Factor) of all elements of each sub-array is equal to 1 in O(n).
Examples:
Input: arr[] = {4, 2, 3, 0, 1, 8, 16, 1}.
Output: 3
Explanation: GCD of subarray {4, 2, 3} is 1, GCD of subarray {0, 1} is 1. GCD of {8, 16, 1} is 1, maximum number of subarrays is 3.Input: arr[] = {9, 36, 8, 3, 7, 2, 13, 26, 5}
Output: 4
Explanation: GCD of subarray {9, 36, 8} is 1, GCD of subarray {3, 7} is 1, GCD of {2, 13} is 1, GCD of {26, 5} is 1, maximum number of subarrays is 4.
Approach: To solve the problem follow the below observations:
- GCD of any number with 0 is the number itself, hence, initially set GCD as 0.
- GCD of any two numbers will be 1 if they don’t have any common factor.
In the traversal:
- Keep on calculating the GCD of the current element with the GCD of the subarray till now.
- At any position, If the GCD of the current subarray becomes 1 then increase the count of the subarray by one and set the gcd to 0 so that we can calculate the maximum subarray.
- Return the number of subarrays.
Follow the given steps to solve the problem:
- Declare variables cnt and g and initialize them to 0.
- variable g denotes GCD.
- While traversing the array:
- Keep calculating GCD till the g becomes 1.
- If g equals 1, then increase the cnt variable, and set g to 0.
- In the end, return the number of subarrays.
Below is the implementation for the above approach:
C++
// C++ program to find maximum number of// sub-arrays such that the GCD// of all elements of each sub-array is// equal to 1 in O(n))#include <bits/stdc++.h>using namespace std;// Function to find GCDint gcd(int a, int b){ if (b == 0) return a; return gcd(b, a % b);}// Function to count sub-arraysint count_subarrays(int arr[], int n){ int g = 0; int cnt = 0; // Counting subarrays whose gcd is 1 for (int i = 0; i < n; ++i) { g = gcd(g, arr[i]); // gcd becomes 1 then increases // the count if (g == 1) { cnt++; // Set g to 0 for further use g = 0; } } // Returning no. of subarrays return cnt;}// Driver codeint main(){ int arr[] = { 9, 36, 8, 3, 7, 2, 13, 26, 5 }; int n = (sizeof(arr) / sizeof(arr[0])); // Function call int ans = count_subarrays(arr, n); cout << ans; return 0;} |
Java
// Java program to find maximum number of// sub-arrays such that the GCD// of all elements of each sub-array is// equal to 1 in O(n))import java.io.*;class GFG { // Function to find GCD public static int gcd(int a, int b) { if (b == 0) return a; return gcd(b, a % b); } // Function to count sub-arrays public static int count_subarrays(int arr[], int n) { int g = 0; int cnt = 0; // Counting subarrays whose gcd is 1 for (int i = 0; i < n; ++i) { g = gcd(g, arr[i]); // gcd becomes 1 then increases // the count if (g == 1) { cnt++; // Set g to 0 for further use g = 0; } } // Returning no. of subarrays return cnt; } // Driver Code public static void main(String[] args) { int arr[] = { 9, 36, 8, 3, 7, 2, 13, 26, 5 }; int n = arr.length; // Function call int ans = count_subarrays(arr, n); System.out.print(ans); }}// This code is contributed by Rohit Pradhan |
Python3
class GFG : # Function to find GCD @staticmethod def gcd( a, b) : if (b == 0) : return a return GFG.gcd(b, a % b) # Function to count sub-arrays @staticmethod def count_subarrays( arr, n) : g = 0 cnt = 0 # Counting subarrays whose gcd is 1 i = 0 while (i < n) : g = GFG.gcd(g, arr[i]) # gcd becomes 1 then increases # the count if (g == 1) : cnt += 1 # Set g to 0 for further use g = 0 i += 1 # Returning no. of subarrays return cnt # Driver Code @staticmethod def main( args) : arr = [9, 36, 8, 3, 7, 2, 13, 26, 5] n = len(arr) # Function call ans = GFG.count_subarrays(arr, n) print(ans, end ="") if __name__=="__main__": GFG.main([]) # This code is contributed by aadityaburujwale. |
C#
// C# program to find maximum number of// sub-arrays such that the GCD// of all elements of each sub-array is// equal to 1 in O(n))using System;public class GFG{ // Function to find GCD public static int gcd(int a, int b) { if (b == 0) return a; return gcd(b, a % b); } // Function to count sub-arrays public static int count_subarrays(int []arr, int n) { int g = 0; int cnt = 0; // Counting subarrays whose gcd is 1 for (int i = 0; i < n; ++i) { g = gcd(g, arr[i]); // gcd becomes 1 then increases // the count if (g == 1) { cnt++; // Set g to 0 for further use g = 0; } } // Returning no. of subarrays return cnt; } // Driver Code public static void Main(string[] args) { int []arr = { 9, 36, 8, 3, 7, 2, 13, 26, 5 }; int n = arr.Length; // Function call int ans = count_subarrays(arr, n); Console.WriteLine(ans); }}// This code is contributed by AnkThon |
Javascript
// JS program to find maximum number of// sub-arrays such that the GCD// of all elements of each sub-array is// equal to 1 in O(n))// Function to find GCDfunction gcd( a, b){ if (b == 0) return a; return gcd(b,a % b);}// Function to count sub-arraysfunction count_subarrays(arr, n){ let g = 0; let cnt = 0; // Counting subarrays whose gcd is 1 for (let i = 0; i < n; ++i) { g = gcd(g, arr[i]); // gcd becomes 1 then increases // the count if (g == 1) { cnt++; // Set g to 0 for further use g = 0; } } // Returning no. of subarrays return cnt;}// Driver code let arr = [ 9, 36, 8, 3, 7, 2, 13, 26, 5 ]; let n = arr.length; // Function call let ans = count_subarrays(arr, n); console.log(ans); //this code is contributed by ksam24000 |
Output
4
Time Complexity: O(N*log(M)), where N is the size of the array and M is the minimum element in the given array
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!
