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

You are given a 0-indexed array nums consisiting of positive integers. You can do the following operation on the array any number of times:

Select an index i such that 0 <= i < n - 1 and replace either of nums[i] or nums[i+1] with their gcd value.
Return the minimum number of operations to make all elements of nums equal to 1. If it is impossible, return -1.

The gcd of two integers is the greatest common divisor of the two integers.

• 양의 정수로 이루어진 배열 arr이 주어진다.
• 해당 배열에 주어진 연산을 무한번 실행할수 있다
  • i번 인덱스 값이 대해 i + 1 번 인덱스 값과 최소공약수를 구해 둘중 한 숫자를 최소공약수로 변경한다.
• 최소한의 연산으로 모든 숫자를 1로 바꿀때 사용되는 연산의 횟수를 구하라
• 불가능하면 -1을 리턴한다.

예시

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

1. 1, 4를 1, 1로 (2, 6, 1, 1)
2. 6, 1을 1, 1로 (2, 1, 1, 1)
3. 2, 1을 1, 1로 (1, 1, 1, 1)

• 최소 3번에 변경됨

제한

$2 <= nums.length <= 50$
$1 <= nums[i] <= 10^6$

• 배열의 길이가 최대 50이기 때문에 시간복잡도는 $O(2^n)$ 정도가 아니라면 크게 신경쓰지 않아도 된다.

풀이

이 문제의 풀이는 세 가지 경우로 나눌 수 있다.

1. 모든 숫자의 최소공약수가 1이 아닌 경우

• 전체 배열의 GCD가 1이 아니라면 어떤 연산을 해도 1을 만들 수 없다.
• 따라서 -1을 리턴한다.

2. 이미 1이 존재하는 경우

• 배열 안에 1이 있다면, 그 1을 이용해 다른 수를 1로 만들 수 있다.
• 따라서 필요한 연산 수는 배열의 길이 - 1의 개수 가 된다.

3. 1이 하나도 없는 경우

• 이 경우엔 먼저 1을 만들어야 한다.

• 가능한 모든 부분 배열에 대해 GCD를 계산하며 1이 되는 최소 길이를 찾는다.

• 그 길이가 best라면, 전체 연산 횟수는 N + best - 1 이 된다.

  • best는 1을 만들기 위한 추가 연산 수이고,
  • N은 이후 남은 수를 모두 1로 만드는 데 필요한 연산 수이다.

class Solution:
    def minOperations(self, nums: List[int]) -> int:
        N = len(nums)

        # 전체 배열의 GCD 계산
        acc = nums[0]
        for i in range(1, N):
            acc = gcd(acc, nums[i])

        # 모든 수의 GCD가 1이 아니라면 불가능
        if acc != 1:
            return -1

        # 이미 1이 존재하는 경우
        one_count = nums.count(1)
        if one_count > 0:
            return N - one_count

        # 1을 만들기 위한 최소 길이의 부분 배열 탐색
        best = float('inf')
        for i in range(N - 1):
            g = nums[i]
            for j in range(i + 1, N):
                g = gcd(g, nums[j])
                if g == 1:
                    best = min(best, j - i)
                    break

        return N + best - 1