最大的子阵列，GCD 1-yiteyi-C++库

有一个包含n个元素的数组。找到GCD等于1的最大子阵列的长度。如果没有GCD为1的子阵列，则打印-1。

null

例如：

Input  : 1 3 5 Output : 3Input : 2 4 6Output :-1

建议：请在“上解决” 实践 “首先，在讨论解决方案之前。

A. 简单解决方案 是考虑每个子阵列，找到其GCD和跟踪最大子阵列与GCD之一。最后返回GCD为1的最大子阵列的长度。

一 有效解决方案 基于这样一个事实，如果任意两个元素的GCD等于一，那么整个数组的GCD为一。所以输出要么是-1要么是数组的长度。

C++

                         // C++ program, to find length of the largest                       
                         // subarray with GCD equals to 1.                       
                         #include<bits/stdc++.h>                       
                         using                                     namespace                                     std;                       
           
                         int                                     findLargest(                                     int                                     arr[],                                     int                                     n)                       
                         {                       
                                                 /*If gcd of any subarray is 1 then gcd of                       
                                                 any number with the sub array will be 1.                       
                                                 so if we are getting any subarray with                       
                                                 gcd 1, then maximum number of element of                       
                                                 the subarray will be equal to the number                       
                                                 of elements of the array. Else it will be -1.*/                       
                                                 int                                     gcd = arr[0];                       
                                                 for                                     (                                     int                                     i=1; i<n; i++)                       
                                                 gcd = __gcd(gcd, arr[i]);                       
           
                                                 return                                     (gcd == 1)? n : -1;                       
                         }                       
           
                         // Driver code                       
                         int                                     main()                       
                         {                       
                                                 int                                     arr[] = {1, 3, 5, 7};                       
                                                 int                                     n =                                     sizeof                                     (arr)/                                     sizeof                                     (                                     int                                     );                       
                                                 cout <<                                     "Length of the largest subarray = "                       
                                                 << findLargest(arr, n);                       
                                                 return                                     0;                       
                         }                       

JAVA

                         // Java program, to find length of the                       
                         // largest subarray with GCD equals to 1.                       
                         class                                     GFG {                       
                                   
                                                 static                                     int                                     ___gcd(                                     int                                     a,                                     int                                     b)                       
                                                 {                       
                                   
                                                 // Everything divides 0                       
                                                 if                                     (a ==                                     0                                     || b ==                                     0                                     )                       
                                                 return                                     0                                     ;                       
                                   
                                                 // base case                       
                                                 if                                     (a == b)                       
                                                 return                                     a;                       
                                   
                                                 // a is greater                       
                                                 if                                     (a > b)                       
                                                 return                                     ___gcd(a - b, b);                       
                                   
                                                 return                                     ___gcd(a, b - a);                       
                                                 }                       
                                   
                                                 static                                     int                                     findLargest(                                     int                                     arr[],                       
                                                 int                                     n)                       
                                                 {                       
                                   
                                                 /*If gcd of any subarray is 1                       
                                                 then gcd of any number with the                       
                                                 sub array will be 1. so if we                       
                                                 are getting any subarray with                       
                                                 gcd 1, then maximum number of                       
                                                 element of the subarray will                       
                                                 be equal to the number of                       
                                                 elements of the array. Else                       
                                                 it will be -1.*/                       
                                                 int                                     gcd = arr[                                     0                                     ];                       
                                   
                                                 for                                     (                                     int                                     i =                                     1                                     ; i < n; i++)                       
                                                 gcd = ___gcd(gcd, arr[i]);                       
                                   
                                                 return                                     (gcd ==                                     1                                     )? n : -                                     1                                     ;                       
                                                 }                       
                                   
                                                 // Driver code                       
                                                 public                                     static                                     void                                     main (String[] args)                       
                                                 {                       
                                                 int                                     arr[] = {                                     1                                     ,                                     3                                     ,                                     5                                     ,                                     7                                     };                       
                                                 int                                     n = arr.length;                       
                                   
                                                 System.out.print(                                     "Length of the "                       
                                                 +                                     "largest subarray = "                       
                                                 + findLargest(arr, n));                       
                                                 }                       
                         }                       
           
                         // This code is contributed by Anant Agarwal.                       

