Java 中不同子序列的 GCD

2024年9月10日 | 阅读 6 分钟

给定一个包含正数的数组 inArr。任务是找到输入数组中所有存在的子序列中不同的 GCD（最大公约数）的数量。注意，数组的子序列是通过一次选取一个或多个元素形成的。

示例 1

输入

int inArr[] = {6, 8, 10}

输出 4

解释：输入数组的不同子序列及其 GCD 为

对于子序列 {6}，GCD 为 6。

对于子序列 {8}，GCD 为 8。

对于子序列 {10}，GCD 为 10。

对于子序列 {6, 8}，GCD 为 2。

对于子序列 {8, 10}，GCD 为 2。

对于子序列 {6, 10}，GCD 为 2。

对于子序列 {6, 8, 10}，GCD 为 2。

因此，所有计算出的 GCD 为 6、8、10、2、2、2、2，其中只有 4 个是唯一的（6、8、10、2）。因此，输出为 4。

示例 2

输入

int inArr[] = {2, 4, 8}

输出 3

解释：输入数组的不同子序列及其 GCD 为

对于子序列 {2}，GCD 为 2。

对于子序列 {4}，GCD 为 4。

对于子序列 {8}，GCD 为 8。

对于子序列 {2, 4}，GCD 为 2。

对于子序列 {4, 8}，GCD 为 4。

对于子序列 {2, 8}，GCD 为 2。

对于子序列 {2, 4, 8}，GCD 为 2。

因此，所有计算出的 GCD 为 2、4、8、2、4、2、2，其中只有 3 个是唯一的（2、4、8）。因此，输出为 3。

方法：暴力法

在此方法中，我们将计算输入数组的所有子序列，并将这些子序列存储在 ArrayList 中。然后，我们将计算存储在 ArrayList 中的所有子序列的 GCD，并将它们放入一个 Set 中。由于 Set 只包含唯一元素，Set 的大小就是我们的答案。为了找到子序列，我们将使用递归。观察以下程序。

文件名：DiffSubseqGCD.java

// important import statements
import java.util.ArrayList;
import java.util.Set;
import java.util.HashSet;


public class DiffSubseqGCD 
{
ArrayList<ArrayList<Integer>> al = new ArrayList<ArrayList<Integer>>();
Set<Integer> st = new HashSet<Integer>();

public void findSubseq(int arr[], int size, int i, ArrayList<Integer> temp) 
{
// handling the base case
if(i >= size)
{

// adding elements to the 2-d array list
ArrayList<Integer> t = new ArrayList<Integer>();
for(int idx = 0; idx < temp.size(); idx++)
{
t.add(temp.get(idx));
}
al.add(t);
return;
}

temp.add(arr[i]);
// including the elements in the temp subarray list
findSubseq(arr, size, i + 1, temp);
int index = temp.size() - 1;
temp.remove(index);
// ignoring the elements in the temp subarray list
findSubseq(arr, size, i + 1, temp);
}

// method for finding the GCD of the two
// numbers a1 and a2 recursively
public int findGCD(int a1, int a2)
{
// handling the base case
if(a1 == 0)
{
return a2;
}

// recursively finding the GCD of two numbers a1 and a2
return findGCD(a2 % a1, a1);
}

public void findGCDSubSeq(ArrayList<Integer> al1)
{
// if the array list is empty
// there is no need to find the GCD
if(al1.size() == 0)
{
return;
}

// For only one element in the array list
// the GCD is considered to be the element itself
if(al1.size() == 1)
{

st.add(al1.get(0));
return;
}


int t1 = al1.get(0);
int t2 = al1.get(1);
int t = findGCD(t1, t2);
for(int i = 2; i < al1.size(); i++)
{
t = findGCD(t, al1.get(i));
}

st.add(t);
}
public void findGCDUtil()
{
int size = al.size();

for(int i = 0; i < size; i++)
{
findGCDSubSeq(al.get(i));
}
}
// main method
public static void main(String argvs[])
{
// creating an object of the class DiffSubseqGCD 
DiffSubseqGCD obj = new DiffSubseqGCD();
// input 1
int inArr[] = {6, 8, 10};
int size = inArr.length;
ArrayList<Integer> temp = new ArrayList<Integer>();
obj.findSubseq(inArr, size, 0, temp);
obj.findGCDUtil();
System.out.println("For the input array: ");
for(int i = 0; i < size; i++)
{
System.out.print(inArr[i] + " ");
}
System.out.println();
System.out.println("The total number of unique GCDs is: " + obj.st.size());
System.out.println();
obj.st = new HashSet<Integer>();
obj.al = new ArrayList<ArrayList<Integer>>();
// input 2
int inArr1[] = {2, 4, 8};
size = inArr1.length;
temp = new ArrayList<Integer>();
obj.findSubseq(inArr1, size, 0, temp);
obj.findGCDUtil();
System.out.println("For the input array: ");
for(int i = 0; i < size; i++)
{
System.out.print(inArr1[i] + " ");
}
System.out.println();
System.out.println("The total number of unique GCDs is: " + obj.st.size());
}
}

