Given an array A[] and M, the task is to check whether there exist M non-overlapping subarrays(non-empty) of A for which the average of the GCD of those subarrays equals G where G denotes the gcd of all the numbers in the array A.
Examples:
Input: A[] = {1, 2, 3, 4, 5}, M = 3
Output: Yes
?Explanation: Here, G = gcd(1, 2, 3, 4, 5) = 1.
We can choose 3 non overlapping subarrays {[1], [2, 3], [4, 5]} where
gcd(1) = 1, gcd(2, 3) = 1, and gcd(4, 5) = 1.
Thus, the average = (1 + 1 + 1)/3 = 1. Hence, we can have 3 such subarrays.Input: A[] = {6, 12, 18, 24}
Output: No
Approach: The problem can be solved based on the following observation:
Observations:
Note that the gcd of any subarray of A[] will certainly be at least G, since G divides every element of A[]. So, each gi (gcd of subarray) ? G, which means the only way their average can equal G is if each gi itself equals G.
So, we need to find if at least M disjoint subarrays in A[] have gcd G.
- Since G divides every element of A[], if we have a subarray whose gcd is G, extending this subarray to the right or left will still leave its gcd as G.
- In particular, if a solution exists, then there will always exist a solution that covers the full array.
- This gives us a simple algorithm to check:
- While the array is not empty, find the smallest prefix of the array with gcd G. If no such prefix exists, stop.
- This prefix (if found) will form one subarray in the answer. Remove this prefix and do the same to the remaining array.
- The number of times we successfully performed the operation equals the maximum number of disjoint subarrays with gcd G that can be obtained.
If number is ? M then print ‘Yes’, otherwise print ‘No’.
Follow the below steps to solve the problem:
- Find the GCD(G)of all the elements in array A[].
- Keep a variable denoting the current gcd, say g. Initially, g = 0.
- For each i from 1 to N:
- Set g = gcd(g, Ai)
- If g > G, continue on
- If g = G, increase the count by 1 and reset g to 0.
- If the count of GCD is greater than or equal to M, print “Yes” else “No”
Below is the implementation of the above approach.
C++
// C++ code to implement the approach#include <bits/stdc++.h>using namespace std;// Function to find gcd of two numbersint gcd(int a, int b){ if (b == 0) { return a; } return gcd(b, a % b);}// Function to find check whether// non-overlapping subarray existsstring find(int arr[], int n, int m){ int G = 0; int g = 0; int count = 0; for (int i = 0; i < n; i++) { G = gcd(G, arr[i]); } for (int i = 0; i < n; i++) { // arr[i] = sc.nextInt(); g = gcd(g, arr[i]); if (g == G) { count++; g = 0; } } if (count >= m) return "Yes"; return "No";}// Driver codeint main(){ int A[] = {1, 2, 3, 4, 5}; int N = sizeof(A) / sizeof(A[0]); int K = 3; // Function call cout << (find(A, N, K));}// This code is contributed by Potta Lokesh |
Java
// Java code to implement the approachimport java.io.*;import java.util.*;public class GFG { // Function to find gcd of two numbers public static int gcd(int a, int b) { if (b == 0) { return a; } return gcd(b, a % b); } // Function to find check whether // non-overlapping subarray exists static String find(int arr[], int n, int m) { int G = 0; int g = 0; int count = 0; for (int i = 0; i < n; i++) { G = gcd(G, arr[i]); } for (int i = 0; i < n; i++) { // arr[i] = sc.nextInt(); g = gcd(g, arr[i]); if (g == G) { count++; g = 0; } } if (count >= m) return "Yes"; return "No"; } // Driver code public static void main(String[] args) { int A[] = { 1, 2, 3, 4, 5 }; int N = A.length; int K = 3; // Function call System.out.println(find(A, N, K)); }} |
Python3
# Python code to implement the approach# Function to find gcd of two numbersdef gcd(a, b): if (b == 0): return a return gcd(b, a % b)# Function to find check whether# non-overlapping subarray existsdef find(arr, n, m): G = 0 g = 0 count = 0 for i in range(n): G = gcd(G, arr[i]) for i in range(n): g = gcd(g, arr[i]) if (g == G): count += 1 g = 0 if (count >= m): return "Yes" return "No"# Driver codeif __name__ == "__main__": A = [1, 2, 3, 4, 5] N = 5 K = 3 # Function call print(find(A, N, K))# This code is contributed by Rohit Pradhan |
C#
// C# code to implement the approachusing System;public class GFG { // Function to find gcd of two numbers public static int gcd(int a, int b) { if (b == 0) { return a; } return gcd(b, a % b); } // Function to find check whether // non-overlapping subarray exists static String find(int[] arr, int n, int m) { int G = 0; int g = 0; int count = 0; for (int i = 0; i < n; i++) { G = gcd(G, arr[i]); } for (int i = 0; i < n; i++) { // arr[i] = sc.nextInt(); g = gcd(g, arr[i]); if (g == G) { count++; g = 0; } } if (count >= m) return "Yes"; return "No"; } static public void Main() { // Code int[] A = { 1, 2, 3, 4, 5 }; int N = A.Length; int K = 3; // Function call Console.WriteLine(find(A, N, K)); }}// This code is contributed by lokeshmvs21. |
Javascript
// Javascript code to implement the approach// Function to find gcd of two numbers function gcd(a, b){ // Everything divides 0 if(b == 0){ return a; } return gcd(b, a % b);}// Function to find check whether// non-overlapping subarray existsfunction find(arr, n, m){ let G = 0; let g = 0; let count = 0; for (let i = 0; i < n; i++) { G = gcd(G, arr[i]); } for (let i = 0; i < n; i++) { g = gcd(g, arr[i]); if (g == G) { count++; g = 0; } } if (count >= m) return "Yes"; return "No"; }// Driver codelet A = [ 1, 2, 3, 4, 5 ];let N = A.length;let K = 3; // Function callconsole.log(find(A, N, K));// This code is contributed by aarohirai2616. |
Output
Yes
Time Complexity: O(N * log(K)) where K is the maximum element of A[]
Auxiliary Space: O(log(min(a,b))
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
