Number of Subarrays With LCM Equal to K

Medium
1164.

Number of Subarrays With LCM Equal to K

Number of Subarrays With LCM Equal to K is a medium coding problem on arrays, math and number theory, asked in Amazon and Google interviews.

Given an integer array nums and an integer k, return the number of subarrays (contiguous, non-empty) whose elements have a least common multiple equal to k.

The least common multiple of a set of numbers is the smallest positive integer divisible by every one of them.

Example 1

Input
nums = [2,6,3,1,4], k = 6
Output
6
Explanation
`[2,6]`, `[2,6,3]`, `[2,6,3,1]`, `[6]`, `[6,3]` and `[6,3,1]`. Anything containing the `4` has LCM 12 or more.

Example 2

Input
nums = [7], k = 1
Output
0

Constraints

  • 1 <= nums.length <= 1000
  • 1 <= nums[i], k <= 1000
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var subarrayLCM = function(nums, k) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Number of Subarrays With LCM Equal to K — Problem & Solution

Number of Subarrays With LCM Equal to K solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Number of Subarrays With LCM Equal to K is a medium coding problem on arrays, math and number theory, asked in Amazon and Google interviews.

  • Difficulty: Medium
  • Topics: Arrays, Math, Number Theory
  • Asked at: Amazon, Google
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

Given an integer array nums and an integer k, return the number of subarrays (contiguous, non-empty) whose elements have a least common multiple equal to k.

The least common multiple of a set of numbers is the smallest positive integer divisible by every one of them.

Example 1

Input: nums = [2,6,3,1,4], k = 6
Output: 6
Explanation: `[2,6]`, `[2,6,3]`, `[2,6,3,1]`, `[6]`, `[6,3]` and `[6,3,1]`. Anything containing the `4` has LCM 12 or more.

Example 2

Input: nums = [7], k = 1
Output: 0

Constraints

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

Hints for Number of Subarrays With LCM Equal to K

  1. Hint 1

    Fix the left end and extend to the right, updating the LCM incrementally: lcm(a, b) = a / gcd(a, b) * b.

  2. Hint 2

    If some element does not divide k, no subarray containing it can have LCM k.

  3. Hint 3

    Stop extending as soon as the running LCM no longer divides k — this also keeps every value at most k, so nothing overflows.

How to solve Number of Subarrays With LCM Equal to K

The LCM of a growing subarray only grows (each new value is a multiple of the old one). Once it stops dividing k it can never come back to k, so each start only extends while the LCM is a divisor of k.

Approach

  1. For each start i, set l = 1.
  2. For j = i..n-1, update l = l / gcd(l, nums[j]) * nums[j].
  3. If k % l != 0, break.
  4. If l == k, count the subarray.

Why it works

Extending a subarray replaces its LCM by a multiple of it. If l does not divide k, no multiple of l divides k either, so k is unreachable and breaking loses nothing. Before the break every l divides k, so it is at most k and the products stay small.

Complexity

  • Time — O(n^2 log k)
  • Space — O(1)

Pitfalls

  • Without the early break the LCM of a long subarray overflows 64-bit integers quickly.
  • Divide before multiplying (l / gcd * x) to keep the intermediate small.
  • Start the running LCM at 1, the identity for LCM.

Reference solution

Python

from typing import List
from math import gcd

def subarrayLCM(nums: List[int], k: int) -> int:
    n = len(nums)
    count = 0
    for i in range(n):
        l = 1
        for j in range(i, n):
            l = l // gcd(l, nums[j]) * nums[j]
            if k % l != 0:
                break
            if l == k:
                count += 1
    return count

Java

static int gcdLcm(int a, int b) {
    while (b != 0) { int t = a % b; a = b; b = t; }
    return a;
}

public static int subarrayLCM(int[] nums, int k) {
    int n = nums.length, count = 0;
    for (int i = 0; i < n; i++) {
        int l = 1;
        for (int j = i; j < n; j++) {
            l = l / gcdLcm(l, nums[j]) * nums[j];
            if (k % l != 0) break;
            if (l == k) count++;
        }
    }
    return count;
}

C++

static int gcdLcm(int a, int b) {
    while (b != 0) { int t = a % b; a = b; b = t; }
    return a;
}

int subarrayLCM(vector<int>& nums, int k) {
    int n = nums.size(), count = 0;
    for (int i = 0; i < n; i++) {
        int l = 1;
        for (int j = i; j < n; j++) {
            l = l / gcdLcm(l, nums[j]) * nums[j];
            if (k % l != 0) break;
            if (l == k) count++;
        }
    }
    return count;
}

JavaScript

var subarrayLCM = function(nums, k) {
    var gcd = function(a, b) {
        while (b !== 0) { var t = a % b; a = b; b = t; }
        return a;
    };
    var n = nums.length, count = 0;
    for (var i = 0; i < n; i++) {
        var l = 1;
        for (var j = i; j < n; j++) {
            l = l / gcd(l, nums[j]) * nums[j];
            if (k % l !== 0) break;
            if (l === k) count++;
        }
    }
    return count;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays