aboutsummaryrefslogtreecommitdiff
path: root/min_num_opp_arr_equal_1.py
blob: 75551dce42b35b33d5e1dce0173ef562f61b3a91 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
# 2654. Minimum Number of Operations to Make All Array Elements Equal to 1
from math import gcd

"""
given a 0-indexed array 'nums' consisting of positive integers. you can do
the following operation on the array any number of time: select an index 'i'
such that '0 <= i < n - 1' and replace either of 'nums[i]' or 'nums[i + 1]'
with their gcd values. return the minimum number of operations to make all
elements of 'nums' equal to 1. if this is impossible, return -1. the gcd of
two integers is the greatest common divisor of the two integers.
"""


class Solution(object):
    def minOperations(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        ones_cnt = nums.count(1)
        if ones_cnt:
            return len(nums) - ones_cnt
        diff = float("inf")
        for i in range(len(nums)):
            g = nums[i]
            for j in range(i + 1, len(nums)):
                g = gcd(g, nums[j])
                if g == 1:
                    diff = min(diff, j - i)
        return -1 if diff == float("inf") else diff + len(nums) - 1


if __name__ == "__main__":
    obj = Solution()
    print(obj.minOperations([2, 6, 3, 4]))
    print(obj.minOperations([2, 10, 6, 14]))