Katkat
Back

Fewest Adjacent-GCD Operations to Turn Every Array Element into 1

Otter.AiSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteCoding & Algorithms

Last updated

Given an array of positive integers, find the fewest operations that make every element 1, where each operation replaces one of two neighboring values with their greatest common divisor, or return -1 if it cannot be done. Tests GCD properties, lower-bound reasoning and careful case analysis on small arrays.

You are given an array nums of positive integers. In one operation, you choose an index i with 0 <= i < len(nums) - 1 and replace either nums[i] or nums[i + 1], but not both, with the greatest common divisor (GCD) of those two values.

Return the minimum number of operations needed to make every element of nums equal to 1. If that is impossible, return -1.

Function Signature

def min_operations_to_all_ones(nums: list[int]) -> int:

Rules

  • gcd(a, b) is the largest positive integer that divides both a and b; for example, gcd(12, 18) = 6 and gcd(4, 9) = 1.
  • Operations are applied one at a time, and each one sees the values left by the previous operations.
  • Return 0 if every element is already 1.

Constraints

  • 2 <= len(nums) <= 50
  • 1 <= nums[i] <= 10^6

Examples

Example 1

Input: nums = [6, 10, 15]
Output: 4

One optimal sequence: replace 10 with gcd(10, 15) = 5, giving [6, 5, 15]; replace 6 with gcd(6, 5) = 1, giving [1, 5, 15]; replace 5 with gcd(1, 5) = 1, giving [1, 1, 15]; replace 15 with gcd(1, 15) = 1, giving [1, 1, 1]. No sequence of three operations works.

Example 2

Input: nums = [3, 1, 9, 1]
Output: 2

Replace 3 with gcd(3, 1) = 1, then replace 9 with gcd(9, 1) = 1.

Example 3

Input: nums = [4, 6, 8]
Output: -1

Every value is even, so every GCD that can be formed is even and no element can ever become 1.