GCD为1的最大子集-yiteyi-C++库

给定n个整数，我们需要找到最大子集的大小 GCD 等于1。输入约束：

null

n <= 10^5A[i] <= 10^5

例如：

Input : A = {2, 3, 5}Output : 3Input : A = {3, 18, 12}Output : -1

推荐：请尝试你的方法 {IDE} 首先，在进入解决方案之前。

天真的解决方案：

我们发现 GCD 并找到GCD为1的最大子集。所用的总时间将等于评估所有可能子集的GCD所用的时间。可能的子集总数为2 ^N 在最坏的情况下，子集中有n个元素，计算其GCD所需的时间为n*log（n）容纳当前子集所需的额外空间为O（n）

Time complexity : O(n * log(n) * 2^n)Space Complexity : O(n)

优化的O（n）解决方案：

假设我们找到一个GCD为1的子集，如果我们在其中添加一个新元素，那么GCD仍然为1。因此，如果存在GCD为1的子集，则完整集合的GCD也为1。因此，我们首先找到全集的GCD，如果它是1，那么全集就是子集，否则就不存在GCD为1的子集。

C++

                         // C++ program to find size of the largest subset with GCD 1                       
                         #include <iostream>                       
                         using                                     namespace                                     std;                       
           
                         // Function to return gcd of a and b                       
                         int                                     gcd(                                     int                                     a,                                     int                                     b)                       
                         {                       
                                                 if                                     (a == 0)                       
                                                 return                                     b;                       
                                                 return                                     gcd(b%a, a);                       
                         }                       
           
                         // Function to find largest subset with GCD 1                       
                         int                                     largestGCD1Subset(                                     int                                     A[],                                     int                                     n)                       
                         {                       
                                                 // finding gcd of whole array                       
                                                 int                                     currentGCD = A[0];                       
                                                 for                                     (                                     int                                     i=1; i<n; i++)                       
                                                 {                       
                                                 currentGCD = gcd(currentGCD, A[i]);                       
           
                                                 // If current GCD becomes 1 at any momemnt,                       
                                                 // then whole array has GCD 1.                       
                                                 if                                     (currentGCD == 1)                       
                                                 return                                     n;                       
                                                 }                       
           
                                                 return                                     0;                       
                         }                       
           
                         // Driver program to test above function                       
                         int                                     main()                       
                         {                       
                                                 int                                     A[] = {2, 18, 6, 3};                       
                                                 int                                     n =                                     sizeof                                     (A)/                                     sizeof                                     (A[0]);                       
                                                 cout << largestGCD1Subset(A, n);                       
                                                 return                                     0;                       
                         }                       

JAVA

                         // Java program to find size of the                       
                         // largest subset with GCD 1                       
                         import                                     java.*;                       
           
                         class                                     GFG {                       
                                   
                                                 // Function to return gcd of                       
                                                 // a and b                       
                                                 static                                     int                                     gcd(                                     int                                     a,                                     int                                     b)                       
                                                 {                       
                                                 if                                     (a ==                                     0                                     )                       
                                                 return                                     b;                       
                                                 return                                     gcd(b % a, a);                       
                                                 }                       
           
                                                 // Function to find largest                       
                                                 // subset with GCD 1                       
                                                 static                                     int                                     largestGCD1Subset(                                     int                                     A[],                       
                                                 int                                     n)                       
                                                 {                       
                                   
                                                 // finding gcd of whole array                       
                                                 int                                     currentGCD = A[                                     0                                     ];                       
                                   
                                                 for                                     (                                     int                                     i=                                     1                                     ; i<n; i++)                       
                                                 {                       
                                                 currentGCD =                       
                                                 gcd(currentGCD, A[i]);                       
                                   
                                                 // If current GCD becomes 1                       
                                                 // at any momemnt, then whole                       
                                                 // array has GCD 1.                       
                                                 if                                     (currentGCD ==                                     1                                     )                       
                                                 return                                     n;                       
                                                 }                       
                                   
                                                 return                                     0                                     ;                       
                                                 }                       
                                   
                                                 // Driver code                       
                                                 public                                     static                                     void                                     main (String[] args)                       
                                                 {                       
                                                 int                                     A[] = {                                     2                                     ,                                     18                                     ,                                     6                                     ,                                     3                                     };                       
                                                 int                                     n =A.length;                       
                                   
                                                 System.out.println(                       
                                                 largestGCD1Subset(A, n) );                       
                                                 }                       
                         }                       
           
                         // This code is contributed by Sam007.                       

Python3

                         # python program to find size of the                       
                         # largest subset with GCD 1                       
           
                         # Function to return gcd of a and b                       
                         def                                     gcd( a, b):                       
                                   
                                                 if                                     (a                                     =                                     =                                     0                                     ):                       
                                                 return                                     b                       
                                   
                                                 return                                     gcd(b                                     %                                     a, a)                       
           
           
                         # Function to find largest subset                       
                         # with GCD 1                       
                         def                                     largestGCD1Subset(A, n):                       
                                   
                                                 # finding gcd of whole array                       
                                                 currentGCD                                     =                                     A[                                     0                                     ];                       
                                                 for                                     i                                     in                                     range                                     (                                     1                                     , n):                       
                                   
                                                 currentGCD                                     =                                     gcd(currentGCD, A[i])                       
           
                                                 # If current GCD becomes 1 at                       
                                                 # any momemnt, then whole                       
                                                 # array has GCD 1.                       
                                                 if                                     (currentGCD                                     =                                     =                                     1                                     ):                       
                                                 return                                     n                       
                                                 return                                     0                       
           
                         # Driver code                       
                         A                                     =                                     [                                     2                                     ,                                     18                                     ,                                     6                                     ,                                     3                                     ]                       
                         n                                     =                                     len                                     (A)                       
                         print                                     (largestGCD1Subset(A, n))                       
           
                         # This code is Contributed by Sam007.                       

