Jobs

Interviews

Discussions

Number of Subarrays With LCM Equal to K

Medium

Asked by:

0 views

Topics:

ArraysSliding Windows

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

Try coding it in LeetCode

Number of Subarrays With LCM Equal to K

Medium

Asked by:

0 views

Topics:

ArraysSliding Windows

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

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the constraints on the size of the input array `nums` and the value of `k`? Specifically, what are the maximum possible values?
Can the elements in the `nums` array be zero or negative?
If no subarrays have an LCM equal to `k`, what value should I return?
Are all the numbers in `nums` and `k` guaranteed to be integers, or do I need to handle floating-point numbers?
If there are multiple subarrays with the same LCM equal to `k`, should I count overlapping subarrays or only distinct ones?

Brute Force Solution

Approach

The simplest way to solve this is to check every possible group of numbers within the given list. We'll calculate the Least Common Multiple (LCM) for each of these groups and then count how many of those LCMs are equal to our target number.

Here's how the algorithm would work step-by-step:

Consider every possible starting point in the list of numbers.
For each starting point, look at all possible groups of consecutive numbers beginning from there. Start with a group of size one, then two, then three, and so on until you reach the end of the list.
For each group of numbers you've created, calculate their Least Common Multiple.
Compare the Least Common Multiple you just calculated to the target number.
If the calculated Least Common Multiple equals the target number, increase a counter.
After checking every possible group of numbers, the counter will hold the total number of groups whose Least Common Multiple equals the target number. That's our answer.

Code Implementation

def number_of_subarrays_with_lcm_equal_to_k(numbers, target_lcm):
    subarray_count = 0
    array_length = len(numbers)

    def calculate_lcm(group_of_numbers):
        least_common_multiple = group_of_numbers[0]
        for i in range(1, len(group_of_numbers)):
            least_common_multiple = (least_common_multiple * group_of_numbers[i]) // find_gcd(least_common_multiple, group_of_numbers[i])
        return least_common_multiple

    def find_gcd(first_number, second_number):
        while(second_number):
            first_number, second_number = second_number, first_number % second_number
        return first_number

    # Iterate through all possible start indices
    for start_index in range(array_length):
        # Iterate through all possible end indices for each start index
        for end_index in range(start_index, array_length):
            current_subarray = numbers[start_index : end_index + 1]

            # Calculate the LCM of the current subarray
            lcm_of_subarray = calculate_lcm(current_subarray)

            # Check if the LCM is equal to the target
            if lcm_of_subarray == target_lcm:
                # Increment the count if LCM matches
                subarray_count += 1

    return subarray_count

Big(O) Analysis

Time Complexity

O(n³) – The algorithm iterates through all possible subarrays of the input array of size n. The outer loop selects the starting index, which takes O(n) time. The inner loop iterates through all possible ending indices from the selected starting index, also taking O(n) time. For each subarray, we calculate the LCM which, in the worst case, could take O(n) time where n is the length of the subarray because we must iterate through the subarray to find the LCM. Thus, the overall time complexity is O(n * n * n) which simplifies to O(n³).

Space Complexity

O(1) – The algorithm iterates through subarrays calculating the Least Common Multiple (LCM) on the fly. While the LCM calculation itself might involve intermediate computations, these are performed on a fixed number of variables. No auxiliary data structures like arrays or hash maps are used to store intermediate results of varying sizes based on the input list of numbers of size N. Therefore, the auxiliary space complexity is constant.

Optimal Solution

Approach

The most efficient way to count subarrays with a specific least common multiple (LCM) is to examine each possible subarray once. For each subarray, calculate its LCM and check if it matches the target. An important optimization is to stop calculating the LCM for a given subarray as soon as the LCM exceeds the target, since that subarray and all its extensions will also exceed the target LCM.

Here's how the algorithm would work step-by-step:

Consider each element in the given set as a potential starting point for a subarray.
For each starting element, expand the subarray by adding one element at a time to the right.
With each element added, calculate the LCM of the current subarray.
If the calculated LCM is equal to the target LCM, increment the count of valid subarrays.
If the calculated LCM exceeds the target LCM, stop expanding the current subarray because any further expansion will also have an LCM greater than the target.
Continue this process for all possible starting positions and all possible subarray expansions until the entire set is explored.
The final count represents the total number of subarrays with an LCM equal to the target LCM.

Code Implementation

def find_number_of_subarrays_with_lcm_equal_to_k(numbers, target_lcm):
    subarray_count = 0
    list_length = len(numbers)

    for start_index in range(list_length):
        current_lcm = 1

        for end_index in range(start_index, list_length):
            current_lcm = calculate_lcm(current_lcm, numbers[end_index])

            # If the LCM exceeds the target, stop.
            if current_lcm > target_lcm:
                break

            if current_lcm == target_lcm:
                subarray_count += 1

    return subarray_count

def calculate_gcd(number_one, number_two):
    while(number_two):
        number_one, number_two = number_two, number_one % number_two
    return number_one

def calculate_lcm(number_one, number_two):
    # We need GCD to calculate LCM.
    return (number_one * number_two) // calculate_gcd(number_one, number_two)

# Example usage (not part of the solution, for demonstration):
# numbers = [2, 4, 8, 2, 4]
# target_lcm = 4
# result = find_number_of_subarrays_with_lcm_equal_to_k(numbers, target_lcm)
# print(f"Number of subarrays with LCM equal to {target_lcm}: {result}")

Big(O) Analysis

Time Complexity

O(n²) – The outer loop iterates through each of the n elements of the input array as a starting point for a subarray. The inner loop expands each subarray to the right, potentially iterating up to n times in the worst case. Calculating the LCM within the inner loop takes constant time relative to n, although the cost of LCM increases with the size of the numbers. Therefore, we have a nested loop structure where the outer loop runs n times and the inner loop, in the worst case, also runs n times, making it approximately n * n operations, which simplifies to O(n²).

Space Complexity

O(1) – The algorithm iterates through subarrays, calculating the LCM on the fly. It doesn't store intermediate subarrays or a significant number of variables related to the input size, N. The LCM calculation itself uses a constant amount of space, regardless of N. Therefore, the auxiliary space used is constant, independent of the input size, leading to a space complexity of O(1).

Edge Cases

Case	How to Handle
Empty input array (nums is null or has length 0)	Return 0, as there are no subarrays in an empty array.
Single element array where the single element is equal to k	Return 1, as the single element subarray satisfies the condition.
Single element array where the single element is not equal to k	Return 0, as the single element subarray does not satisfy the condition.
Array contains a number 0	LCM of any subarray containing 0 will be 0, return 0 if k is not 0, or handle the case where k is 0.
Array contains very large numbers that might cause integer overflow when calculating LCM	Use a data type with larger capacity like long or BigInteger to store LCM, or check for overflow before multiplying.
k is a very large number which cannot be formed by any subarray's LCM	The algorithm should correctly iterate through all subarrays and return 0 as no subarray's LCM equals k.
Array contains only 1s and k is 1	The number of subarrays will be n*(n+1)/2 where n is the array length, so return this value.
Array contains prime numbers greater than k.	If the subarray contains any prime number greater than k, the LCM will always be greater than k, so skip those subarrays.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the constraints on the size of the input array `nums` and the value of `k`? Specifically, what are the maximum possible values?
Can the elements in the `nums` array be zero or negative?
If no subarrays have an LCM equal to `k`, what value should I return?
Are all the numbers in `nums` and `k` guaranteed to be integers, or do I need to handle floating-point numbers?
If there are multiple subarrays with the same LCM equal to `k`, should I count overlapping subarrays or only distinct ones?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Consider every possible starting point in the list of numbers.
For each starting point, look at all possible groups of consecutive numbers beginning from there. Start with a group of size one, then two, then three, and so on until you reach the end of the list.
For each group of numbers you've created, calculate their Least Common Multiple.
Compare the Least Common Multiple you just calculated to the target number.
If the calculated Least Common Multiple equals the target number, increase a counter.
After checking every possible group of numbers, the counter will hold the total number of groups whose Least Common Multiple equals the target number. That's our answer.