Python3

                         # Python program, to find                       
                         # length of the largest                       
                         # subarray with GCD equals to 1.                       
           
                         def                                     ___gcd(a,b):                       
           
                                                 # Everything divides 0                       
                                                 if                                     (a                                     =                                     =                                     0                                     or                                     b                                     =                                     =                                     0                                     ):                       
                                                 return                                     0                       
                                   
                                                 # base case                       
                                                 if                                     (a                                     =                                     =                                     b):                       
                                                 return                                     a                       
                                   
                                                 # a is greater                       
                                                 if                                     (a > b):                       
                                                 return                                     ___gcd(a                                     -                                     b, b)                       
                                                 return                                     ___gcd(a, b                                     -                                     a)                       
                                   
                         def                                     findLargest(arr, n):                       
           
                                                 '''If gcd of any subarray is 1 then gcd of                       
                                                 any number with the sub array will be 1.                       
                                                 so if we are getting any subarray with                       
                                                 gcd 1, then maximum number of element of                       
                                                 the subarray will be equal to the number                       
                                                 of elements of the array. Else it will be -1.'''                       
                                                 gcd                                     =                                     arr[                                     0                                     ]                       
                                                 for                                     i                                     in                                     range                                     (                                     1                                     ,n):                       
                                                 gcd                                     =                                     ___gcd(gcd, arr[i])                       
                                   
                                                 return                                     n                                     if                                     (gcd                                     =                                     =                                     1                                     )                                     else                                     -                                     1                       
                                   
                         # Driver code                       
                         arr                                     =                                     [                                     1                                     ,                                     3                                     ,                                     5                                     ,                                     7                                     ]                       
                         n                                     =                                     len                                     (arr)                       
           
                         print                                     (                                     "Length of the largest subarray = "                                     ,                       
                                                 findLargest(arr, n))                       
           
                         # This code is contributed                       
                         # by Anant Agarwal.                       

C#

                         // C# program, to find length of the                       
                         // largest subarray with GCD equals to 1.                       
                         using                                     System;                       
           
                         class                                     GFG {                       
                                   
                                                 static                                     int                                     ___gcd(                                     int                                     a,                                     int                                     b)                       
                                                 {                       
                                   
                                                 // Everything divides 0                       
                                                 if                                     (a == 0 || b == 0)                       
                                                 return                                     0;                       
                                   
                                                 // base case                       
                                                 if                                     (a == b)                       
                                                 return                                     a;                       
                                   
                                                 // a is greater                       
                                                 if                                     (a > b)                       
                                                 return                                     ___gcd(a - b, b);                       
                                   
                                                 return                                     ___gcd(a, b - a);                       
                                                 }                       
                                   
                                                 static                                     int                                     findLargest(                                     int                                     []arr,                       
                                                 int                                     n)                       
                                                 {                       
                                   
                                                 // If gcd of any subarray is 1                       
                                                 // then gcd of any number with the                       
                                                 // sub array will be 1. so if we                       
                                                 // are getting any subarray with                       
                                                 // gcd 1, then maximum number of                       
                                                 // element of the subarray will                       
                                                 // be equal to the number of                       
                                                 // elements of the array. Else                       
                                                 // it will be -1.                       
                                                 int                                     gcd = arr[0];                       
                                   
                                                 for                                     (                                     int                                     i = 1; i < n; i++)                       
                                                 gcd = ___gcd(gcd, arr[i]);                       
                                   
                                                 return                                     (gcd == 1)? n : -1;                       
                                                 }                       
                                   
                                                 // Driver code                       
                                                 public                                     static                                     void                                     Main ()                       
                                                 {                       
                                                 int                                     []arr = {1, 3, 5, 7};                       
                                                 int                                     n = arr.Length;                       
                                   
                                                 Console.Write(                                     "Length of the "                       
                                                 +                                     "largest subarray = "                       
                                                 + findLargest(arr, n));                       
                                                 }                       
                         }                       
           
                         // This code is contributed by Nitin Mittal.                       

