大小为 k 的子序列的最大可能最大公约数

问题陈述中说，我们将得到一个数组作为输入和一个正整数 K，我们需要在这个问题中找出数组的 k 大小子序列的最大可能最大公约数（最大公约数）。可以使用不同的算法来求数字的最大公约数，并找出 k 大小子序列的最大公约数。

在此之前，我们必须了解数组的子序列。数组的子序列是数组中数字的一个序列，这些数字不一定是数组中的相邻数字，但序列中数字的顺序必须与它们在数组中的顺序相同，才能被称为数组的子序列。子序列在本质上可能是连续的，也可能是不连续的。

例如，a=[1,2,3,4,5,6]。[1, 2, 5] 是数组 a 的一个子序列。在这个问题中，我们需要找到数组 a[] 的大小为 K 的正确子序列，使得该子序列的最大公约数是在所有大小为 K 的子序列中最大可能的公约数。通过以下示例可以更好地理解该问题：

输入：a=[5, 2, 6, 10, 12]，K=2

输出 : 6

说明：6 是大小为 K（即 2）的子序列的最大可能最大公约数。6 是 [6,12] 的最大公约数。也可能存在其他子序列，例如 [5,10]、[10,12] 等等。但 [5,10] 的最大公约数是 5，[10,12] 的最大公约数是 2。因此，6 是所有大小为 2 的子序列中最大可能的公约数。

输入：a=[1,2,3,4,5]，K=3

输出 : 1

说明：给定子序列的大小为 3。任何大小为 3 的可能子序列的最大公约数都只有 1。因此，1 是我们的输出。

让我们看看可以用来解决此问题的算法。

算法

解决此问题的朴素方法可以是生成所有可能的 k 大小子序列，然后计算每个子序列的最大公约数。在所有计算出的最大公约数中找到的最大公约数将是我们的答案。由于该算法仅适用于小型数组，因此我们不能将其用作解决此问题的方法。

解决此问题的有效方法可以是：

  • 我们将创建一个大小等于数组中最大元素+1 的数组。

  • 我们可以使用 C++ 中内置的 *max_element() 函数找到数组中存在的最大元素，该函数返回给定范围内的最大元素。

语法

int x= *max_element(arr, arr+n); //n is the size of the array

  • 我们将在给定数组中从 i=0 到 i=array.size() 的 for 循环中迭代，以计算数组中每个元素的除数个数。

  • 在嵌套的 for 循环中从 j=1 到 sqrt(a[i]) 迭代，因为在数学中，每个有两个因子的数字都至少有一个因子小于该数字的平方根。

  • 如果 j 可以整除数字 a[i]，则通过向其添加 1 来更新我们在 j 索引处创建的数组中的值。然后，如果它不等于 j，则还将数组中 (a[i]/j) 索引处的值更新为 1，因为如果 j 可以整除 a[i] 得到某个数字，则该数字也将是 a[i] 的除数 (a[i]/j=x 或 a[i]/x=j)。

  • 最后，在迭代给定数组中的所有元素后，我们将迭代我们创建并存储值的数组。从最后一个元素迭代数组并检查该索引处的值是否大于或等于 K。

  • 如果在从后向前迭代时，任何索引处的值都大于或等于 K，则该索引将是我们所需的答案，因为数组中任何索引处的每个数字都表示给定数组中索引值可以整除的元素的数量。因此，从后向前迭代将为我们提供可以整除给定数组中 K 个或更多数字的最大可能数字。

现在让我们在我们的方法中实现此算法来解决问题。

Explore our latest online courses and learn new skills at your own pace. Enroll and become a certified expert to boost your career.

方法

我们将遵循以下步骤来解决上述问题：

  • 初始化一个函数来计算大小为 K 的子序列的最大可能最大公约数。

  • 将给定数组的最大元素存储在变量 m 中。

  • 创建一个大小为 m+1 的数组，count[m+1]。

  • 在 for 循环中从 i=0 迭代到数组的大小。

  • 在嵌套的 for 循环中，从 j=1 迭代到 sqrt(a[i]) 并检查 j 的每个值，以查看它是否可以整除 a[i]。

  • 如果可以整除，则将 count 中 j 索引处的值增加 1。还要检查 j 是否不等于 (a[i]/j)，如果是，则将 (a[i]/j) 索引处的值也增加 1。

  • 然后，在所有迭代完成后，再次迭代更新所有所需值后的 count。

  • 从后向前迭代 count，直到 i 大于或等于 1，因为 0 不能整除任何数字。我们遇到的第一个值大于或等于 K 的索引，该索引值将是我们的答案。

  • 返回该索引作为输出。

示例

在 C++ 中实现该方法：

Open Compiler
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
//function to calculate maximum gcd possible of subsequence of size K
int maximum_gcd(int a[], int N, int K){
   int m = *max_element(a,a+N); //store maximum element present in the array
   int count[m+1]={0}; //create an array to store count of every divisor
   for(int i=0;i<N;i++){ //iterate in the given array
      for(int j=1;j<=sqrt(a[i]);j++){ //to get every possible divisor of the given number in the array
         if(a[i]%j==0){
            //if it is a divisor of the number, update the count
            count[j]=count[j]+1;
            if(a[i]/j != j){ //a[i]/j is also the divisor of the number if j divides a[i]
               count[a[i]/j] = count[a[i]/j] + 1;
            }
         }
      }
   }
   int ans; //to store maximum gcd of subsequence of size K
   for(int i=m;i>=1;--i){ //iterating from to get the maximum value
      if(count[i]>=K){ //if value at index is greater than or equal to K
         ans = i; //the index must be the gcd of atleast one K-sized subsequence
         break;
      }
   }
   return ans; //return the answer
}
int main(){
   int a[]={8,10,3,15,20,9};
   int K=3;
   int N = sizeof(a)/sizeof(a[0]); //to calculate the size of the given array
   cout<<maximum_gcd(a,N,K)<<endl;
   return 0;
}

输出

5

时间复杂度：O(𝑁 × 𝑠𝑞𝑟𝑡(𝑚))，其中 N 是给定数组的大小，m 是数组中存在的最大元素。

空间复杂度：O(m+1)，其中 m 是给定数组中存在的最大元素。

结论

我们讨论了使用不同的函数和方法在 C++ 中解决查找大小为 K 的子序列的最大可能最大公约数（最大公约数）的问题。从朴素方法到有效方法，我们讨论了如何在 C++ 中解决上述问题。

希望本文能帮助您解决您对该问题的理解。

更新于： 2023年3月16日

661 次浏览

开启您的 职业生涯

通过完成课程获得认证

开始学习
广告