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

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

Leetcode Solutions

Finding Smallest Subarray with GCD

  1. Calculate the GCD of the entire array. If it is greater than 1, return -1 since it's impossible to make all elements equal to 1.
  2. Count the number of elements that are already 1. If there are any, the answer is n - count_of_ones.
  3. Iterate over the array to find the smallest subarray with a GCD of 1. For each element, calculate the GCD of the subarray starting from that element.
  4. Once the smallest subarray with GCD 1 is found, calculate the number of operations as length of subarray - 1 + n - 1.
  5. Return the calculated number of operations.
UML Thumbnail

Brute Force Search for GCD Pairs

Ask Question

Programming Language
image/screenshot of info(optional)
Full Screen
Loading...

Suggested Answer

Answer
Full Screen
Copy Answer Code
Loading...