PHP

                         <?php                       
                         // PHP program, to find length                       
                         // of the largest subarray with                       
                         // GCD equals to 1.                       
                         function                                     ___gcd(                                     $a                                     ,                                     $b                                     )                       
                         {                       
                                                 // Everything divides 0                       
                                                 if                                     (                                     $a                                     == 0 ||                                     $b                                     == 0)                       
                                                 return                                     0;                       
           
                                                 // base case                       
                                                 if                                     (                                     $a                                     ==                                     $b                                     )                       
                                                 return                                     $a                                     ;                       
           
                                                 // a is greater                       
                                                 if                                     (                                     $a                                     >                                     $b                                     )                       
                                                 return                                     ___gcd(                                     $a                                     -                                     $b                                     ,                                     $b                                     );                       
                                   
                                                 return                                     ___gcd(                                     $a                                     ,                                     $b                                     -                                     $a                                     );                       
                         }                       
           
                         function                                     findLargest(                                     $arr                                     ,                                     $n                                     )                       
                         {                       
                                   
                                                 /*If gcd of any subarray is 1                       
                                                 then gcd of any number with the                       
                                                 sub array will be 1. so if we                       
                                                 are getting any subarray with                       
                                                 gcd 1, then maximum number of                       
                                                 element of the subarray will                       
                                                 be equal to the number of                       
                                                 elements of the array. Else                       
                                                 it will be -1.*/                       
                                                 $gcd                                     =                                     $arr                                     [0];                       
                                   
                                                 for                                     (                                     $i                                     = 1;                                     $i                                     <                                     $n                                     ;                                     $i                                     ++)                       
                                                 $gcd                                     = ___gcd(                                     $gcd                                     ,                                     $arr                                     [                                     $i                                     ]);                       
           
                                                 return                                     (                                     $gcd                                     == 1)?                                     $n                                     : -1;                       
                         }                       
           
                         // Driver code                       
                         $arr                                     =                                     array                                     (1, 3, 5, 7);                       
                         $n                                     =                                     count                                     (                                     $arr                                     );                       
           
                         echo                                     "Length of the "                                     .                       
                                                 "largest subarray = "                                     .                       
                                                 findLargest(                                     $arr                                     ,                                     $n                                     );                       
           
                         // This code is contributed by Sam007                       
                         ?>                       

Javascript

                         <script>                       
           
                         // Javascript program, to find length of the                       
                         // largest subarray with GCD equals to 1.                       
                                   
                                                 function                                     ___gcd(a, b)                       
                                                 {                       
                                   
                                                 // Everything divides 0                       
                                                 if                                     (a == 0 || b == 0)                       
                                                 return                                     0;                       
                                   
                                                 // base case                       
                                                 if                                     (a == b)                       
                                                 return                                     a;                       
                                   
                                                 // a is greater                       
                                                 if                                     (a > b)                       
                                                 return                                     ___gcd(a - b, b);                       
                                   
                                                 return                                     ___gcd(a, b - a);                       
                                                 }                       
                                   
                                                 function                                     findLargest(arr, n)                       
                                                 {                       
                                   
                                                 /*If gcd of any subarray is 1                       
                                                 then gcd of any number with the                       
                                                 sub array will be 1. so if we                       
                                                 are getting any subarray with                       
                                                 gcd 1, then maximum number of                       
                                                 element of the subarray will                       
                                                 be equal to the number of                       
                                                 elements of the array. Else                       
                                                 it will be -1.*/                       
                                                 let gcd = arr[0];                       
                                   
                                                 for                                     (let i = 1; i < n; i++)                       
                                                 gcd = ___gcd(gcd, arr[i]);                       
                                   
                                                 return                                     (gcd == 1)? n : -1;                       
                                                 }                       
                                   
           
                         // Driver Code                       
                                   
                                                 let arr = [1, 3, 5, 7];                       
                                                 let n = arr.length;                       
                                   
                                                 document.write(                                     "Length of the "                       
                                                 +                                     "largest subarray = "                       
                                                 + findLargest(arr, n));                       
                                   
                         </script>                       

输出：

Length of the largest subarray = 4

本文由 斯马拉克·乔普达尔 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用写极客。组织或者把你的文章寄去评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章