C#

                         // C# program to find size of the                       
                         // largest subset with GCD 1                       
                         using                                     System;                       
                                   
                         public                                     class                                     GFG {                       
                                   
                                                 // Function to return gcd of                       
                                                 // a and b                       
                                                 static                                     int                                     gcd(                                     int                                     a,                                     int                                     b)                       
                                                 {                       
                                                 if                                     (a == 0)                       
                                                 return                                     b;                       
                                                 return                                     gcd(b % a, a);                       
                                                 }                       
           
                                                 // Function to find largest subset                       
                                                 // with GCD 1                       
                                                 static                                     int                                     largestGCD1Subset(                                     int                                     []A,                       
                                                 int                                     n)                       
                                                 {                       
                                   
                                                 // finding gcd of whole array                       
                                                 int                                     currentGCD = A[0];                       
                                                 for                                     (                                     int                                     i = 1; i < n; i++)                       
                                                 {                       
                                                 currentGCD =                       
                                                 gcd(currentGCD, A[i]);                       
                                   
                                                 // If current GCD becomes 1 at                       
                                                 // any momemnt, then whole                       
                                                 // array has GCD 1.                       
                                                 if                                     (currentGCD == 1)                       
                                                 return                                     n;                       
                                                 }                       
                                   
                                                 return                                     0;                       
                                                 }                       
                                   
                                                 // Driver method                       
                                                 public                                     static                                     void                                     Main()                       
                                                 {                       
                                                 int                                     []A = {2, 18, 6, 3};                       
                                                 int                                     n = A.Length;                       
                                   
                                                 Console.Write(                       
                                                 largestGCD1Subset(A, n));                       
                                                 }                       
                         }                       
           
                         // This code is contributed by Sam007.                       

PHP

                         <?php                       
           
                         // php program to find size of the                       
                         // largest subset with GCD 1                       
           
                         // Function to return gcd of a and b                       
                         function                                     gcd(                                     $a                                     ,                                     $b                                     )                       
                         {                       
                                                 if                                     (                                     $a                                     == 0)                       
                                                 return                                     $b                                     ;                       
                                                 return                                     gcd(                                     $b                                     %                                     $a                                     ,                                     $a                                     );                       
                         }                       
           
                         // Function to find largest subset                       
                         // with GCD 1                       
                         function                                     largestGCD1Subset(                                     $A                                     ,                                     $n                                     )                       
                         {                       
                                   
                                                 // finding gcd of whole array                       
                                                 $currentGCD                                     =                                     $A                                     [0];                       
                                                 for                                     (                                     $i                                     = 1;                                     $i                                     <                                     $n                                     ;                                     $i                                     ++)                       
                                                 {                       
                                                 $currentGCD                                     =                       
                                                 gcd(                                     $currentGCD                                     ,                                     $A                                     [                                     $i                                     ]);                       
           
                                                 // If current GCD becomes 1                       
                                                 // at any momemnt, then                       
                                                 // whole array has GCD 1.                       
                                                 if                                     (                                     $currentGCD                                     == 1)                       
                                                 return                                     $n                                     ;                       
                                                 }                       
           
                                                 return                                     0;                       
                         }                       
           
                         // Driver program                       
                         $A                                     =                                     array                                     (2, 18, 6, 3);                       
                         $n                                     = sizeof(                                     $A                                     );                       
                         echo                                     largestGCD1Subset(                                     $A                                     ,                                     $n                                     );                       
                                   
                         // This code is contributed by ajit                       
                         ?>                       

Javascript

                         <script>                       
           
                         // Javascript program to find size of the                       
                         // largest subset with GCD 1                       
           
                         // Function to return gcd of a and b                       
                         function                                     gcd(a, b)                       
                         {                       
                                                 if                                     (a == 0)                       
                                                 return                                     b;                       
                                                 return                                     gcd(b % a, a);                       
                         }                       
           
                         // Function to find largest subset                       
                         // with GCD 1                       
                         function                                     largestGCD1Subset(A, n)                       
                         {                       
                                   
                                                 // finding gcd of whole array                       
                                                 let currentGCD = A[0];                       
                                                 for                                     ( let i = 1; i < n; i++)                       
                                                 {                       
                                                 currentGCD =                       
                                                 gcd(currentGCD, A[i]);                       
           
                                                 // If current GCD becomes 1                       
                                                 // at any momemnt, then                       
                                                 // whole array has GCD 1.                       
                                                 if                                     (currentGCD == 1)                       
                                                 return                                     n;                       
                                                 }                       
           
                                                 return                                     0;                       
                         }                       
           
                         // Driver program                       
                         let A = [2, 18, 6, 3];                       
                         let n = A.length;                       
                         document.write(largestGCD1Subset(A, n));                       
                                   
                         // This code is contributed by _saurabh_jaiswal                       
           
                         </script>                       

输出：

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

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

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

THE END

技术文章