Code Implementation

def number_of_subarrays_with_lcm_equal_to_k(numbers, target_lcm):
    subarray_count = 0
    array_length = len(numbers)

    def calculate_lcm(group_of_numbers):
        least_common_multiple = group_of_numbers[0]
        for i in range(1, len(group_of_numbers)):
            least_common_multiple = (least_common_multiple * group_of_numbers[i]) // find_gcd(least_common_multiple, group_of_numbers[i])
        return least_common_multiple

    def find_gcd(first_number, second_number):
        while(second_number):
            first_number, second_number = second_number, first_number % second_number
        return first_number

    # Iterate through all possible start indices
    for start_index in range(array_length):
        # Iterate through all possible end indices for each start index
        for end_index in range(start_index, array_length):
            current_subarray = numbers[start_index : end_index + 1]

            # Calculate the LCM of the current subarray
            lcm_of_subarray = calculate_lcm(current_subarray)

            # Check if the LCM is equal to the target
            if lcm_of_subarray == target_lcm:
                # Increment the count if LCM matches
                subarray_count += 1

    return subarray_count

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Consider each element in the given set as a potential starting point for a subarray.
For each starting element, expand the subarray by adding one element at a time to the right.
With each element added, calculate the LCM of the current subarray.
If the calculated LCM is equal to the target LCM, increment the count of valid subarrays.
If the calculated LCM exceeds the target LCM, stop expanding the current subarray because any further expansion will also have an LCM greater than the target.
Continue this process for all possible starting positions and all possible subarray expansions until the entire set is explored.
The final count represents the total number of subarrays with an LCM equal to the target LCM.

Code Implementation

def find_number_of_subarrays_with_lcm_equal_to_k(numbers, target_lcm):
    subarray_count = 0
    list_length = len(numbers)

    for start_index in range(list_length):
        current_lcm = 1

        for end_index in range(start_index, list_length):
            current_lcm = calculate_lcm(current_lcm, numbers[end_index])

            # If the LCM exceeds the target, stop.
            if current_lcm > target_lcm:
                break

            if current_lcm == target_lcm:
                subarray_count += 1

    return subarray_count

def calculate_gcd(number_one, number_two):
    while(number_two):
        number_one, number_two = number_two, number_one % number_two
    return number_one

def calculate_lcm(number_one, number_two):
    # We need GCD to calculate LCM.
    return (number_one * number_two) // calculate_gcd(number_one, number_two)

# Example usage (not part of the solution, for demonstration):
# numbers = [2, 4, 8, 2, 4]
# target_lcm = 4
# result = find_number_of_subarrays_with_lcm_equal_to_k(numbers, target_lcm)
# print(f"Number of subarrays with LCM equal to {target_lcm}: {result}")

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty input array (nums is null or has length 0)	Return 0, as there are no subarrays in an empty array.
Single element array where the single element is equal to k	Return 1, as the single element subarray satisfies the condition.
Single element array where the single element is not equal to k	Return 0, as the single element subarray does not satisfy the condition.
Array contains a number 0	LCM of any subarray containing 0 will be 0, return 0 if k is not 0, or handle the case where k is 0.
Array contains very large numbers that might cause integer overflow when calculating LCM	Use a data type with larger capacity like long or BigInteger to store LCM, or check for overflow before multiplying.
k is a very large number which cannot be formed by any subarray's LCM	The algorithm should correctly iterate through all subarrays and return 0 as no subarray's LCM equals k.
Array contains only 1s and k is 1	The number of subarrays will be n*(n+1)/2 where n is the array length, so return this value.
Array contains prime numbers greater than k.	If the subarray contains any prime number greater than k, the LCM will always be greater than k, so skip those subarrays.