aboutsummaryrefslogtreecommitdiff
path: root/min_num_opp_arr_equal_1.py
diff options
context:
space:
mode:
Diffstat (limited to 'min_num_opp_arr_equal_1.py')
-rw-r--r--min_num_opp_arr_equal_1.py36
1 files changed, 36 insertions, 0 deletions
diff --git a/min_num_opp_arr_equal_1.py b/min_num_opp_arr_equal_1.py
new file mode 100644
index 0000000..75551dc
--- /dev/null
+++ b/min_num_opp_arr_equal_1.py
@@ -0,0 +1,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]))