Java 中的 Zumkeller 数

2025年4月10日 | 阅读 12 分钟

如果一个数 N 的所有因子可以被分成两个集合，使得第一个集合中因子的和等于第二个集合中因子的和，则称 N 为 Zumkeller 数。这两个集合都必须是非空集。让我们通过几个例子来理解一下。输入时会给出数字 N。

示例 1

输入: N = 84

输出: 是，84 是一个 Zumkeller 数。

解释: 84 的因子是：1, 2, 3, 4, 6, 7, 12, 14, 21, 28, 42, 84。现在，如果我们把这些因子分成两个集合，如下所示，我们得到：

(28, 84) 和 (1, 2, 3, 4, 6, 7, 12, 14, 21, 42)。现在，第一个集合元素的和为 28 + 84 = 112

第二个集合元素的和为：

1 + 2 + 3 + 4 + 6 + 7 + 12 + 14 + 21 + 42 = 112。由于这两个集合元素的和相等，所以数字 84 是一个 Zumkeller 数。

示例 2

输入: N = 108

输出: 是，108 是一个 Zumkeller 数。

解释: 108 的因子是：1, 2, 3, 4, 6, 9, 12, 18, 27, 36, 54, 108。现在，如果我们把这些因子分成两个集合，如下所示，我们得到：

(2, 3, 27, 108) 和 (1, 4, 6, 9, 12, 18, 36, 54)。现在，第一个集合元素的和为 2 + 3 + 27 + 108 = 140

第二个集合元素的和为：

1 + 4 + 6 + 9 + 12 + 18 + 36 + 54 = 140。由于这两个集合元素的和相等，所以数字 108 是一个 Zumkeller 数。

示例 3

输入: N = 200

输出: 否，200 不是一个 Zumkeller 数。

解释: 200 的因子是：1, 2, 4, 5, 8, 10, 20, 25, 40, 50, 100, 200。现在，如果我们把这些因子分成任何两个集合，我们都无法找到一对集合，使其元素的和相等。因此，200 不是一个 Zumkeller 数。

朴素方法

方法很简单。首先，我们将找到数字 N 的所有因子并将其存储在一个数组中。同时，计算数组中元素的总和并将其存储在一个名为 totalSum 的变量中。然后，我们将计算所有可能的集合，并将它们存储在二维数组中。迭代二维数组，并在每次迭代中逐个计算集合的总和。我们将其存储在一个名为 setSum 的变量中。然后，用 totalSum 减去 setSum，得到的差值如果与 setSum 匹配，则数字 N 是 Zumkeller 数。如果不匹配，请对其他迭代重复上述过程。如果所有迭代都已完成，并且没有一次迭代得到 totalSum - setSum 等于 setSum 的值，那么我们可以说 N 不是 Zumkeller 数。

文件名: ZumkellerNaive.java

