2447. Number of Subarrays With GCD Equal to K

MediumArrayMathNumber Theory
Leetcode Link

Problem Description

This problem asks us to determine the count of subarrays within a given integer array nums such that the greatest common divisor (GCD) of all the numbers in each subarray equals a specified integer k. A subarray is defined as a contiguous, non-empty sequence of elements from the array. The GCD of an array is the largest integer that divides every element of the array without leaving a remainder.

The task is to explore all possible subarrays within nums and determine which of them have a GCD that matches k. The final output should be the total number of these qualifying subarrays.

Intuition

The intuition behind the solution is based on incrementally verifying every possible subarray. The traditional brute-force approach starts with an index i and iteratively expands to include each subsequent element, recalculating the GCD each time with the new element included. This brute force method works by calculating the GCD of each subarray starting with a single element and expanding the subarray one element at a time, keeping track of the GCD as it grows. If the GCD matches k at any point, that configuration is counted as a valid subarray.

By starting from every possible index i in the array, we ensure that we do not miss any potential subarrays. For each fixed starting index i, we expand the subarray by adding one element at a time to the end, which we denote as x coming from the slice nums[i:] in the code. We keep updating the GCD with the help of the gcd function, which computes the GCD of two numbers.

Whenever the GCD of the current subarray configuration (g) equates to k, we increment our answer (ans) indicating that we have found a subarray that satisfies the given condition. The process then repeats for all start and end index combinations. Although this method has a higher time complexity as it employs nested loops to check all subarrays, it is straightforward and makes use of the mathematical properties of GCD to identify qualifying subarrays.

Learn more about Math patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

How does quick sort divide the problem into subproblems?

Solution Approach

The implemented solution approach relies on a nested loop construct to evaluate each subarray's GCD within the input nums array. The outer loop determines the starting position of the subarray, and the inner loop expands the subarray to include additional elements one by one. Here's a breakdown of how the algorithm operates:

  1. We iterate over the array nums using an outer loop with the index i which defines the start of the subarray. This loop goes from the first element to the last in nums.

  2. For each starting index i, we initialize a variable g which will hold the GCD of the current subarray. Initially, g is set to 0, representing an "empty" subarray state.

  3. We then enter an inner loop starting at i and going to the end of nums. Within this loop, we use the gcd function to calculate the new GCD each time an additional element (x) is included in the subarray. The gcd function is called with the current value of g and the new element x from nums.

  4. The result of the gcd function is then used to update g, which now holds the GCD of the subarray starting at index i and ending at the current position of the inner loop.

  5. If at any point the value of g (the GCD of the current subarray) equals the target value k, we increment a counter variable ans since we've found a qualifying subarray.

  6. After all elements have been considered for the subarray starting with index i, we repeat the process for the next start index.

This approach does not use any sophisticated data structures; it simply depends on two variables—g for tracking the GCD and ans for tracking the count of valid subarrays. The computation leans heavily on the mathematical properties of GCD, particularly that the GCD of any two numbers remains unchanged or becomes smaller when more elements are introduced into the calculation.

The complexity of the solution lies in the nested loops, making the time complexity O(n^2) in the worst case, where n is the length of nums. This occurs because for each starting index, the inner loop could, in the worst case, iterate over the entire array size to form the subarray.

Despite the relatively simple brute-force nature of the approach, it is effective for solving this specific problem. However, for larger arrays or constraints requiring better performance, a more optimized solution would be necessary to reduce the time complexity of the problem.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which type of traversal does breadth first search do?

Example Walkthrough

Let's walk through a small example to illustrate the solution approach. Suppose we have the following input:

1nums = [2, 4, 6, 3, 9]
2k = 3

