Un Número Práctico es un número N si todos los números M < N pueden escribirse como la suma de distintos divisores propios de N .
1, 2, 4, 6, 8, 12, 16, 18, 20, 24, 28….
Comprobar si N es un número práctico
Dado un número N , la tarea es comprobar si N es un número práctico o no. Si N es un número práctico, escriba «Sí» , de lo contrario, escriba «No» .
Ejemplos:
Entrada: N = 6
Salida: Sí
Explicación:
Divisores propios de 6 = 1, 2, 3
2 = 2
3 = 1 + 2 o 3
4 = 1 + 3Entrada: N = 5
Salida: No
Enfoque: la idea es almacenar todos los factores del número en una array y luego, finalmente, determinar para todos los números i menores que N si hay un subconjunto del conjunto almacenado de factores con una suma igual a i.
El problema de la suma de subconjuntos para el mismo se explica en detalle en este artículo: Problema de la suma de subconjuntos | DP-25
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to check if a number is Practical
// or not.
#include <bits/stdc++.h>
using namespace std;
// Returns true if there is a subset of set[]
// with sun equal to given sum
bool isSubsetSum(vector<int>& set, int n, int sum)
{
// The value of subset[i][j] will be true if
// there is a subset of set[0..j-1] with sum
// equal to i
bool subset[n + 1][sum + 1];
// If sum is 0, then answer is true
for (int i = 0; i <= n; i++)
subset[i][0] = true;
// If sum is not 0 and set is empty,
// then answer is false
for (int i = 1; i <= sum; i++)
subset[0][i] = false;
// Fill the subset table in bottom up manner
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= sum; j++) {
if (j < set[i - 1])
subset[i][j] = subset[i - 1][j];
if (j >= set[i - 1])
subset[i][j] = subset[i - 1][j]
|| subset[i - 1][j - set[i - 1]];
}
}
return subset[n][sum];
}
// 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 num is Practical
bool isPractical(int N)
{
// vector to store all
// divisors of N
vector<int> div;
storeDivisors(N, div);
// to check all numbers from 1 to < N
for (int i = 1; i < N; i++) {
if (!isSubsetSum(div, div.size(), i))
return false;
}
return true;
}
// Driver code
int main()
{
int N = 18;
isPractical(N) ? cout << "Yes"
: cout << "No";
return 0;
}
Java
// Java program to check if a number is Practical
// or not.
import java.util.*;
class GFG{
// Returns true if there is a subset of set[]
// with sun equal to given sum
static boolean isSubsetSum(Vector<Integer> set,
int n, int sum)
{
// The value of subset[i][j] will be true if
// there is a subset of set[0..j-1] with sum
// equal to i
boolean [][]subset = new boolean[n + 1][sum + 1];
// If sum is 0, then answer is true
for (int i = 0; i <= n; i++)
subset[i][0] = true;
// If sum is not 0 and set is empty,
// then answer is false
for (int i = 1; i <= sum; i++)
subset[0][i] = false;
// Fill the subset table in bottom up manner
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= sum; j++)
{
if (j < set.get(i - 1))
subset[i][j] = subset[i - 1][j];
if (j >= set.get(i - 1))
subset[i][j] = subset[i - 1][j] ||
subset[i - 1][j -
set.get(i - 1)];
}
}
return subset[n][sum];
}
// 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 num is Practical
static boolean isPractical(int N)
{
// vector to store all
// divisors of N
Vector<Integer> div = new Vector<Integer>();
storeDivisors(N, div);
// to check all numbers from 1 to < N
for (int i = 1; i < N; i++)
{
if (!isSubsetSum(div, div.size(), i))
return false;
}
return true;
}
// Driver code
public static void main(String[] args)
{
int N = 18;
if(isPractical(N) == true)
System.out.print("Yes");
else
System.out.print("No");
}
}
// This code is contributed by PrinciRaj1992
Python3
# Python3 program to check if a number is
# Practical or not.
import math
# Returns true if there is a subset of set[]
# with sun equal to given sum
def isSubsetSum(Set, n, Sum):
# The value of subset[i][j] will be true if
# there is a subset of set[0..j-1] with sum
# equal to i
subset = [[False for i in range(Sum + 1)]
for j in range(n + 1)]
# If sum is 0, then answer is true
for i in range(n + 1):
subset[i][0] =True
# If sum is not 0 and set is empty,
# then answer is false
for i in range(1, Sum + 1):
subset[0][i] = False
# Fill the subset table in bottom up manner
for i in range(1, n + 1):
for j in range(1, Sum + 1):
if (j < Set[i - 1]):
subset[i][j] = subset[i - 1][j]
if (j >= Set[i - 1]):
subset[i][j] = (subset[i - 1][j] or
subset[i - 1][j - Set[i - 1]])
return subset[n][Sum]
# Function to store divisors of N
# in a vector
def storeDivisors(n, div):
# Find all divisors which divides 'num'
for i in range(1, int(math.sqrt(n)) + 1):
# 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 == int(n / i)):
div.append(i)
else:
div.append(i)
div.append(int(n / i))
# Returns true if num is Practical
def isPractical(N):
# Vector to store all
# divisors of N
div = []
storeDivisors(N, div)
# To check all numbers from 1 to < N
for i in range(1, N):
if (not isSubsetSum(div, len(div), i)):
return False
return True
# Driver code
N = 18
if (isPractical(N)):
print("Yes")
else:
print("No")
# This code is contributed by avanitrachhadiya2155
C#
// C# program to check if a number
// is Practical or not.
using System;
using System.Collections.Generic;
class GFG{
// Returns true if there is a subset of set[]
// with sun equal to given sum
static bool isSubsetSum(List<int> set,
int n, int sum)
{
// The value of subset[i,j] will be true if
// there is a subset of set[0..j-1] with sum
// equal to i
bool [,]subset = new bool[n + 1, sum + 1];
// If sum is 0, then answer is true
for (int i = 0; i <= n; i++)
subset[i, 0] = true;
// If sum is not 0 and set is empty,
// then answer is false
for (int i = 1; i <= sum; i++)
subset[0, i] = false;
// Fill the subset table in bottom up manner
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= sum; j++)
{
if (j < set[i - 1])
subset[i, j] = subset[i - 1, j];
if (j >= set[i - 1])
subset[i, j] = subset[i - 1, j] ||
subset[i - 1,
j - set[i - 1]];
}
}
return subset[n, sum];
}
// 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 num is Practical
static bool isPractical(int N)
{
// vector to store all
// divisors of N
List<int> div = new List<int>();
storeDivisors(N, div);
// to check all numbers from 1 to < N
for (int i = 1; i < N; i++)
{
if (!isSubsetSum(div, div.Count, i))
return false;
}
return true;
}
// Driver code
public static void Main(String[] args)
{
int N = 18;
if(isPractical(N) == true)
Console.Write("Yes");
else
Console.Write("No");
}
}
// This code is contributed by PrinciRaj1992
Javascript
<script>
// Javascript program to check if a number is Practical
// or not.
// Returns true if there is a subset of set[]
// with sun equal to given sum
function isSubsetSum(set, n, sum)
{
// The value of subset[i][j] will be true if
// there is a subset of set[0..j-1] with sum
// equal to i
var subset = Array.from(Array(n+1), ()=> Array(sum+1));
// If sum is 0, then answer is true
for (var i = 0; i <= n; i++)
subset[i][0] = true;
// If sum is not 0 and set is empty,
// then answer is false
for (var i = 1; i <= sum; i++)
subset[0][i] = false;
// Fill the subset table in bottom up manner
for (var i = 1; i <= n; i++) {
for (var j = 1; j <= sum; j++) {
if (j < set[i - 1])
subset[i][j] = subset[i - 1][j];
if (j >= set[i - 1])
subset[i][j] = subset[i - 1][j]
|| subset[i - 1][j - set[i - 1]];
}
}
return subset[n][sum];
}
// 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 == (n / i))
div.push(i);
else {
div.push(i);
div.push(n / i);
}
}
}
}
// Returns true if num is Practical
function isPractical(N)
{
// vector to store all
// divisors of N
div = [];
storeDivisors(N, div);
// to check all numbers from 1 to < N
for (var i = 1; i < N; i++) {
if (!isSubsetSum(div, div.length, i))
return false;
}
return true;
}
// Driver code
var N = 18;
isPractical(N) ? document.write( "Yes")
: document.write( "No");
</script>
Producción:
Yes
Complejidad de tiempo: O(n)