Minimum number of GCD operations to make array = 1

We have explored the algorithm to find the Minimum number of GCD operations to make all elements of an array equal to 1. We have illustrated with examples how different approaches result in different number of GCD operations.

Table of content:

  1. Problem Statement
  2. Approach 1
  3. Approach 2
  4. Algorithm
  5. Implementation
  6. Time and Space Complexity

We will get started now.

Problem Statement

We are given an integer array arr[] of size N. Now we have to find the minimum number of GCD operations to make all elements in array 1.

A GCD operation is to take 2 adjacent elements and set one of the elements to its GCD.

Print -1 if it is not possible to make all elements of array equal to 1 in any numbers of GCD operations.

For Example 1:

Input:      Output:
 3             2
 1 2 3

Explanation:

Here N = 3 and arr = {1,2,3}

  1. Start from index 0, arr[0] = 1 and adjacent element at index 1
    arr[1] = 2.
    GCD(1,2) = 1
    so replace value at index 1 by result = 1.
    i.e arr[1] = 1
    ---> arr = {1,1,3}
  2. Now take element at index 1 and 2, arr[1] and arr[2]
    GCD(1,3) = 1
    replace the value at index 2 by result = 1.
    i.e arr[2] = 1
    ---> arr = {1,1,1}
    So, here it requires minimum 2 GCD operations to convert all elements of array to 1.

Example 2:

 Input:         Output:
 4              -1
 5 10 15 20

Explanation:

Here N = 4 and arr = {5,10,15,20}

  1. Start from index 0, arr[0] = 5 and adjacent element at index 1
    arr[1] = 10
    GCD(5,10) = 5
    so replace value at index 1 by result = 5.
    i.e arr[1] = 5
    ---> arr = {5,5,15,20}
  2. Now take element at index 1 and 2, arr[1] and arr[2]
    GCD(5,15) = 5
    replace the value at index 2 by result = 5.
    i.e arr[2] = 5
    ---> arr = {5,5,5,20}
  3. Now take element at index 2 and 3, arr[2] and arr[3]
    GCD(5,20) = 5
    replace the value at index 3 by result = 5.
    i.e arr[3] = 5
    ---> arr = {5,5,5,5}
    As, we see all elements converted to 5 and even after of infinite GCD
    operation we can not change the elements to 1 as always the GCD of two
    concurrent elements will be 5.
    So, here it will return -1.

Example 3:

 Input:         Output:
 5              5
 2 4 3 5 6

Explanation:

Here N = 5 and arr = {2,4,3,5,6}

Approach 1

  1. Start from index 0, arr[0] = 2 and adjacent element at index 1
    arr[1] = 4
    GCD(2,4) = 2
    so, replace value at index 1 by result = 2.
    i.e arr[1] = 2
    ---> arr = {2,2,3,5,6}
  2. Now take element at index 1 and 2, arr[1] and arr[2]
    GCD(2,3) = 1
    replace the value at index 2 by result = 1.
    i.e arr[2] = 1
    ---> arr = {2,2,1,5,6}
  3. Now it will take 4 GCD operations more to convert all elements to
    1.
    i.e GCD(2,1)---> arr = {2,1,1,5,6}
    GCD(2,1)---> arr = {1,1,1,5,6}
    GCD(1,5)---> arr = {1,1,1,1,6}
    GCD(1,6)---> arr = {1,1,1,1,1}
    Here it is taking 6 GCD operations to convert all elements to 1.

Approach 2

Given array arr = {2,4,3,5,6}

  1. Start from index 1, arr[1] = 4 and adjacent element at index 2
    arr[2] = 3
    GCD(4,3) = 1
    so, replace value at index 1 by result = 1.
    i.e arr[1] = 1
    ---> arr = {2,1,3,5,6}
  2. Now it will take 4 GCD operations more to convert all elements to
    1.
    i.e GCD(2,1)---> arr = {1,1,3,5,6}
    GCD(1,3)---> arr = {1,1,1,5,6}
    GCD(1,5)---> arr = {1,1,1,1,6}
    GCD(1,6)---> arr = {1,1,1,1,1}
    Here it is taking 5 GCD operations to convert all elements to 1. And also the
    minimum operations required to convert array elements to 1 are 5 so output will
    be 5.

