给定一个大小为N的数组A[]，可以用 gcd 该元素及其任何相邻元素。找到使整个数组的元素等于1的此类操作的最小数目。如果无法打印-1。 例如：
null
Input : A[] = {4, 8, 9}Output : 3Explanation: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 : 5Explanation:There is no pair with GCD equal one. We firstconsider (5, 10) and replace 10 with 5. Now arraybecomes { 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 : -1Explanation:Its not possible to make all the element equal to 1.Input : A[] = { 8, 10, 12, 6, 3 }Output : 7
- 如果数组最初包含1，我们的答案是数组的大小和数组中的个数之差。
- 如果数组中没有等于1的元素。我们需要找到GCD等于1的最小子数组。我们的结果是N+（GCD为1的最小子阵列的长度）–1。例如{5,10,2,6}和{8,10,12,6,3}。
我们可以在O（N^2）中找到所有子数组，并且可以在O（logn）中使用 欧几里德算法 . 总体复杂度为O（N^2 logn）。 下面是上述想法的实现。
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> |
输出：
4
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
