Minimum gcd operations to make all array elements one

0 0 6 minutes read

Given an array A[] of size N. You can replace any number in the array with the gcd of that element with any of its adjacent elements. Find the minimum number of such operation to make the element of whole array equal to 1. If its not possible print -1.

Examples:

Input : A[] = {4, 8, 9}
Output : 3
Explanation:
In the first move we choose (8, 9) 
gcd(8, 9) = 1. Now the array becomes {4, 1, 9}.
After second move, the array becomes {1, 1, 9}. 
After third move the array becomes {1, 1, 1}.

Input : A[] = { 5, 10, 2, 6 }
Output : 5
Explanation:
There is no pair with GCD equal one. We first
consider (5, 10) and replace 10 with 5. Now array
becomes { 5, 5, 2, 6 }. Now we consider pair (5, 2)
and replace 5 with 1, array becomes { 5, 1, 2, 6 }.
We have a 1, so further steps are simple.

Input : A[] = {8, 10, 12}
Output : -1
Explanation:
Its not possible to make all the element equal to 1.

Input : A[] = { 8, 10, 12, 6, 3 }
Output : 7

If initially the array contains 1, our answer is the difference between the size of the array and count of ones in the array.
If the array has no element equal to 1. We need to find the smallest sub array with GCD equal to one. Our result is N + (length of the minimum subarray with GCD 1) – 1. Example cases are { 5, 10, 2, 6 } and { 8, 10, 12, 6, 3 }.

We can find all the sub array in O(N^2) and GCD can be calculated in O(Log N) using Euclidean algorithms.
The overall complexity will be O(N^2 Log N).

Here is the implementation of the above idea.

C++

// CPP program to find minimum GCD operations
// to make all array elements one.
#include <bits/stdc++.h>
using namespace std;
 
// Function to count number of moves.
int minimumMoves(int A[], int N)
{
   // Counting Number of ones.
    int one = 0;
    for (int i = 0; i < N; i++) 
        if (A[i] == 1)
            one++; 
 
    // If there is a one
    if (one != 0) 
        return N - one; 
     
    // Find smallest subarray with GCD equals
    // to one.
    int minimum = INT_MAX;
    for (int i = 0; i < N; i++) {
        int g = A[i]; // to calculate GCD
        for (int j = i + 1; j < N; j++) {
            g = __gcd(A[j], g); 
            if (g == 1) {
                minimum = min(minimum, j - i); 
                break;
            }
        }
    }
 
    if (minimum == INT_MAX) // Not Possible
        return -1;
    else
        return N + minimum - 1; // Final answer
}
 
// Driver code
int main()
{
    int A[] = { 2, 4, 3, 9 };
    int N = sizeof(A) / sizeof(A[0]);
    cout << minimumMoves(A, N);
    return 0;
}

Java

// Java program to find minimum GCD operations
// to make all array elements one.
import java.util.*;
 
class GFG {
     
//__gcd function
static int __gcd(int a, int b) 
{
    if (a == 0)
    return b;
    return __gcd(b % a, a);
}
 
// Function to count number of moves.
static int minimumMoves(int A[], int N) 
{
    // Counting Number of ones.
    int one = 0;
    for (int i = 0; i < N; i++)
    if (A[i] == 1)
        one++;
 
    // If there is a one
    if (one != 0)
    return N - one;
 
    // Find smallest subarray with 
    // GCD equals to one.
    int minimum = Integer.MAX_VALUE;
    for (int i = 0; i < N; i++) {
         
    // to calculate GCD
    int g = A[i]; 
    for (int j = i + 1; j < N; j++) {
        g = __gcd(A[j], g);
        if (g == 1) {
        minimum = Math.min(minimum, j - i);
        break;
        }
    }
    }
 
    if (minimum == Integer.MAX_VALUE) // Not Possible
    return -1;
    else
    return N + minimum - 1; // Final answer
}
 
// Driver code
public static void main(String[] args) 
{
    int A[] = {2, 4, 3, 9};
    int N = A.length;
    System.out.print(minimumMoves(A, N));
}
}
 
// This code is contributed by Anant Agarwal.

Python3

# Python program to find
# minimum GCD operations
# to make all array elements one.
 
#__gcd function
def __gcd(a,b):
 
    if (a == 0):
        return b
    return __gcd(b % a, a)
  
