2447. Number of Subarrays With GCD Equal to K

Medium

368

57

Given an integer array `nums`

and an integer `k`

, return *the number of subarrays of *

`nums`

`k`

.A **subarray** is a contiguous non-empty sequence of elements within an array.

The **greatest common divisor of an array** is the largest integer that evenly divides all the array elements.

**Example 1:**

Input:nums = [9,3,1,2,6,3], k = 3Output:4Explanation:The subarrays of nums where 3 is the greatest common divisor of all the subarray's elements are: - [9,,1,2,6,3] - [9,3,1,2,6,3] - [3,1,2,6,3] - [9,3,1,2,9,3]6,3

**Example 2:**

Input:nums = [4], k = 7Output:0Explanation:There are no subarrays of nums where 7 is the greatest common divisor of all the subarray's elements.

**Constraints:**

`1 <= nums.length <= 1000`

`1 <= nums[i], k <= 10`

^{9}

Accepted

20.3K

Submissions

41.7K

Acceptance Rate

48.7%

Seen this question in a real interview before?

1/4

Yes

No

Discussion (0)

Related Topics

Copyright ©️ 2023 LeetCode All rights reserved