The maximum number of subarrays

Problem Statement

The maximum number of subarrays Problem Description You are given an integer array A of size N. You have to find the maximum number of non-overlapping subarrays whose size is greater than 0 such that the greatest common divisor of all the subarray equals to 1. The subarray of array A is a contiguous part of array A, that is, arrays A i , A i+1 , ..., A j where 1 ≤ i ≤ j ≤ N. Recall, the greatest common divisor (GCD) of two integers, is the largest positive integer that divides each of the integers. For two integers x, y, the greatest common divisor of x and y is denoted as gcd(x, y). For example, the gcd of 8 and 12 is 4, that is, gcd(8, 12) = 4. Note: Assume 1-based indexing of array A. For each test case, print a single integer in a new line representing the maximum number of subarrays. Examples Example 1: Input: N = 5 A = [2,2,2,2,2] Output: 0 Explanation: In the first testcase, we don't have any subarray, whose GCD is equal to 1. Example 2: Input: N = 2 A = [1,1] Output: 2