We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

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

Number: 2753

Difficulty: Medium

Paid? No

Companies: N/A

Problem Description

Given an array of positive integers, you are allowed to perform operations where you choose an index i (0 <= i < n-1) and replace either nums[i] or nums[i+1] with the greatest common divisor (gcd) of nums[i] and nums[i+1]. The goal is to make every element in the array equal to 1 using the minimum number of operations. If it is impossible to achieve this, return -1.

Key Insights

  • If at least one element is already 1, then that element can be used to convert its neighbors to 1. Hence, the number of operations in this case is simply (n - number of ones).
  • If no element is 1, then check if the overall gcd of the array is 1; if it isn’t, it is impossible to make every element 1.
  • Otherwise, find the smallest subarray for which the cumulative gcd becomes 1. Converting that subarray into a 1 uses (L - 1) operations (where L is the length of the subarray). Then use the newly created 1 to turn the rest of the elements into 1 with an additional (n - 1) operations.
  • The final answer will be the sum of these two parts.

Space and Time Complexity

Time Complexity: O(n^2) in the worst-case, where n is the length of the array
Space Complexity: O(1) extra space (ignoring the input list)

Solution

The solution works in two main parts:

  1. First, scan through the array to count how many elements are 1. If at least one exists, then the answer is (n - count1) because each non-1 element can be paired with a nearby 1 in one operation.

  2. If there are no ones, compute the overall gcd of the array. If the overall gcd is not 1, return -1. Otherwise, iterate through every possible subarray, and for each subarray compute its cumulative gcd. If the gcd becomes 1 for a subarray starting at index i and ending at j, track the shortest length (j - i). The operations needed will be (length of subarray - 1) for creating the first 1, plus (n - 1) to spread that 1 to all remaining elements.

The algorithm relies heavily on gcd computations and a brute force two-loop approach over the small maximum input size (n ≤ 50).

Code Solutions

# Python solution with line-by-line comments
import math

def minOperations(nums):
    n = len(nums)
    
    # Count the number of ones already present
    count_ones = sum(1 for num in nums if num == 1)
    
    # If there is any 1 in the array, then each non-1 element can be converted directly
    if count_ones > 0:
        return n - count_ones

    # Compute overall gcd of the entire array
    overall_gcd = nums[0]
    for num in nums:
        overall_gcd = math.gcd(overall_gcd, num)
    if overall_gcd != 1:
        return -1

    # Since there were no ones, find the shortest subarray that can be reduced to 1
    best = float('inf')
    for i in range(n):
        current_gcd = nums[i]
        for j in range(i + 1, n):
            current_gcd = math.gcd(current_gcd, nums[j])
            if current_gcd == 1:
                best = min(best, j - i)
                break  # Found a subarray from i that results in gcd==1, so break inner loop

    # Total operations = (subarray length - 1) to create one "1" + (n - 1) to propagate that 1 to every other element
    return best + (n - 1)

# Example usage:
print(minOperations([2,6,3,4]))  # Expected output: 4
print(minOperations([2,10,6,14])) # Expected output: -1
← Back to All Questions