Jobs

Interviews

Discussions

Number of Subarrays With GCD Equal to K

Medium

Asked by:

15 views

Topics:

ArraysGreedy Algorithms

Given an integer array nums and an integer k, return the number of subarrays of nums where the greatest common divisor of the subarray's elements is 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 = 3
Output: 4
Explanation: The subarrays of nums where 3 is the greatest common divisor of all the subarray's elements are:
- [9,3,1,2,6,3]
- [9,3,1,2,6,3]
- [9,3,1,2,6,3]
- [9,3,1,2,6,3]

Example 2:

Input: nums = [4], k = 7
Output: 0
Explanation: 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⁹

Try coding it in LeetCode

Number of Subarrays With GCD Equal to K

Medium

Asked by:

15 views

Topics:

ArraysGreedy Algorithms

Given an integer array nums and an integer k, return the number of subarrays of nums where the greatest common divisor of the subarray's elements is 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 = 3
Output: 4
Explanation: The subarrays of nums where 3 is the greatest common divisor of all the subarray's elements are:
- [9,3,1,2,6,3]
- [9,3,1,2,6,3]
- [9,3,1,2,6,3]
- [9,3,1,2,6,3]

Example 2:

Input: nums = [4], k = 7
Output: 0
Explanation: 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⁹

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 possible ranges for the values within the input array and the value of K?
Can the input array contain zero or negative numbers?
What should I return if no subarrays have a GCD equal to K?
Does the order of the subarrays in my counting matter, or is it only the number of subarrays that's important?
Is K guaranteed to be a positive integer?

Brute Force Solution

Approach

The brute force method for this problem involves checking every possible group of numbers within the given set. We calculate the greatest common divisor (GCD) for each group and count how many of these GCDs match our target value. It's like exhaustively trying every combination to find the ones that work.

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

Consider each number as the beginning of a possible group.
For each starting number, extend the group by one number at a time.
With each extension, calculate the greatest common divisor (GCD) of all the numbers in the current group.
Compare the calculated GCD to the target value.
If the GCD matches the target value, increase the count.
Repeat this process for all possible starting numbers and group sizes.
The final count represents the total number of groups whose GCD equals the target value.

Code Implementation

def number_of_subarrays_with_gcd_equal_to_k_brute_force(numbers, target):
    number_of_subarrays = 0

    for start_index in range(len(numbers)):
        current_gcd = 0
        for end_index in range(start_index, len(numbers)):
            # Need to calculate GCD of the current subarray.
            current_gcd = numbers[end_index] if current_gcd == 0 else greatest_common_divisor(current_gcd, numbers[end_index])

            # Check if GCD is equal to target.
            if current_gcd == target:
                number_of_subarrays += 1

    return number_of_subarrays

def greatest_common_divisor(first_number, second_number):
    #Euclid's algorithm to calculate GCD
    while(second_number):
        first_number, second_number = second_number, first_number % second_number

    return first_number

Big(O) Analysis

Time Complexity

O(n²) – The algorithm iterates through all possible subarrays of the input array of size n. For each starting index, the algorithm iterates through all possible ending indices to form a subarray. Calculating the GCD for each subarray takes O(log(min(subarray))) which is O(log(max element)). Since we perform GCD calculations on O(n²) subarrays, and GCD calculation is less than O(n), the dominant factor is the nested loops, giving us approximately n * n/2 operations. Thus, the overall time complexity is O(n²).

Space Complexity

O(1) – The brute force method calculates the GCD of subarrays on the fly without storing the subarrays themselves. It uses a constant amount of extra space for variables like the current GCD being computed and the loop indices, regardless of the input array's size, N. Therefore, the auxiliary space complexity is O(1) as it does not scale with the input size.

Optimal Solution

Approach

The core idea is to find all the continuous sections within the list of numbers where the greatest common divisor (GCD) is exactly the target number. Instead of checking every possible section, we use a method that efficiently calculates the GCD of each section as we go, and only count the sections that match our target.

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

Start by looking at each number in the list, one by one.
For each number, consider it as the possible start of a valid section.
Calculate the GCD of this first number.
Now, extend the section by adding the next number in the list.
Recalculate the GCD of the expanded section. This can be done efficiently by using the GCD of the previous section and the newly added number.
If the GCD of the section is equal to the target number, increase the count of valid sections.
If the GCD is smaller than the target number, there's no need to continue extending this section because the GCD can only decrease or stay the same when you add more numbers.
Repeat steps 4-7 until you reach the end of the list or until the GCD becomes smaller than the target.
Move on to the next number in the original list and treat it as the start of a new section and repeat the process from step 3.
By following this approach, you only check sections that have the potential to have the target GCD, avoiding unnecessary calculations.

Code Implementation

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

def number_of_subarrays_with_gcd_equal_to_k(number_list, target_gcd):
    subarray_count = 0
    list_length = len(number_list)

    for start_index in range(list_length):
        current_gcd = 0

        # Consider each element as start of subarray
        for end_index in range(start_index, list_length):
            if current_gcd == 0:
                current_gcd = number_list[end_index]
            else:
                # Update GCD with current element
                current_gcd = greatest_common_divisor(current_gcd, number_list[end_index])

            # If GCD is less than target_gcd, break
            if current_gcd < target_gcd:
                break

            if current_gcd == target_gcd:
                # Count the subarray if GCD equals target
                subarray_count += 1

    return subarray_count