# Function to count number of moves.
def minimumMoves(A,N):
 
    # Counting Number of ones.
    one = 0
    for i in range(N): 
        if (A[i] == 1):
            one+=1
  
    # If there is a one
    if (one != 0): 
        return N - one 
      
    # Find smallest subarray with GCD equals
    # to one.
    minimum = +2147483647
    for i in range(N):
        g = A[i] # to calculate GCD
        for j in range(i + 1,N):
            g = __gcd(A[j], g) 
            if (g == 1):
                minimum = min(minimum, j - i) 
                break
  
    if (minimum == +2147483647): # Not Possible
        return -1
    else:
        return N + minimum - 1; # Final answer
 
 
# Driver program
A = [ 2, 4, 3, 9 ]
N = len(A)
print(minimumMoves(A, N))
 
# This code is contributed
# by Anant Agarwal.

C#

// C# program to find minimum GCD operations
// to make all array elements one.
using System;
 
class GFG {
     
//__gcd function
static int __gcd(int a, int b) 
{
    if (a == 0)
    return b;
    return __gcd(b % a, a);
}
 
// Function to count number of moves.
static int minimumMoves(int []A, int N) 
{
    // Counting Number of ones.
    int one = 0;
    for (int i = 0; i < N; i++)
    if (A[i] == 1)
        one++;
 
    // If there is a one
    if (one != 0)
    return N - one;
 
    // Find smallest subarray with 
    // GCD equals to one.
    int minimum = int.MaxValue;
    for (int i = 0; i < N; i++) {
         
    // to calculate GCD
    int g = A[i]; 
    for (int j = i + 1; j < N; j++) {
        g = __gcd(A[j], g);
        if (g == 1) {
        minimum = Math.Min(minimum, j - i);
        break;
        }
    }
    }
 
    if (minimum == int.MaxValue) // Not Possible
    return -1;
    else
    return N + minimum - 1; // Final answer
}
 
// Driver code
public static void Main() 
{
    int []A = {2, 4, 3, 9};
    int N = A.Length;
    Console.WriteLine(minimumMoves(A, N));
}
}
 
// This code is contributed by vt_m.

PHP

<?php
// PHP program to find minimum 
// GCD operations to make all 
// array elements one.
 
// __gcd function
function __gcd($a, $b) 
{
    if ($a == 0)
    return $b;
    return __gcd($b % $a, $a);
}
 
// Function to count
// number of moves.
function minimumMoves($A, $N) 
{
    // Counting Number of ones.
    $one = 0;
    for ($i = 0; $i < $N; $i++)
    if ($A[$i] == 1)
        $one++;
 
    // If there is a one
    if ($one != 0)
    return $N - $one;
 
    // Find smallest subarray  
    // with GCD equals to one.
    $minimum = PHP_INT_MAX;
    for ($i = 0; $i < $N; $i++)
    {
         
    // to calculate GCD
    $g = $A[$i]; 
    for ($j = $i + 1; 
         $j < $N; $j++) 
    {
        $g = __gcd($A[$j], $g);
        if ($g == 1) 
        {
            $minimum = min($minimum, 
                           $j - $i);
            break;
        }
    }
    }
 
    if ($minimum == PHP_INT_MAX) // Not Possible
    return -1;
    else
    return $N + $minimum - 1; // Final answer
}
 
// Driver code
$A = array(2, 4, 3, 9);
$N = sizeof($A);
echo (minimumMoves($A, $N));
 
// This code is contributed 
// by akt_mit.
?>

Javascript

<script>
 
// JavaScript program to find minimum 
// GCD operations to make all 
// array elements one.
 
// __gcd function
function __gcd(a, b) 
{
    if (a == 0)
    return b;
    return __gcd(b % a, a);
}
 
// Function to count
// number of moves.
function minimumMoves(A, N) 
{
    // Counting Number of ones.
    let one = 0;
    for (let i = 0; i < N; i++)
    if (A[i] == 1)
        one++;
 
    // If there is a one
    if (one != 0)
    return N - one;
 
    // Find smallest subarray  
    // with GCD equals to one.
    let minimum = Number.MAX_SAFE_INTEGER;
    for (let i = 0; i < N; i++)
    {
         
    // to calculate GCD
    let g = A[i]; 
    for (let j = i + 1; 
         j < N; j++) 
    {
        g = __gcd(A[j], g);
        if (g == 1) 
        {
            minimum = Math.min(minimum, 
                           j - i);
            break;
        }
    }
    }
 
    if (minimum == Number.MAX_SAFE_INTEGER) // Not Possible
    return -1;
    else
    return N + minimum - 1; // Final answer
}
 
// Driver code
let A = [2, 4, 3, 9];
let N = A.length;
document.write(minimumMoves(A, N));
 
// This code is contributed by _saurabh_jaiswal.
 
</script>

Output:

Time Complexity: O(n²*log(n))
Auxiliary Space: O(1)

Recommended

Solve DSA problems on GfG Practice.

Solve Problems

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!