We want to find all subarrays whose GCD is equal to 3.

  1. Start with i = 0 and g = 0.

    • The subarray starting at index 0 is [2]. The GCD (g) of [2] is 2, which is not equal to k (3).

  2. Increment i to 1 and reset g to 0.

    • The subarray starting at index 1 is [4]. The GCD (g) of [4] is 4, which is not equal to k (3).

  3. Increment i to 2 and reset g to 0.

    • The subarray [6] has a GCD (g) of 6, which is not equal to k (3).
    • Expand the subarray to [6, 3]. The GCD (g) of [6, 3] is 3, which is equal to k. We increment ans to 1.

  4. Increment i to 3 and reset g to 0.

    • The subarray [3] has a GCD (g) of 3, which is equal to k. Increment ans to 2.
    • Expand the subarray to [3, 9]. The GCD (g) of [3, 9] is 3, which is equal to k. Increment ans to 3.

  5. Increment i to 4 and reset g to 0.

    • The subarray [9] has a GCD (g) of 9, which is not equal to k (3).

After checking all possible subarrays, we end up with a total count of 3 subarrays for which the GCD equals k. Hence, ans is 3, and that is our solution.

In this example, the process of expanding subarrays and finding their GCDs demonstrates the straightforward but computationally intensive nature of the algorithm, exemplifying how it operates in practice.

Solution Implementation

1from math import gcd
2from typing import List
3
4class Solution:
5    def subarrayGCD(self, nums: List[int], k: int) -> int:
6        # Initialize the answer to 0.
7        answer = 0
8      
9        # Iterate over the list starting from each index.
10        for i in range(len(nums)):
11            # Initialize gcd accumulator for this subarray to 0.
12            current_gcd = 0
13          
14            # Go through the subsequent numbers to form different subarrays.
15            for x in nums[i:]:
16                # Update the current gcd with the new number included.
17                current_gcd = gcd(current_gcd, x)
18              
19                # If the current gcd equals the target k, increment the count.
20                if current_gcd == k:
21                    answer += 1
22      
23        # Return the total count of subarrays where the gcd is equal to k.
24        return answer
25
1class Solution {
2
3    /**
4     * Counts the number of subarrays that have a GCD equal to k.
5     *
6     * @param nums The array of integers to be checked.
7     * @param k    The GCD value that subarrays need to match.
8     * @return The count of subarrays with GCD equal to k.
9     */
10    public int subarrayGCD(int[] nums, int k) {
11        int length = nums.length; // Use a clearer variable name for array length
12        int count = 0; // Use 'count' to represent the number of valid subarrays
13
14        // Outer loop to iterate over the start of the subarray
15        for (int i = 0; i < length; ++i) {
16            int gcdValue = 0; // This will hold the GCD of the subarray starting at 'i'
17
18            // Inner loop to iterate over the end of the subarray
19            for (int j = i; j < length; ++j) {
20                // Update gcdValue with the current num
21                gcdValue = gcd(gcdValue, nums[j]);
22
23                // Check if the current GCD equals to k; if so, increment the count
24                if (gcdValue == k) {
25                    ++count;
26                }
27            }
28        }
29
30        // Return the total count of subarrays with GCD equal to k
31        return count;
32    }
33
34    /**
35     * Calculates the greatest common divisor (GCD) of two numbers.
36     *
37     * @param a The first number.
38     * @param b The second number.
39     * @return The GCD of a and b.
40     */
41    private int gcd(int a, int b) {
42        return b == 0 ? a : gcd(b, a % b); // Recursive implementation of the Euclidean algorithm
43    }
44}
45
1#include <vector>
2#include <numeric> // For using gcd function
3
4class Solution {
5public:
6    // Function to compute the number of subarrays whose GCD is exactly k
7    int subarrayGCD(vector<int>& nums, int k) {
8        int count = 0; // Variable to store the count of valid subarrays
9        int size = nums.size(); // Get the number of elements in nums
10      
11        // Loop through the starting index of the subarray
12        for (int start = 0; start < size; ++start) {
13            int gcd_value = 0; // Initialize GCD value for this subarray
14          
15            // Expand the subarray towards the right
16            for (int end = start; end < size; ++end) {
17                // Update the GCD of the current subarray
18                gcd_value = std::gcd(gcd_value, nums[end]);
19              
20                // If the GCD matches k, increment the count
21                if (gcd_value == k) {
22                    ++count;
23                }
24            }
25        }
26        // Return the total count of subarrays with GCD equal to k
27        return count;
28    }
29};
30
1/**
2 * Calculates the number of subarrays with a GCD equal to k.
3 * @param {number[]} nums - The array of numbers to be checked.
4 * @param {number} k - The target GCD value for the subarrays.
5 * @return {number} - The total count of subarrays with GCD equal to k.
6 */
7function subarrayGCD(nums: number[], k: number): number {
8    // Initialize the counter for the number of subarrays found.
9    let count = 0;
10    // Store the length of nums to avoid recalculating it.
11    const numsLength = nums.length;
12  
13    // Iterate over the array to start each subarray from each index.
14    for (let start = 0; start < numsLength; ++start) {
15        // Initialize gcdValue to be the GCD of the current subarray being considered.
16        let gcdValue = 0;
17      
18        // Extend the subarray one element at a time until the end of the array.
19        for (let end = start; end < numsLength; ++end) {
20            // Update gcdValue to be the GCD of the current subarray.
21            gcdValue = gcd(gcdValue, nums[end]);
22          
23            // If the current subarray's GCD is equal to k, increment the counter.
24            if (gcdValue === k) {
25                ++count;
26            }
27        }
28    }
29  
30    // Return the total count of qualifying subarrays.
31    return count;
32}
33
34/**
35 * Computes the greatest common divisor (GCD) of two integers.
36 * @param {number} a - The first integer.
37 * @param {number} b - The second integer.
38 * @return {number} - The GCD of a and b.
39 */
40function gcd(a: number, b: number): number {
41    // If b is 0, a is the GCD. Otherwise, call gcd recursively with b and the remainder of a divided by b.
42    return b === 0 ? a : gcd(b, a % b);
43}
44
Not Sure What to Study? Take the 2-min Quiz：