// importing ArrayList
import java.util.ArrayList;
public class ZumkellerNaive
{
ArrayList<Integer> al;
void findFactors(int n)
{
int range = (int)Math.sqrt(n);
al = new ArrayList<Integer>();
// finding the factors and 
// storing it in the list al
for(int i = 1; i <= range; i++)
{
if((n % i) == 0)
{
    al.add(i);
    if((n / i) != i)
    {
        al.add(n / i);
    }
}
}
}

boolean isZumkeller()
{
int totalSum = 0;
int size = al.size();

// sum of all the factors of the number n
for(int i = 0; i < size; i++)
{
    totalSum = totalSum + al.get(i);
}

// if the sum of elements of the first set
// is equal to the sum of elements of the second set
// then it means the sum of all the elements, including the first
// and the second subset should be even. Otherwise, we can say that the 
// number is not the Zumkeller number
if((totalSum % 2) != 0)
{
    return false;
}

// for storing all the subsets
ArrayList<ArrayList<Integer>> twoDmnslAl = new ArrayList<ArrayList<Integer>>();

// for storing the current subsets
ArrayList<Integer> oneDmnslAl = new ArrayList<Integer>();

findSubsets(0, size, al, oneDmnslAl, twoDmnslAl);

// iterating over all the subsets present 
// in the two-dimensional array list
for(int i = 0; i < twoDmnslAl.size(); i++)
{
    oneDmnslAl = twoDmnslAl.get(i);
    size = oneDmnslAl.size();
    int setSum = 0;
    
    // iterating over the subset present
    // at the index i
    // the elements of the subset are 
    // considered as the first set
    // remaining elements consist of the second set
    for(int j = 0; j < size; j++)
    {
        // finding the sum of elements of the first set
        setSum = setSum + oneDmnslAl.get(j);
    }
    
    // totalSum - setSum consists of the sum of elements
    // of the second set
    if((totalSum - setSum) == setSum)
    {
        return true;
    }
}

return false;
    
}

void findSubsets(int i, int s, ArrayList<Integer> factors, ArrayList<Integer> temp, ArrayList<ArrayList<Integer>> alSubsets)
{
// handling the base case
if(i >= s)
{
    ArrayList<Integer> a = new ArrayList<Integer>();
    
    for(int j = 0; j < temp.size(); j++)
    {
        a.add(temp.get(j));
    }
    alSubsets.add(a);
    
    return;
}

// for finding the subsets
// first, we will include the element located at the index i
// and then we will exclude the element located at the index i

temp.add(factors.get(i)); // including the element 
findSubsets(i + 1, s, factors, temp, alSubsets);
temp.remove(temp.size() - 1); // excluding the element
findSubsets(i + 1, s, factors, temp, alSubsets);

    
}
// main method
public static void main(String argvs[]) 
{
// instantiating the class ZumkellerNaive
ZumkellerNaive obj = new ZumkellerNaive();
int n = 84; // first input
obj.findFactors(n);
boolean ans = obj.isZumkeller();
if(ans)
{
    System.out.println("Yes, " + n + " is a Zumkeller number.");
}
else
{
    System.out.println("No, " + n + " is not a Zumkeller number.");
}

n = 108; // second input
obj.findFactors(n);
ans = obj.isZumkeller();
if(ans)
{
    System.out.println("Yes, " + n + " is a Zumkeller number.");
}
else
{
    System.out.println("No, " + n + " is not a Zumkeller number.");
}

 n = 200; // third input

obj.findFactors(n);
ans = obj.isZumkeller();
if(ans)
{
    System.out.println("Yes, " + n + " is a Zumkeller number.");
}
else
{
    System.out.println("No, " + n + " is not a Zumkeller number.");
}
}
}

输出

Yes, 84 is a Zumkeller number.
Yes, 108 is a Zumkeller number.
No, 200 is not a Zumkeller number.

复杂度分析: 上述程序使用了递归，使得程序的 time complexity 是指数级的，即 O(2f)，space complexity 也是指数级的，即 O(f * 2f)，其中 f 是输入数字 n 的总因子数。

上述程序的 space 和 time complexities 都非常高，不适用于因子数量很多的数字。对于这类数字，可能会出现 time limit exceeded 或 memory limit exceeded。因此，需要进行一些优化。

方法：使用动态规划

我们可以通过动态规划做得更好。观察使用动态规划解决问题的步骤。

步骤 1: 首先，检查数字 N 的因子之和是否为偶数。如果和不是偶数，我们可以得出该数字不是 Zumkeller 数。

步骤 2: 声明一个大小为 (sumofFactors / 2) + 1 * (size + 1) 的二维数组 dp[][]，其中 size 是因子的总数。

步骤 3: 运行一个 for 循环，从 0 <= j <= size，并将 dp[0][j] 设置为 true。因为零和总是可行的。

步骤 4: 使用 for 循环，从 1 <= j <= sumofFactors / 2，并将 dp[j][0] 设置为零，因为任何和为零的组合都是不可能的。

步骤 5: 运行一个嵌套 for 循环，从 1 <= k <= sumofFactors / 2 和 1 <= k <= size，并将 dp[j][k] 设置为 dp[j][k - 1]

步骤 6: 如果 j 大于或等于 arr[k-1]，并且 dp[j - arr[k - 1]][k - 1] 为 true，则将 dp[j][k] 赋值为 true。

现在，让我们来实现上述步骤。

文件名: ZumkellerDP.java

