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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

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

Difficulty: Medium

Problem Description

You are given a 0-indexed array nums consisting of positive integers. You can do the following operation on the array any number of times: Select an index i such that 0 <= i < n - 1 and replace either of nums[i] or nums[i+1] with their gcd value. Return the minimum number of operations to make all elements of nums equal to 1. If it is impossible, return -1.

Key Insights

  • The operation allows replacing elements with their gcd, which can only reduce the values of the elements.
  • If the gcd of the entire array is greater than 1, it is impossible to make all elements equal to 1.
  • The number of operations required to convert the entire array to 1 can be calculated based on the position of the first 1 encountered when reducing the elements.
  • The goal is to minimize the number of operations by strategically choosing indices to operate on.

Space and Time Complexity

Time Complexity: O(n) - where n is the length of the array, as we may need to iterate through the array to find the gcd and the number of operations. Space Complexity: O(1) - since we use a constant amount of space for variables.

Solution

The solution involves first checking if it's possible to reach the state where all elements become 1. This can be done by calculating the gcd of the entire array. If the gcd is greater than 1, we return -1. Otherwise, we proceed to count the operations needed to convert all elements to 1. We can track the position of the first 1 we can create and then calculate the distance from all other elements to this position to find the minimum operations.

Code Solutions

import math
from functools import reduce

def min_operations_to_one(nums):
    overall_gcd = reduce(math.gcd, nums)
    if overall_gcd > 1:
        return -1
    
    operations = 0
    first_one_position = -1
    
    # Finding the first position where we can make a 1
    for i in range(len(nums)):
        if nums[i] == 1:
            first_one_position = i
            break
            
    if first_one_position == -1:
        # If there's no 1, we find the first index we can make a 1
        # This is done by checking where we can create a 1
        for i in range(len(nums) - 1):
            if math.gcd(nums[i], nums[i + 1]) == 1:
                first_one_position = i + 1
                break
    
    # Counting operations needed to convert all to 1
    for i in range(len(nums)):
        if i < first_one_position:
            operations += first_one_position - i
        else:
            operations += i - first_one_position
    
    return operations

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