Skip to content

2470. Number of Subarrays With LCM Equal to K

SourceWeekly Contest 319 Q2DifficultyMediumRating1559

Description

Given an integer array nums and an integer k, return the number of subarrays of nums where the least common multiple of the subarray's elements is k.

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

The least common multiple of an array is the smallest positive integer that is divisible by all the array elements.

 

Example 1:

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

Example 2:

Input: nums = [3], k = 2
Output: 0
Explanation: There are no subarrays of nums where 2 is the least common multiple of all the subarray's elements.

 

Constraints:

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

Solutions

Solution 1: Enumeration

Thinking

With \(n \le 1000\), fix the left end and extend to the right. A subarray whose LCM is \(k\) can contain only divisors of \(k\), so the first element that does not divide \(k\) ends the segment. Until then the running LCM itself divides \(k\) and stays at most \(k\). Multiplying before dividing by the GCD overflows a 32-bit product even when the true LCM still fits, and the wrapped value can equal \(k\).

Enumerate each index as the left end and extend to the right. Stop at the first value that does not divide \(k\). While extending, the running LCM stays a divisor of \(k\); count the positions where it equals \(k\).

The time complexity is \(O(n^2)\). Here, \(n\) is the length of the array.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
from math import lcm


class Solution:
    def subarrayLCM(self, nums: List[int], k: int) -> int:
        ans = 0
        for i in range(len(nums)):
            a = 1
            for b in nums[i:]:
                if k % b:
                    break
                a = lcm(a, b)
                ans += a == k
        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
class Solution {
    public int subarrayLCM(int[] nums, int k) {
        int ans = 0;
        for (int i = 0; i < nums.length; ++i) {
            int a = 1;
            for (int j = i; j < nums.length; ++j) {
                if (k % nums[j] != 0) {
                    break;
                }
                a = lcm(a, nums[j]);
                if (a == k) {
                    ++ans;
                }
            }
        }
        return ans;
    }

    private int lcm(int a, int b) {
        return a / gcd(a, b) * b;
    }

    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
class Solution {
public:
    int subarrayLCM(vector<int>& nums, int k) {
        int ans = 0;
        for (int i = 0; i < nums.size(); ++i) {
            int a = 1;
            for (int j = i; j < nums.size(); ++j) {
                if (k % nums[j] != 0) {
                    break;
                }
                a = lcm(a, nums[j]);
                ans += a == k;
            }
        }
        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
func subarrayLCM(nums []int, k int) (ans int) {
    for i := range nums {
        a := 1
        for _, b := range nums[i:] {
            if k%b != 0 {
                break
            }
            a = lcm(a, b)
            if a == k {
                ans++
            }
        }
    }
    return
}

func gcd(a, b int) int {
    if b == 0 {
        return a
    }
    return gcd(b, a%b)
}

func lcm(a, b int) int {
    return a / gcd(a, b) * b
}

Comments