#2654

Medium

LeetCode Problem Workspace

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

Find the minimum number of operations to transform every element of a positive integer array into 1 using gcd operations efficiently.

array math number theory

Problem Statement

You are given a 0-indexed array nums of positive integers. You can perform the following operation any number of times: choose an index i and replace nums[i] with gcd(nums[i], nums[i+1]) or gcd(nums[i], nums[i-1]) if the neighbor exists. The goal is to minimize the number of operations required to make all elements equal to 1.

Return the minimum number of operations needed. If it is impossible to make all elements equal to 1, return -1. Remember that gcd(a,b) is the greatest common divisor of integers a and b, which is central to reducing numbers in this problem's array plus math pattern.

Examples

Example 1

Input: nums = [2,6,3,4]

Output: 4

We can do the following operations:

Choose index i = 2 and replace nums[2] with gcd(3,4) = 1. Now we have nums = [2,6,1,4].
Choose index i = 1 and replace nums[1] with gcd(6,1) = 1. Now we have nums = [2,1,1,4].
Choose index i = 0 and replace nums[0] with gcd(2,1) = 1. Now we have nums = [1,1,1,4].
Choose index i = 2 and replace nums[3] with gcd(1,4) = 1. Now we have nums = [1,1,1,1].

Example 2

Input: nums = [2,10,6,14]

Output: -1

It can be shown that it is impossible to make all the elements equal to 1.

Constraints

2 <= nums.length <= 50
1 <= nums[i] <= 106

Solution Approach

Check for Existing Ones

Scan the array for any element equal to 1. If present, each remaining non-one element can be reduced to 1 using a single gcd operation per element. This quickly solves many cases and reduces unnecessary computation.

Use GCD Sliding Window

For arrays without a 1, iterate over all subarrays computing the gcd. Find the shortest subarray with gcd equal to 1. Each element outside this subarray will require operations to propagate the 1 through gcd replacements, counting carefully to minimize total steps.

Handle Impossible Cases

If no subarray has gcd equal to 1, the array cannot be transformed entirely into 1s. Return -1 immediately. This recognizes the failure mode where the overall gcd of the array exceeds 1, which blocks all reduction attempts.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n^2) in the worst case due to checking all subarrays for gcd calculations. Space complexity is O(1) or O(n) depending on whether you store intermediate gcd values or compute them on the fly.

What Interviewers Usually Probe

Mentions gcd operations directly in array transformation context.
Asks about minimum operations or impossible cases using array plus math reasoning.
Probes for recognition of subarray patterns that yield gcd 1.

Common Pitfalls or Variants

Common pitfalls

Assuming presence of a 1 is unnecessary for optimal operations.
Overlooking that overall gcd > 1 makes the task impossible.
Counting operations incorrectly when propagating 1 through neighbors.

Follow-up variants

Compute minimum operations if you can only use adjacent pairs in one direction.
Find minimum steps when the array can contain zeros and gcd is undefined.
Determine number of operations needed if multiple gcd replacements can be done in parallel.

FAQ

What is the main idea behind the Minimum Number of Operations to Make All Array Elements Equal to 1 problem?

It uses gcd operations on array elements to reduce them to 1, focusing on the shortest subarray that yields gcd 1 and propagating 1s through the array.

Can I solve this problem if the array has no 1s?

Yes, but only if some subarray has gcd equal to 1. Otherwise, it is impossible and the answer is -1.

Why is checking the overall gcd of the array important?

If the overall gcd is greater than 1, no sequence of operations can reduce all elements to 1, making the problem unsolvable.

Is there a fast way to count operations once a 1 exists?

Yes, simply count the number of non-one elements and apply one gcd operation per element to convert them to 1.

Does this problem pattern combine array manipulation with math reasoning?

Exactly, it combines array traversal with gcd-based math reasoning, exemplifying the array plus math pattern in algorithm interviews.

terminal

Solution

Solution 1: Math

We first count the number of $1$s in the array $nums$ as $cnt$. If $cnt \gt 0$, then we only need $n - cnt$ operations to turn the entire array into $1$s.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

class Solution:
    def minOperations(self, nums: List[int]) -> int:
        n = len(nums)
        cnt = nums.count(1)
        if cnt:
            return n - cnt
        mi = n + 1
        for i in range(n):
            g = 0
            for j in range(i, n):
                g = gcd(g, nums[j])
                if g == 1:
                    mi = min(mi, j - i + 1)
        return -1 if mi > n else n - 1 + mi - 1

Continue Practicing

#2614 prime in diagonal #2607 make k subarray sums equal #2601 prime subtraction operation