Leetcode: 2447. Number of Subarrays With GCD Equal to K

Problem Statement

Understand the problem

Given an array of integers \(a\) and an integer \(k\), find all subarrays \(a[i..j]\) where \(gcd(a[i], a[i+1], ..., a[j])=k\).

Devise a plan

Pattern: Small constraints could allow a brute-force solution, so iterate over all subarrays and compute GCD.

Carry out the plan

class Solution:
    def subarrayGCD(self, nums: List[int], k: int) -> int:
        N = len(nums)
        ans = 0
        for i in range(N):
            if nums[i] == k:
                ans += 1
            cur = nums[i]
            for j in range(i + 1, N):
                cur = math.gcd(cur, nums[j])
                if cur == k:
                    ans += 1
        return ans