2447. Number of Subarrays With GCD Equal to K

• Time: $O(n\log(\min(\texttt{nums})))$
• Space: $O(n)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 class Solution { public: int subarrayGCD(vector& nums, int k) { int ans = 0; unordered_map gcds; for (const int num : nums) if (num % k == 0) { unordered_map nextGcds{{num, 1}}; for (const auto& [prevGcd, count] : gcds) nextGcds[gcd(prevGcd, num)] += count; ans += nextGcds[k]; gcds = move(nextGcds); } else { // The GCD streak stops, so fresh start from the next num. gcds.clear(); } return ans; } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 class Solution { public int subarrayGCD(int[] nums, int k) { int ans = 0; Map gcds = new HashMap<>(); for (final int num : nums) if (num % k == 0) { Map nextGcds = new HashMap<>(); nextGcds.put(num, 1); for (Map.Entry entry : gcds.entrySet()) { final int prevGcd = entry.getKey(); final int count = entry.getValue(); nextGcds.merge(gcd(prevGcd, num), count, Integer::sum); } ans += nextGcds.getOrDefault(k, 0); gcds = nextGcds; } else { // The GCD streak stops, so fresh start from the next num. gcds.clear(); } return ans; } private int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 class Solution: def subarrayGCD(self, nums: List[int], k: int) -> int: ans = 0 gcds = collections.Counter() for num in nums: if num % k == 0: nextGcds = collections.defaultdict(int) nextGcds[num] += 1 for prevGcd, count in gcds.items(): nextGcds[math.gcd(prevGcd, num)] += count ans += nextGcds.get(k, 0) gcds = nextGcds else: # The GCD streak stops, so fresh start from the next num. gcds.clear() return ans