输出

For the input array: 
6 8 10 
The total number of unique GCDs is: 4

For the input array: 
2 4 8 
The total number of unique GCDs is: 3

复杂度分析：每次递归调用都会导致另外两次递归调用。因此，程序的 time complexity 是指数级的。程序的 space complexity 也是指数级的。

上述程序不适用于较大的输入，因为程序的 time complexity 和 space complexity 都太高了。因此，我们必须进行一些优化来降低 time complexity 和 space complexity。

高效方法

使用贪心方法，我们可以进行优化。我们必须利用这样的事实：任何两个数字 n1 和 n2 的 GCD 介于 1 到 max(n1, n2) 之间，并且对于包含两个以上元素的任何子序列，相同的概念也成立。如果子序列中的最大元素是 M，则 GCD 始终落在 [1, M] 的范围内。因此，我们可以从 1 到 M 进行迭代，如果给定范围内的任何数字是数组中某个元素的因子，那么我们可以将该元素显示为 GCD 的一个结果。

文件名：DiffSubseqGCD1.java

// important import statements
import java.util.ArrayList;
import java.util.Set;
import java.util.HashSet;

public class DiffSubseqGCD1 
{
// method for finding the GCD of the two
// numbers a1 and a2 recursively
public int findGCD(int a1, int a2)
{
// handling the base case
if(a1 == 0)
{
return a2;
}

// recursively finding the GCD of two numbers a1 and a2
return findGCD(a2 % a1, a1);
}

// A method for finding the different GCDs
public int findGCDsSubseq(ArrayList<Integer> arrList)
{

// for storing all the GCDs that are possible
ArrayList<Integer> answer = new ArrayList<Integer>();

// Stores all array elements in set
HashSet<Integer> hs = new HashSet<Integer>();
for(int i = 0; i < arrList.size(); i++)
{
hs.add(arrList.get(i));
}

int Max = Integer.MIN_VALUE;
for(int i = 0; i < arrList.size(); i++)
{
if (arrList.get(i) > Max)
{
Max = arrList.get(i);
}
}   

// Iterating from 1 to M
for(int j = 1; j <= Max; j++)
{
int computeGCD = 0;

// Checking whether k could be the GCD of any of the subsequence if i can be the GCD of
// any subsequence
for(int k = j; k < Max + 1; k += j)
{
if (hs.contains(k))
{
computeGCD = findGCD(computeGCD, k);
}
}
if (computeGCD == j)
{
answer.add(j);
}
}
return answer.size();
}


// main method
public static void main(String argvs[])
{
// creating an object of the class DiffSubseqGCD1 
DiffSubseqGCD1 obj = new DiffSubseqGCD1();

// input 1
ArrayList<Integer> arrList = new ArrayList<Integer>();
arrList.add(6);
arrList.add(8);
arrList.add(10);
int size = arrList.size();
int answer = obj.findGCDsSubseq(arrList);

System.out.println("For the input array: ");
for(int i = 0; i < size; i++)
{
System.out.print(arrList.get(i) + " ");
}
System.out.println();
System.out.println("The total number of unique GCDs is: " + answer);


System.out.println();

// input 2
ArrayList<Integer> arrList1 = new ArrayList<Integer>();
arrList1.add(2);
arrList1.add(4);
arrList1.add(8);
size = arrList1.size();
answer = obj.findGCDsSubseq(arrList1);

System.out.println("For the input array: ");
for(int i = 0; i < size; i++)
{
System.out.print(arrList1.get(i) + " ");
}
System.out.println();
System.out.println("The total number of unique GCDs is: " + answer);

}

}

输出

For the input array: 
6 8 10 
The total number of unique GCDs is: 4

For the input array: 
2 4 8 
The total number of unique GCDs is: 3

复杂度分析：程序的 time complexity 为 O(Max * log(Max))，其中 Max 是数组的最大元素。程序的 space complexity 为 O(N)，其中 N 是 ArrayList 中存在的元素总数。

下一个主题Java 中的 Sylvester Sequence

← 上一个下一个 →

Java 中不同子序列的 GCD

方法：暴力法

高效方法

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

Java Conversion

Java Misc

Java 中不同子序列的 GCD

方法：暴力法

高效方法

相关帖子

DecimalStyle getDecimalSeparator() method in Java with Examples

Java 中模拟 N 个骰子滚动器的程序

Java 中的拼写检查器

Advantages and Disadvantages of Inheritance in Java

Java 中的抽象语法树 (AST)

Fork Join in Java

Java 中的帕斯卡三角形程序

Can We Have Multiple Main Methods in Java?

RuleBasedCollator equals() method in Java with Example

next() vs nextLine()

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器