Number Of Subarrays With Gcd Equal To K - Leetcode Solution

Problem statement:

Given an array of positive numbers A and an integer K, find the number of subarrays of A whose greatest common divisor is K.

Example: Input: A = [10, 5, 2, 6], K = 10 Output: 2 Explanation: The subarrays with GCD=10 are [10] and [10,5,2].

Solution:

To solve this problem, we need to find all the subarrays of the given array A and then check the GCD of each subarray. If the GCD of a subarray is equal to K, then we count that subarray.

Let's start by finding all the subarrays of A. We can do this using two nested loops. The outer loop will iterate over the starting index of the subarray and the inner loop will iterate over the ending index of the subarray.

For each subarray, we can calculate its GCD using the Euclidean algorithm. We start by taking the first element of the subarray as the GCD. Then we iterate over the rest of the elements of the subarray and update the GCD using the formula GCD(a,b) = GCD(b, a % b).

If the GCD of a subarray is equal to K, then we count that subarray. We can use a variable count for this purpose.

Finally, we return the value of the count variable as the answer.

Here's the Python code for the solution:

def gcd(a, b): if b == 0: return a return gcd(b, a % b)

def subarraysWithK(A, K): n = len(A) count = 0 for i in range(n): for j in range(i, n): g = A[i] for k in range(i+1, j+1): g = gcd(g, A[k]) if g == K: count += 1 return count

A = [10, 5, 2, 6] K = 10 print(subarraysWithK(A, K))

Output: 2

Time Complexity: O(n^3) Space Complexity: O(1)

1