Consider the classic dynamic programming of longest increasing subsequence:

Find the length of the longest subsequence of a given sequence such that all elements of the subsequence are sorted in increasing order.

For example, the length of LIS for [50, 3, 10, 7, 40, 80] is 4 and LIS is [3, 7, 40, 80].

What is the recurrence relation?

Time and Space Complexity

Time Complexity

The given function calculates the number of subarrays with a GCD equal to k. It uses two nested loops. The outer loop runs from the start of the nums array to its end. For each iteration of the outer loop, denoted by index i, the inner loop runs from the current index i to the end of the array. In the worst case, where i starts at 0, this is n iterations for the inner loop. As i increases, the inner loop's range decreases, but in a big-O notation sense, this still leads to an overall time complexity of about (1/2)n(n+1), which is O(n^2) (quadratic time complexity), where n is the length of nums.

At each step of the inner loop, the greatest common divisor (GCD) is updated and compared against k. The gcd function itself has a time complexity which is effectively O(log(min(a, b))) where a and b are the numbers for which the GCD is being computed. However, in the worst case, since these are elements of the array which can vary widely, we often consider this part constant because it doesn't scale with n substantially.

Thus, the time complexity is dominated by the nested loops and is typically expressed as O(n^2).

Space Complexity

The space complexity of the function is O(1) which means constant space. This is because the space used does not grow with the input size n. The only extra variables used are g and ans which are used for calculating the GCD and for keeping the running count of subarrays whose GCD equals k, respectively.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Depth first search is equivalent to which of the tree traversal order?

Recommended Readings

Math Basics

Math for Technical Interviews How much math do I need to know for technical interviews The short answer is about high school level math Computer science is often associated with math and some universities even place their computer science department under the math faculty However the reality is that you

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