Dado un número entero N , la tarea es comprobar si N es un número de Zumkelle
Número de Zumkelle es un número cuyos divisores se pueden dividir en dos conjuntos con la misma suma.
Por ejemplo, 12 es un número de Zumkeller porque sus divisores 1, 2, 3, 4, 6, 12 se pueden dividir en los dos conjuntos {12, 2} y {1, 3, 4, 6} con la misma suma 14 .
Ejemplos:
Entrada: N = 12
Salida: Sí
Explicación:
Los divisores de 12 1, 2, 3, 4, 6, 12 se pueden dividir
en los dos conjuntos {12, 2} y {1, 3, 4, 6} con el mismo suma 14.
Entrada: N = 26
Salida: No
Enfoque: la idea es almacenar todos los factores del número en una array y luego, finalmente, dividir la array en dos subconjuntos de modo que la suma de los elementos en ambos subconjuntos sea la misma.
El problema de partición para el mismo se explica en detalle en este artículo:
Problema de partición | DP-18
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ Program to check if n
// is an Zumkelle number
#include <bits/stdc++.h>
using namespace std;
// Function to store divisors of N
// in a vector
void storeDivisors(int n, vector<int>& div)
{
// Find all divisors which divides 'num'
for (int i = 1; i <= sqrt(n); i++) {
// if 'i' is divisor of 'n'
if (n % i == 0) {
// if both divisors are same
// then store it once else store
// both divisors
if (i == (n / i))
div.push_back(i);
else {
div.push_back(i);
div.push_back(n / i);
}
}
}
}
// Returns true if vector can be partitioned
// in two subsets of equal sum, otherwise false
bool isPartitionPossible(vector<int>& arr)
{
int n = arr.size();
int sum = 0;
int i, j;
// Calculate sum of all elements
for (i = 0; i < n; i++)
sum += arr[i];
if (sum % 2 != 0)
return false;
bool part[sum / 2 + 1][n + 1];
// initialize top row as true
for (i = 0; i <= n; i++)
part[0][i] = true;
// initialize leftmost column,
// except part[0][0], as 0
for (i = 1; i <= sum / 2; i++)
part[i][0] = false;
// Fill the partition table
// in bottom up manner
for (i = 1; i <= sum / 2; i++) {
for (j = 1; j <= n; j++) {
part[i][j] = part[i][j - 1];
if (i >= arr[j - 1])
part[i][j] = part[i][j] || part[i - arr[j - 1]][j - 1];
}
}
return part[sum / 2][n];
}
// Function to check if n
// is an Zumkelle number
bool isZumkelleNum(int N)
{
// vector to store all
// proper divisors of N
vector<int> div;
storeDivisors(N, div);
return isPartitionPossible(div);
}
// Driver code
int main()
{
int n = 12;
if (isZumkelleNum(n))
cout << "Yes";
else
cout << "No";
return 0;
}
Java
// Java Program to check if n
// is an Zumkelle number
import java.util.*;
class GFG{
// Function to store divisors of N
// in a vector
static void storeDivisors(int n,
Vector<Integer> div)
{
// Find all divisors which divides 'num'
for (int i = 1; i <= Math.sqrt(n); i++)
{
// if 'i' is divisor of 'n'
if (n % i == 0)
{
// if both divisors are same
// then store it once else store
// both divisors
if (i == (n / i))
div.add(i);
else
{
div.add(i);
div.add(n / i);
}
}
}
}
// Returns true if vector can be partitioned
// in two subsets of equal sum, otherwise false
static boolean isPartitionPossible
(Vector<Integer> arr)
{
int n = arr.size();
int sum = 0;
int i, j;
// Calculate sum of all elements
for (i = 0; i < n; i++)
sum += arr.get(i);
if (sum % 2 != 0)
return false;
boolean [][]part = new boolean[sum / 2 + 1][n + 1];
// initialize top row as true
for (i = 0; i <= n; i++)
part[0][i] = true;
// initialize leftmost column,
// except part[0][0], as 0
for (i = 1; i <= sum / 2; i++)
part[i][0] = false;
// Fill the partition table
// in bottom up manner
for (i = 1; i <= sum / 2; i++) {
for (j = 1; j <= n; j++) {
part[i][j] = part[i][j - 1];
if (i >= arr.get(j - 1))
part[i][j] = part[i][j] ||
part[i - arr.get(j - 1)][j - 1];
}
}
return part[sum / 2][n];
}
// Function to check if n
// is an Zumkelle number
static boolean isZumkelleNum(int N)
{
// vector to store all
// proper divisors of N
Vector<Integer> div = new Vector<Integer>();
storeDivisors(N, div);
return isPartitionPossible(div);
}
// Driver code
public static void main(String[] args)
{
int n = 12;
if (isZumkelleNum(n))
System.out.print("Yes");
else
System.out.print("No");
}
}
// This code is contributed by Amit Katiyar
C#
// C# Program to check if n
// is an Zumkelle number
using System;
using System.Collections.Generic;
class GFG{
// Function to store divisors of N
// in a vector
static void storeDivisors(int n,
List<int> div)
{
// Find all divisors which divides 'num'
for (int i = 1; i <= Math.Sqrt(n); i++)
{
// if 'i' is divisor of 'n'
if (n % i == 0)
{
// if both divisors are same
// then store it once else store
// both divisors
if (i == (n / i))
div.Add(i);
else
{
div.Add(i);
div.Add(n / i);
}
}
}
}
// Returns true if vector can be partitioned
// in two subsets of equal sum, otherwise false
static bool isPartitionPossible
(List<int> arr)
{
int n = arr.Count;
int sum = 0;
int i, j;
// Calculate sum of all elements
for (i = 0; i < n; i++)
sum += arr[i];
if (sum % 2 != 0)
return false;
bool [,]part = new bool[sum / 2 + 1, n + 1];
// initialize top row as true
for (i = 0; i <= n; i++)
part[0, i] = true;
// initialize leftmost column,
// except part[0,0], as 0
for (i = 1; i <= sum / 2; i++)
part[i, 0] = false;
// Fill the partition table
// in bottom up manner
for (i = 1; i <= sum / 2; i++)
{
for (j = 1; j <= n; j++)
{
part[i, j] = part[i, j - 1];
if (i >= arr[j - 1])
part[i, j] = part[i, j] ||
part[i - arr[j - 1],
j - 1];
}
}
return part[sum / 2, n];
}
// Function to check if n
// is an Zumkelle number
static bool isZumkelleNum(int N)
{
// vector to store all
// proper divisors of N
List<int> div = new List<int>();
storeDivisors(N, div);
return isPartitionPossible(div);
}
// Driver code
public static void Main(String[] args)
{
int n = 12;
if (isZumkelleNum(n))
Console.Write("Yes");
else
Console.Write("No");
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// Javascript implementation
// Function to store divisors of N
// in a vector
function storeDivisors(n, div)
{
// Find all divisors which divides 'num'
for (var i = 1; i <= Math.sqrt(n); i++) {
// if 'i' is divisor of 'n'
if (n % i == 0) {
// if both divisors are same
// then store it once else store
// both divisors
if (i == Math.floor(n / i))
div.push(i);
else {
div.push(i);
div.push(Math.floor(n / i));
}
}
}
}
// Returns true if vector can be partitioned
// in two subsets of equal sum, otherwise false
function isPartitionPossible( arr)
{
var n = arr.length;
var sum = 0;
var i, j;
// Calculate sum of all elements
for (i = 0; i < n; i++)
sum += arr[i];
if (sum % 2 != 0)
return false;
var part = [];
for (i = 0; i <= Math.floor(sum / 2); i++) {
var ll = [];
for (j = 0; j <= n; j++) {
ll.push(false);
}
part.push(ll);
}
// initialize top row as true
for (i = 0; i <= n; i++)
part[0][i] = true;
// initialize leftmost column,
// except part[0][0], as 0
for (i = 1; i <= Math.floor(sum / 2); i++)
part[i][0] = false;
// Fill the partition table
// in bottom up manner
for (i = 1; i <= Math.floor(sum / 2); i++) {
for (j = 1; j <= n; j++) {
part[i][j] = part[i][j - 1];
if (i >= arr[j - 1])
part[i][j] = part[i][j] || part[i - arr[j - 1]][j - 1];
}
}
return 1;//part[Math.floor(sum / 2)][n];
}
// Function to check if n
// is an Zumkelle number
function isZumkelleNum(N)
{
// vector to store all
// proper divisors of N
var div = [];
storeDivisors(N, div);
return isPartitionPossible(div);
}
// Driver Code
// Given Number N
var N = 12;
// Function Call
if (isZumkelleNum(N))
document.write("Yes");
else
document.write("No");
// This code is contributed by shubhamsingh10
</script>
Salida:
Sí
Sí
Complejidad de tiempo: O(N * suma)
Referencia: OEIS