Tejav
#2654

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

Medium
ArrayMathNumber Theory
LeetCode ↗

Approaches

💡

Intuition

Time Space

The brute-force approach involves repeatedly applying the gcd operation on adjacent elements until all elements become 1. This method is straightforward but inefficient, as it may require many operations.

⚙️

Algorithm

3 steps
  1. 1Step 1: Initialize a counter for operations.
  2. 2Step 2: For each pair of adjacent elements, compute their gcd and replace one of them with the gcd.
  3. 3Step 3: Repeat the process until all elements are 1 or no more operations can be performed.
solution.py26 lines
1# Full working Python code
2
3def min_operations(nums):
4    n = len(nums)
5    operations = 0
6    while True:
7        if all(x == 1 for x in nums):
8            return operations
9        changed = False
10        for i in range(n - 1):
11            if nums[i] != 1 or nums[i + 1] != 1:
12                gcd_value = gcd(nums[i], nums[i + 1])
13                if gcd_value < nums[i]:
14                    nums[i] = gcd_value
15                    changed = True
16                    operations += 1
17                elif gcd_value < nums[i + 1]:
18                    nums[i + 1] = gcd_value
19                    changed = True
20                    operations += 1
21        if not changed:
22            break
23    return -1
24
25from math import gcd
26

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.