From the above given examples and their explanation we can conclude three things.

  1. If in array any element have value 1 or if array contains 1, then number of GCD operations required to convert all elements to 1 will be equal to (N - count of 1's in array) or difference of size of array and no of 1 present in array i.e in example 1 above.
N = 3
arr = {1,2,3}
count of one = 1W
Minumum GCD operations = (3-1) = 2
  1. If we are able to convert any of the element to 1 then we can surely can convert all elements to 1.

For this we need to convert any element to 1 in minimum no of GCD operations to have overall minimum result. So, we need to find as smallest as possible subarray such that GCD operation on that subarray would result in 1.
i.e in above example 3 subset {4,3} is the smallest subset on which GCD operation results in 1.

And the minimum number of GCD operation will be equal to ( ( N + length of minimum subarray having GCD 1 ) - 2 )
i.e in above example 3

N = 5
arr = {2,4,3,5,6}
min-subarray with GCD 1 = {4,3} and length of min subarray = 2
Minimum GCD operations = ( ( 5 + 2 ) - 2 ) = 5
  1. If there is no any subarray having GCD equal 1 then we can't convert array elements to 1 i.e in above example 2 so it will print -1.

Algorithm

The steps to solve the problem is as follows:

  1. Traverse an array and count the number of 1's.
  2. If count of 1 greater than 0, output (N - count of 1).
  3. Else find the minimum length subarray with GCD 1.
    This can be done in two nested loops.
    i) run a outer loop on arr from index i = 0 to N-2 ( i.e secondlast element) and for every outer loop take initial GCD equal to arr[i].
    ii) run an inner loop from index j= i+1 and take GCD until you get GCD 1 or j = N-1.
    If the GCD is 1 then compare the length of subarray i.e j-i+1 with minOperations which contains the min length of subarray having GCD 1 uptill now.
    If j-i+1 is less than minOperations then minOperations = j-i+1, And break the inner loop.
  4. If you get minimum length subarray with GCD 1 then output ( ( N + length of minimum subarray having GCD 1 ) - 2 )
  5. Else output -1.

Implementation

  1. Java program to find minimum GCD operations to convert all elements of array to 1.
import java.util.*;
public class MinOperations
{
    // Driver method
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
	    int n = sc.nextInt();
	    int[] arr = new int[n];
	    for(int i=0; i&ltn; i++){
	        arr[i] = sc.nextInt();
	    }
	    System.out.println(helper(arr,n));
	}
    // Method to count GCD operations.
	public static int CountOperations(int[] arr, int n){
        // Count no of 1's in array
	    int countOne = 0;
	    for(int i=0; i&ltn; i++){
	        if(arr[i] == 1){
	            countOne++ ;
	        }
	    }
        // If there presents 1 in array
	    if(countOne > 0){
	        return n-countOne ;
	    }
        // If there is not any 1 present in array.
        // Find length of smallest subarray having GCD 1.
	    int minOperations = Integer.MAX_VALUE;
	    for(int i=0; i&ltn-1; i++){
	        int gcdResult = arr[i];
	        for(int j=i+1; j&ltn; j++){
	            gcdResult = GCD(arr[j],gcdResult);
	            if(gcdResult == 1){
	                minOperations = Math.min(minOperations,j-i+1);
	                break;
                }
	        }
	    }
       // If there is no any subarray with GCD 1
       // Not possible to convert elements to 1.
	   if(minOperations == Integer.MAX_VALUE){
	        return -1;
	    }
	    return n+minOperations-2;
	}
    // Method to calculate GCD
	public static int GCD(int a , int b){
	    if(b == 0){
	        return a;
	    }
	    else {
	        return GCD(b,a%b);
	    }
   }
}

Time and Space Complexity

Time-Complexity : O(N^2(log N))

O(N^2) in CountOperation method to find all subarray and O(logN) in GCD method to calculate the GCD of two numbers.

Space-Complexity : O(1)

Here there is no use of extra space or data-structure.

With this article at OpenGenus, you must have the complete knowledge to find the Minimum number of GCD operations to make all array elements = 1.