Number of subarrays with lcm equal to k

Array Math Number Theory

43.4% acceptance

Feb 25, 2026

384

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.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn subarray_lcm(nums: Vec<i32>, k: i32) -> i32 {
    fn gcd(a: i32, b: i32) -> i32 { if b == 0 { a } else { gcd(b, a % b) } }
    fn lcm(a: i32, b: i32) -> i32 { a / gcd(a, b) * b }

    let n = nums.len();
    let mut count = 0;
    for i in 0..n {
      let mut cur = nums[i];
      for j in i..n {
        cur = lcm(cur, nums[j]);
        if cur > k { break; }
        if cur == k { count += 1; }
      }
    }
    count
  }
}