import java.util.ArrayList; // importing ArrayList
public class ZumkellerDP
{
boolean findFactors(int n)
{
// creating an ArrayList for storing factors of n
ArrayList<Integer> al = new ArrayList<Integer>();
int range = (int)Math.sqrt(n);
// finding the factors and 
// storing it in the list al
for(int i = 1; i <= range; i++)
{
if((n % i) == 0)
{
al.add(i);
if((n / i) != i)
{
al.add(n / i);
}
}
}
int size = al.size(); // size of the array list
int factors[] = new int[size];
for(int i = 0; i < size; i++)
{
    factors[i] = al.get(i);
}
return findPartition(factors, size);
}
// Returns true if factors[] can be partitioned in two
// subsets of equal sum, otherwise false
boolean findPartition(int factors[], int size)
{
int sumOfFactor = 0;
int j, k;
// Calculate the sum of all elements
for (j = 0; j < size; j++)
{
sumOfFactor = sumOfFactor + factors[j];
}
// sumOfFactor should be even so that the number n 
// is a Zumkeller number
if (sumOfFactor % 2 != 0)
{
return false;
}
// boolean array
boolean dp[][] = new boolean[sumOfFactor / 2 + 1][size + 1];
// initializing the top row as true
for (k = 0; k <= size; k++)
{
dp[0][k] = true;
}
// initializing the leftmost column, except dp[0][0], as 0
for (j = 1; j <= sumOfFactor / 2; j++)
{
dp[j][0] = false;
}
// Filling the partition table in a bottom-up manner
for (j = 1; j <= sumOfFactor / 2; j++) 
{
for (k = 1; k <= size; k++) 
{
	dp[j][k] = dp[j][k - 1];
	if (j >= factors[k - 1])
	{
		dp[j][k] = dp[j][k] || dp[j - factors[k - 1]][k - 1];
	}
}
}

return dp[sumOfFactor / 2][size];
}

	// main method
public static void main(String argvs[]) 
{
// instantiating the class ZumkellerDP
ZumkellerDP obj = new ZumkellerDP();

int n = 84; // first input

boolean ans = obj.findFactors(n);
if(ans)
{
    System.out.println("Yes, " + n + " is a Zumkeller number.");
}
else
{
    System.out.println("No, " + n + " is not a Zumkeller number.");
}
n = 108; // second input
ans = obj.findFactors(n);
if(ans)
{
    System.out.println("Yes, " + n + " is a Zumkeller number.");
}
else
{
    System.out.println("No, " + n + " is not a Zumkeller number.");
}
n = 200; // third input

ans = obj.findFactors(n);
if(ans)
{
    System.out.println("Yes, " + n + " is a Zumkeller number.");
}
else
{
    System.out.println("No, " + n + " is not a Zumkeller number.");
}
}
}

输出

Yes, 84 is a Zumkeller number.
Yes, 108 is a Zumkeller number.
No, 200 is not a Zumkeller number.

复杂度分析: 该程序使用了嵌套的 for 循环。外层循环运行 sumOfFactors / 2 次，内层循环从 1 运行到 size 次。因此，程序的 time complexity 为 O(size * sumOfFactors)。由于程序中使用了二维数组，space complexity 也为 O(size * sumOfFactors)。

我们仍然可以进行优化以减小 space complexity。以下程序说明了这一点。

文件名: ZumkellerDP.java

import java.util.ArrayList; // importing ArrayList
public class ZumkellerDP
{
boolean isZumkeller(int n)
{
// creating an ArrayList for storing factors of n
ArrayList<Integer> al = new ArrayList<Integer>();
int range = (int)Math.sqrt(n);
// finding the factors and 
// storing it in the list al
for(int i = 1; i <= range; i++)
{
if((n % i) == 0)
{
al.add(i);
if((n / i) != i)
{
al.add(n / i);
}
}
}
int size = al.size(); // size of the array list
int factors[] = new int[size];
for(int i = 0; i < size; i++)
{
    factors[i] = al.get(i);
}
return findPartition(factors, size);
}

boolean findPartition(int factors[], int size)
{
int sumOfFactor = 0;
int j, k;
// Calculate sum of all elements
for (j = 0; j < size; j++)
{
sumOfFactor = sumOfFactor + factors[j];
}
// sumOfFactor should be even so that the number n 
// is a Zumkeller number
if (sumOfFactor % 2 != 0)
{
return false;
}
// boolean array
boolean dp[] = new boolean[sumOfFactor / 2 + 1];
// initializing all the elements with a false value
for (j = 1; j <= sumOfFactor / 2; j++)
{
dp[j] = false;
}
// Filling up in the bottom-up manner
for (j = 0; j < size; j++) 
{

// The element to be included
// in the sum cannot be
// greater than the sum
for (k = sumOfFactor / 2; k >= factors[j]; k--) 
{
// Check if sum - arr[i] could be
// formed from a subset using elements
// before index i
if (dp[k - factors[j]] == true || k == factors[j])
	dp[k] = true;
}
}
return dp[sumOfFactor / 2];
}
// main method
public static void main(String argvs[]) 
{
// instantiating the class ZumkellerDP
ZumkellerDP obj = new ZumkellerDP();

int n = 84; // first input

boolean ans = obj.isZumkeller(n);
if(ans)
{
    System.out.println("Yes, " + n + " is a Zumkeller number.");
}
else
{
    System.out.println("No, " + n + " is not a Zumkeller number.");
}
n = 108; // second input
ans = obj.isZumkeller(n);
if(ans)
{
    System.out.println("Yes, " + n + " is a Zumkeller number.");
}
else
{
    System.out.println("No, " + n + " is not a Zumkeller number.");
}
n = 200; // third input

ans = obj.isZumkeller(n);
if(ans)
{
    System.out.println("Yes, " + n + " is a Zumkeller number.");
}
else
{
    System.out.println("No, " + n + " is not a Zumkeller number.");
}
}
}

