LeetCode Entry

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

12.11.2025 medium 2025 kotlin rust

Min steps to make all '1' by gcd

2654. Minimum Number of Operations to Make All Array Elements Equal to 1 medium blog post substack youtube

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/1171

Problem TLDR

Min steps to make all ‘1’ by gcd #medium

Intuition

• gcd of array = reduce(::gcd)

3 cases:

• have ones in array - then just propagate it in ‘size-ones’ steps
• gcd(array)>1 - no answer, -1
• gcd(array)==1 - then it is min_window_gcd1 steps to make a single 1 plus propagate it size-single ones steps

Approach

• this is a hard problem

Complexity

• Time complexity: \(O(n^2)\)

• Space complexity: \(O(n)\)

Code

// 27ms
    fun minOperations(n: IntArray): Int {
        val n = n.asList(); val ones = n.count { it<2 }
        fun gcd(a: Int, b: Int): Int = if (b==0) a else gcd(b, a%b)
        return if (ones > 0) n.size - ones else if (n.reduce(::gcd) > 1) -1
        else n.size - 2 + (2..n.size).first { L -> n.windowed(L).any { it.reduce(::gcd)<2}}
    }

// 0ms
    pub fn min_operations(n: Vec<i32>) -> i32 {
        let o = n.iter().filter(|&&x|x==1).count() as i32;
        if o > 0 { n.len()as i32 - o} else {
            fn g(mut a:i32,b:&i32)->i32 { let mut b = *b; while b>0 { let t=b;b=a%b;a=t;} a}
            if n.iter().fold(0,g)>1 { -1 } else { n.len() as i32 - 2 +
            (2..=n.len()).find(|&l|n.windows(l).any(|w|w.iter().fold(0,g)==1)).unwrap()as i32}
        }
    }