2654. Minimum Number of Operations to Make All Array Elements Equal to 1

MediumArrayMathNumber Theory
Leetcode Link

Problem Description

The problem presents an operation that we can perform on a 0-indexed array nums of positive integers. The operation involves selecting any index i (where 0 <= i < n - 1, n is the number of elements in the array) and then replacing either nums[i] or nums[i+1] with the greatest common divisor (gcd) of these two elements. This operation can be repeated any number of times, and the goal is to make all elements in the array equal to 1. The task is to determine the minimum number of operations required to achieve this goal; if it's not possible, return -1.

The key point to understand here is the usage of the greatest common divisor (gcd). It is the highest number that divides both of the integers without leaving a remainder. For the array to become all 1's, we would have to be able to break down each number in the array to 1 using gcd operations. If at least one number in the array cannot be broken down to 1, it is impossible to achieve the goal.

Intuition

To solve the problem, our main approach involves finding sequences within the array where the gcd can be reduced to 1, because when we have such a sequence we could repeatedly apply the operation to make all elements in that sequence equal to 1. Here are the steps outlining the intuition behind the solution:

  1. First, check if there is already at least one element equal to 1 in the array. Since we can replace the adjacent elements with their gcd and 1 is the gcd of 1 and any other number, we can turn the entire array into 1s if there's already a 1 present. The number of operations is equal to the length of the array minus the number of 1s, because for every non-1 element, we need one operation to turn it into 1 using the existing 1s.

  2. If there is no 1 in the array, then we need to check if it's possible at all to make all elements equal to 1. To do so, we need to find if there is any subsequence whose elements have a gcd of 1. This is because if we cannot find such a subsequence, it's mathematically impossible for the entire array to have a gcd of 1, meaning that we cannot complete our task and should return -1.

  3. We iterate over every possible starting index i for a subsequence, and for each starting index, we extend the subsequence element by element, updating the gcd of the current subsequence as we go. We look for the gcd to become 1.

  4. Once we find a subsequence with a gcd of 1, we record the length of this subsequence. We do this for every subsequence and keep track of the minimum length that achieves a gcd of 1.

  5. After we find the minimum subsequence length that can be turned into all 1s (let's call this length mi), the total number of operations needed will be n - 1 + mi - 1. This is because it takes mi operations to make the subsequence all 1s and an additional n - 1 operations to spread the 1s to the entire array.

By implementing this approach, we find the minimum number of operations needed to make all elements of the array equal to 1 or determine that it is impossible.

Learn more about Math patterns.

Solution Approach

The solution provided in the Python code is an implementation of the intuition described previously. Let's break down the solution step by step and explain the algorithms, data structures, and patterns utilized.

  1. The very first step in the function minOperations is to determine the size of the input array nums by assigning len(nums) to n.

    1n = len(nums)
  2. Then, we count how many 1s already exist in nums using the count() method and store the result in cnt.

    1cnt = nums.count(1)
  3. If cnt is not zero (meaning there are already 1s in the array), it is possible to make the whole array 1 using n - cnt operations, as explained earlier, so that's what we return. Each non-1 element can be made into 1 by replacing it with the gcd of it and an adjacent 1.

    1if cnt:
    2    return n - cnt
  4. If there are no 1s in nums, we set up a variable mi to keep track of the minimum subsequence where the gcd calculation results in 1. Initialize mi with n + 1.

    1mi = n + 1
  5. We then iterate over all possible starting points for a subsequence within nums using a nested loop. The outer loop variable i represents the start of the subsequence, and the inner loop variable j represents the end.

    1for i in range(n):
    2    g = 0
    3    for j in range(i, n):
  6. Inside the inner loop, we compute the gcd of the current subsequence. An important pattern to notice here is the incremental calculation of gcd. Starting with g=0 (since gcd(0, x) for any x will be x), we update g with the gcd of g and nums[j].

    1g = gcd(g, nums[j])
  7. As soon as we get g == 1 for a subsequence, we know that it is possible to make this subsequence all 1s after certain operations. We calculate the length of the subsequence (j - i + 1) and compare it with the current minimum mi, updating mi if this subsequence is shorter.

    1if g == 1:
    2    mi = min(mi, j - i + 1)
  8. Finally, after completing the iterations, we perform a check on mi. If mi has not been updated from its initial value (i.e., no subsequence with gcd equal to 1 has been found), the function returns -1. If it has been updated, we return n - 1 + mi - 1. This calculation accounts for the minimum number of operations to create a single 1 in the array and to expand it to the rest of the elements.

    1return -1 if mi > n else n - 1 + mi - 1

Throughout the implementation the Python function gcd from the [math](/problems/math-basics) module is used, which efficiently computes the greatest common divisor of two numbers.

The solution approach employs a brute-force search pattern across all possible subsequences combined with gcd calculations and a running minimum to determine the feasibility and number of operations needed to transform the array.

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

Which technique can we use to find the middle of a linked list?

Example Walkthrough

Let's apply the solution approach to an example to illustrate how it works. Consider the following input array nums:

1nums = [4, 6, 8, 10]

We need to perform the operation on nums until all elements become 1 or determine if it's impossible. Below is a step-by-step walk-through following the solution approach:

  1. The length of nums is calculated: n = 4.

  2. We check if there are any ones in nums:

    1cnt = nums.count(1)

    In this example, cnt is 0 because there are no elements equal to 1.

  3. Since there are no 1s in the array to begin with, we cannot instantly determine the minimum number of operations. We must investigate further.

  4. We initialize mi to 4 + 1 (since n is 4):

    1mi = 5
  5. We iterate over nums to find the minimum-length subsequence where the gcd becomes 1.

    We start with i = 0 (first element in nums) and subsequence g at 0. Then we iterate through each j from i to n - 1.

    For i = 0:

    • j = 0:

      • g becomes gcd(0, nums[0]), which is 4.
    • j = 1:

      • g becomes gcd(4, nums[1]), which is 2.
    • j = 2:

      • g becomes gcd(2, nums[2]), which is 2.
    • j = 3:

      • g becomes gcd(2, nums[3]), which is 2.

    Since the gcd does not become 1, we move to the next starting index i = 1.

    • (Continue with this process for each subsequence starting from each i.)

    For i = 1:

    • Skipping the details, we find that all subsequences starting from i = 1 do not have a gcd of 1.

    Continue this process for i = 2 and i = 3. After checking all possible starting indices and their subsequences, if we didn't find any subsequence where the gcd becomes 1, mi would still be 5.

  6. Since we didn't find any subsequence with a gcd of 1, mi remains greater than n. Thus, per our algorithm, we deduce that it's impossible to convert the entire array to 1s:

    1return -1 if mi > n else n - 1 + mi - 1

So, in this example, the function would return -1, indicating that we cannot perform the operation to make all elements in the array equal to 1.

Solution Implementation

1from math import gcd
2from typing import List
3
4class Solution:
5    def minOperations(self, nums: List[int]) -> int:
6        """Calculate the minimum number of array elements to be replaced,
7           to make the whole array contain only 1s, by performing GCD operations.
8        """
9      
10        # Calculate the length of the list nums.
11        length = len(nums)
12      
13        # Count the number of 1s in the list nums.
14        count_ones = nums.count(1)
15      
16        # If there are 1s present, we can replace all the non-1s.
17        if count_ones:
18            return length - count_ones
19      
20        # Set a variable to keep track of the minimum replacements needed.
21        min_operations = length + 1
22      
23        # Loop through the list of nums to find the subarray with GCD 1.
24        for i in range(length):
25            current_gcd = 0
26            # For each starting index i, we check the subarray ending at j.
27            for j in range(i, length):
28                # Calculate the GCD of the current subarray.
29                current_gcd = gcd(current_gcd, nums[j])
30              
31                # If GCD is 1, we found a valid subarray.
32                if current_gcd == 1:
33                    min_operations = min(min_operations, j - i + 1)
34                    break  # Break the loop as we have found the subarray.
35      
36        # If we were unable to find such a subarray, return -1.
37        if min_operations > length:
38            return -1
39      
40        # If we found a valid subarray, return the number of replacements needed.
41        # This includes the length of the array minus 1, plus the length of the
42        # subarray minus 1 (since we need one GCD 1 subarray).
43        return (length - 1) + (min_operations - 1)
44
45# Example usage:
46# solution = Solution()
47# print(solution.minOperations([2, 4, 6, 8]))  # Outputs: -1
48
1class Solution {
2    public int minOperations(int[] nums) {
3        int length = nums.length; // Store the length of the array
4        int countOnes = 0; // Initialize a counter for ones in the array
5
6        // Loop through the array to count the number of ones
7        for (int number : nums) {
8            if (number == 1) {
9                ++countOnes;
10            }
11        }
12
13        // If there is at least one 1, the minimum operations is the length minus the count of ones
14        if (countOnes > 0) {
15            return length - countOnes;
16        }
17
18        int minOperations = length + 1; // Set an initial value higher than possible
19        // Try to find a subsequence which GCD is 1
20        for (int i = 0; i < length; ++i) {
21            int gcdValue = 0; // Initialize the GCD value
22            for (int j = i; j < length; ++j) {
23                // Compute GCD value for the subsequence from i to j
24                gcdValue = gcd(gcdValue, nums[j]);
25                if (gcdValue == 1) {
26                    // Update min operations if we found a shorter subsequence
27                    minOperations = Math.min(minOperations, j - i + 1);
28                }
29            }
30        }
31        // Return -1 if no such subsequence exists, otherwise the number of operations needed
32        return minOperations > length ? -1 : length - 1 + minOperations - 1;
33    }
34
35    // Helper method to compute the Greatest Common Divisor (GCD) of two numbers
36    private int gcd(int a, int b) {
37        return b == 0 ? a : gcd(b, a % b);
38    }
39}
40
1#include <vector>
2#include <algorithm>
3
4class Solution {
5public:
6    // Function to find the minimum number of operations needed
7    int minOperations(std::vector<int>& nums) {
8        int size = nums.size(); // size of the input vector
9        int countOnes = 0; // to count the number of ones in the vector
10        for (int num : nums) { // iterate over all elements
11            if (num == 1) {
12                ++countOnes; // count ones
13            }
14        }
15
16        // If there are ones in the vector, the minimum operation
17        // would be the size of the vector minus the number
18        // of ones present because we only need to transform the 
19        // other numbers into 1's
20        if (countOnes) {
21            return size - countOnes;
22        }
23
24        int minOperations = size + 1; // initialize minimum operations to a large value
25        // Iterate over all possible subarrays to find a subarray
26        // which product can be converted to 1 with minimum operations
27        for (int i = 0; i < size; ++i) {
28            int gcdValue = 0; // greatest common divisor of the subarray
29            for (int j = i; j < size; ++j) {
30                gcdValue = std::gcd(gcdValue, nums[j]); // update gcd for the subarray
31                // If gcd becomes 1, it means we can convert the product of the
32                // numbers in the subarray to 1 with operations, we try to find
33                // the subarray with the minimum length that satisfies this.
34                if (gcdValue == 1) {
35                    minOperations = std::min(minOperations, j - i + 1);
36                }
37            }
38        }
39
40        // If minOperations is still greater than size, no subarray can be converted
41        // to 1, hence return -1.
42        // Otherwise, return the number of operations which is the length of the nums
43        // minus 1 (all numbers to 1) plus the length of the smallest subarray found
44        // which makes gcd 1 minus 1 (because we assume subtracting the largest number
45        // from all will make the smallest number become 1, so we don't count it).
46        return minOperations > size ? -1 : size - 1 + minOperations - 1;
47    }
48};
49
1// Calculates the minimum number of operations required on an array such that
2// the GCD (Greatest Common Divisor) of the array equals 1.
3function minOperations(nums: number[]): number {
4    const length = nums.length;
5    let countOfOnes = 0;
6
7    // Count the number of 1's in the array.
8    for (const num of nums) {
9        if (num === 1) {
10            countOfOnes++;
11        }
12    }
13
14    // If there is at least one 1, return the number of non-1 elements, as 1 is the GCD of any number with itself.
15    if (countOfOnes > 0) {
16        return length - countOfOnes;
17    }
18
19    let minOperations = length + 1;
20
21    // Search for a subsequence of the array where the GCD is 1.
22    for (let i = 0; i < length; ++i) {
23        let gcdValue = 0;
24        for (let j = i; j < length; ++j) {
25            gcdValue = gcd(gcdValue, nums[j]);
26            // If the GCD becomes 1, we found a valid subsequence.
27            if (gcdValue === 1) {
28                minOperations = Math.min(minOperations, j - i + 1);
29                break; // No need to continue this loop as we already found a subsequence resulting in GCD = 1.
30            }
31        }
32    }
33
34    // If no such subsequence was found, return -1. Otherwise, return the length minus 1 (for the swap operation) plus the size of the subsequence minus 1.
35    return minOperations > length ? -1 : length - 1 + minOperations - 1;
36}
37
38// Helper function to calculate the GCD of two numbers using Euclid's algorithm.
39function gcd(a: number, b: number): number {
40    return b === 0 ? a : gcd(b, a % b);
41}
42

Time and Space Complexity

Time Complexity

The time complexity of the code can be analyzed based on the nested loops and the operations performed within them.

  • The first step in the code is counting the occurrences of 1 in the list of numbers using the count() method, which is an O(n) operation, where n is the length of the list.
  • The code then iterates through all possible starting points i for subarrays. This is an O(n) operation.
  • For each starting point i, the code iterates through all possible ending points j from i to n-1. This nested loop results in a O(n^2) operation since it pairs each starting index with each possible ending index.
  • Inside the inner loop, the gcd operation is performed, which has a time complexity of O(log(min(a, b))) in the worst case, where a and b are the numbers for which we are computing the GCD. However, since the GCD is computed cumulatively and the maximum value of g reduces after each iteration (because we are looking for the GCD that equals 1), the amortized time complexity for the GCD operations across all iterations is often used as O(log C), where C is some constant representing the upper limit of the numbers in nums.
  • The conditional check for g == 1 is an O(1) operation.

Given the nested loops and the amortized GCD calculation time, the overall worst-case time complexity would be approximately O(n^3 log C) since the GCD calculation is nested within the O(n^2) double loop.

Space Complexity

The space complexity of the code can be analyzed based on the variables and data structures utilized.

  • A constant amount of additional memory is used for variables like n, cnt, mi, g, i, and j, which does not scale with the input size.
  • No additional data structures that grow with the input size are used.

Therefore, the space complexity is O(1), indicating constant space is used regardless of the input size.

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


Fast Track Your Learning with Our Quick Skills Quiz:

Which type of traversal does breadth first search do?


Recommended Readings


Got a question? Ask the Monster 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.

Tired of the LeetCode Grind?

Our structured approach teaches you the patterns behind problems, so you can confidently solve any challenge. Get started now to land your dream tech job.

Get Started

🪄