输出

Yes, 84 is a Zumkeller number.
Yes, 108 is a Zumkeller number.
No, 200 is not a Zumkeller number.

复杂度分析: 该程序的 time complexity 与前一个程序相同。该程序的 space complexity 为 O(sumOfFactor)，其中 sumOfFactor 是输入数字 n 的因子总和。

在范围内查找 Zumkeller 数

以下程序说明了如何查找范围内的 Zumkeller 数。

文件名: ZumkellerNumbersRange.java

import java.util.ArrayList; // importing ArrayList
public class ZumkellerNumbersRange
{
boolean isZumkeller(int n)
{
// creating an ArrayList for storing factors of n
ArrayList<Integer> al = new ArrayList<Integer>();
int range = (int)Math.sqrt(n);
// finding the factors and 
// storing it in the list al
for(int i = 1; i <= range; i++)
{
if((n % i) == 0)
{
al.add(i);
if((n / i) != i)
{
al.add(n / i);
}
}
}
int size = al.size(); // size of the array list
int factors[] = new int[size];
for(int i = 0; i < size; i++)
{
    factors[i] = al.get(i);
}
return findPartition(factors, size);
}

boolean findPartition(int factors[], int size)
{
int sumOfFactor = 0;
int j, k;
// Calculate sum of all elements
for (j = 0; j < size; j++)
{
sumOfFactor = sumOfFactor + factors[j];
}
// sumOfFactor should be even so that the number n 
// is a Zumkeller number
if (sumOfFactor % 2 != 0)
{
return false;
}
// boolean array
boolean dp[] = new boolean[sumOfFactor / 2 + 1];
// initializing all the elements with a false value
for (j = 1; j <= sumOfFactor / 2; j++)
{
dp[j] = false;
}
// Filling up in the bottom-up manner
for (j = 0; j < size; j++) 
{

// The element to be included
// in the sum cannot be
// greater than the sum
for (k = sumOfFactor / 2; k >= factors[j]; k--) 
{
// Check if sum - arr[i] could be
// formed from a subset using elements
// before index i
if (dp[k - factors[j]] == true || k == factors[j])
	dp[k] = true;
}
}
return dp[sumOfFactor / 2];
}

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

// input 1
int n = 100;

System.out.println("Zumkeller Numbers from 1 to " + n + " are:");
for(int i = 1; i <= n; i++)
{
if(obj.isZumkeller(i))
System.out.print(i + " ");
}
}
}

输出

Zumkeller Numbers from 1 to 100 are:
6 12 20 24 28 30 40 42 48 54 56 60 66 70 78 80 84 88 90 96

下一个主题Java 中的布局管理器

Java 中的 Zumkeller 数

示例 1

示例 2

示例 3

朴素方法

方法：使用动态规划

在范围内查找 Zumkeller 数

联系信息

关注我们

教程

面试题

在线编译器

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 中的 Zumkeller 数

示例 1

示例 2

示例 3

朴素方法

方法：使用动态规划

在范围内查找 Zumkeller 数

相关帖子

Sylvester's Sequence in Java

CharsetEncoder averageBytesPerChar() method in Java with Examples

Session Tracking in Java

Java 中 LongConsumer 接口及示例

Is Java Interpreted or Compiled?

Java Color Codes

Edit Distance Problem in Java

Java 中将 JSON 转换为 Map

Java 中的强制类型转换运算符

Java 中排列二进制网格的最小交换次数

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器