What is the primary approach to solving the "Number of Subarrays With GCD Equal to K" problem?

The primary approach involves checking subarrays for their GCD and comparing it to the given value k, with optimizations such as the sliding window technique.

How can I optimize the brute-force solution for the Number of Subarrays With GCD Equal to K?

One way to optimize the brute-force approach is by using a sliding window to dynamically calculate the GCD as you iterate through the array, reducing redundant calculations.

What are common mistakes when solving the "Number of Subarrays With GCD Equal to K" problem?

Common mistakes include inefficient brute-force solutions, skipping edge cases, and misunderstanding how to calculate the GCD of subarrays correctly.

How does the sliding window technique work in the Number of Subarrays With GCD Equal to K?

The sliding window technique works by progressively calculating the GCD for elements within the window, moving the window across the array and checking if the GCD equals k.

How can mathematical properties of GCD be applied to optimize solving this problem?

Mathematical properties, such as recognizing when GCD exceeds k or leveraging known divisibility rules, can reduce unnecessary subarray checks and speed up the process.

#2447

Medium

auto_awesome数组·数学

LeetCode 题解工作台

最大公因数等于 K 的子数组数目

给你一个整数数组 nums 和一个整数 k ，请你统计并返回 nums 的子数组中元素的最大公因数等于 k 的子数组数目。子数组是数组中一个连续的非空序列。数组的最大公因数是能整除数组中所有元素的最大整数。示例 1：输入： nums = [9,3,1,2,6,3], k = 3 输出： …

数组数学数论

题目描述

给你一个整数数组 nums 和一个整数 k ，请你统计并返回 nums 的子数组中元素的最大公因数等于 k 的子数组数目。

子数组 是数组中一个连续的非空序列。

数组的最大公因数 是能整除数组中所有元素的最大整数。

示例 1：

输入：nums = [9,3,1,2,6,3], k = 3
输出：4
解释：nums 的子数组中，以 3 作为最大公因数的子数组如下：
- [9,3,1,2,6,3]
- [9,3,1,2,6,3]
- [9,3,1,2,6,3]
- [9,3,1,2,6,3]

示例 2：

输入：nums = [4], k = 7
输出：0
解释：不存在以 7 作为最大公因数的子数组。

提示：

1 <= nums.length <= 1000
1 <= nums[i], k <= 10⁹

lightbulb

解题思路

方法一：直接枚举

我们可以枚举 $nums[i]$ 作为子数组的左端点，然后枚举 $nums[j]$ 作为子数组的右端点，其中 $i \le j$ 。在枚举右端点的过程中，我们可以用一个变量 $g$ 来维护当前子数组的最大公因数，每次枚举到一个新的右端点时，我们更新最大公因数 $g = \gcd(g, nums[j])$ 。如果 $g=k$ ，那么当前子数组的最大公因数等于 $k$ ，我们就将答案增加 $1$ 。

枚举结束后，返回答案即可。

时间复杂度 $O(n \times (n + \log M))$ ，其中 $n$ 和 $M$ 分别是数组 $nums$ 的长度和数组 $nums$ 中的最大值。

1

2

3

4

5

6

7

8

9

10

class Solution:
    def subarrayGCD(self, nums: List[int], k: int) -> int:
        ans = 0
        for i in range(len(nums)):
            g = 0
            for x in nums[i:]:
                g = gcd(g, x)
                ans += g == k
        return ans

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Candidate identifies that brute-force approach may not scale well and proposes optimizations.
question_mark
Candidate suggests using sliding window technique for efficiency, ensuring correctness with GCD checks.
question_mark
Candidate mentions mathematical insights into GCD that could simplify the problem or reduce unnecessary work.

warning

常见陷阱

外企场景

error
Overlooking the need to calculate GCD for every subarray, leading to inefficiency.
error
Failure to recognize when GCD exceeds k, causing unnecessary subarray checks.
error
Confusing the greatest common divisor calculation with other operations, leading to incorrect results.

swap_horiz

进阶变体

外企场景

arrow_right_alt
What if the array contains repeated elements? How does this affect GCD calculations?
arrow_right_alt
How would the problem change if we had to check subarrays with GCD greater than k instead?
arrow_right_alt
Consider handling edge cases like a single element array or when k is greater than any element.

help

常见问题

外企场景

继续练习

#2470 最小公倍数等于 K 的子数组数目 #2521 数组乘积中的不同质因数数目 #2344 使数组可以被整除的最少删除次数