Big(O) Analysis

Time Complexity

O(n^2) – The outer loop iterates through each of the n elements of the input array nums. The inner loop, for each element, expands a subarray, calculating the GCD. The worst-case scenario is that the inner loop iterates through the remaining elements (up to n). The GCD calculation itself takes constant time. Thus, in the worst case, the algorithm performs approximately n * n GCD calculations, leading to a time complexity of O(n^2).

Space Complexity

O(1) – The algorithm iterates through the input array but only uses a few integer variables to store the current GCD and loop counters. The number of these variables does not depend on the size of the input array, denoted as N. Therefore, the auxiliary space remains constant regardless of the input size. The space complexity is O(1).

Edge Cases

Case	How to Handle
Null or Empty Array	Return 0, as no subarrays can be formed.
Array with a single element	Check if the single element equals k, return 1 if true, 0 otherwise.
Array where all elements are multiples of k	The algorithm should correctly count all subarrays whose GCD reduces to k.
Array where no subarray has GCD equal to k	The algorithm should return 0.
Large input array (potential performance bottleneck)	Ensure GCD calculation is optimized for speed, possibly using precomputed GCDs or other optimizations if necessary, and avoid recalculating the GCD of the same range repeatedly.
k = 0	If k is zero, return the number of subarrays whose elements are all zero, or zero if the array contains no zeros; handle the special case where GCD(x, 0) = x.
k > max(array)	Return 0, as GCD cannot be greater than any element in the array.
Array contains large numbers leading to integer overflow in GCD calculation	Use appropriate data types (e.g., long) to prevent integer overflow during GCD calculations.

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 possible ranges for the values within the input array and the value of K?
Can the input array contain zero or negative numbers?
What should I return if no subarrays have a GCD equal to K?
Does the order of the subarrays in my counting matter, or is it only the number of subarrays that's important?
Is K guaranteed to be a positive integer?

Brute Force Solution

Approach

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

Consider each number as the beginning of a possible group.
For each starting number, extend the group by one number at a time.
With each extension, calculate the greatest common divisor (GCD) of all the numbers in the current group.
Compare the calculated GCD to the target value.
If the GCD matches the target value, increase the count.
Repeat this process for all possible starting numbers and group sizes.
The final count represents the total number of groups whose GCD equals the target value.

Code Implementation

def number_of_subarrays_with_gcd_equal_to_k_brute_force(numbers, target):
    number_of_subarrays = 0

    for start_index in range(len(numbers)):
        current_gcd = 0
        for end_index in range(start_index, len(numbers)):
            # Need to calculate GCD of the current subarray.
            current_gcd = numbers[end_index] if current_gcd == 0 else greatest_common_divisor(current_gcd, numbers[end_index])

            # Check if GCD is equal to target.
            if current_gcd == target:
                number_of_subarrays += 1

    return number_of_subarrays

def greatest_common_divisor(first_number, second_number):
    #Euclid's algorithm to calculate GCD
    while(second_number):
        first_number, second_number = second_number, first_number % second_number

    return first_number

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

Start by looking at each number in the list, one by one.
For each number, consider it as the possible start of a valid section.
Calculate the GCD of this first number.
Now, extend the section by adding the next number in the list.
Recalculate the GCD of the expanded section. This can be done efficiently by using the GCD of the previous section and the newly added number.
If the GCD of the section is equal to the target number, increase the count of valid sections.
If the GCD is smaller than the target number, there's no need to continue extending this section because the GCD can only decrease or stay the same when you add more numbers.
Repeat steps 4-7 until you reach the end of the list or until the GCD becomes smaller than the target.
Move on to the next number in the original list and treat it as the start of a new section and repeat the process from step 3.
By following this approach, you only check sections that have the potential to have the target GCD, avoiding unnecessary calculations.

Code Implementation

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

def number_of_subarrays_with_gcd_equal_to_k(number_list, target_gcd):
    subarray_count = 0
    list_length = len(number_list)

    for start_index in range(list_length):
        current_gcd = 0

        # Consider each element as start of subarray
        for end_index in range(start_index, list_length):
            if current_gcd == 0:
                current_gcd = number_list[end_index]
            else:
                # Update GCD with current element
                current_gcd = greatest_common_divisor(current_gcd, number_list[end_index])

            # If GCD is less than target_gcd, break
            if current_gcd < target_gcd:
                break

            if current_gcd == target_gcd:
                # Count the subarray if GCD equals target
                subarray_count += 1

    return subarray_count

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or Empty Array	Return 0, as no subarrays can be formed.
Array with a single element	Check if the single element equals k, return 1 if true, 0 otherwise.
Array where all elements are multiples of k	The algorithm should correctly count all subarrays whose GCD reduces to k.
Array where no subarray has GCD equal to k	The algorithm should return 0.
Large input array (potential performance bottleneck)	Ensure GCD calculation is optimized for speed, possibly using precomputed GCDs or other optimizations if necessary, and avoid recalculating the GCD of the same range repeatedly.
k = 0	If k is zero, return the number of subarrays whose elements are all zero, or zero if the array contains no zeros; handle the special case where GCD(x, 0) = x.
k > max(array)	Return 0, as GCD cannot be greater than any element in the array.
Array contains large numbers leading to integer overflow in GCD calculation	Use appropriate data types (e.g., long) to prevent integer overflow during GCD calculations.