Dada una array arr[] que contiene enteros no negativos de longitud N , la tarea es imprimir la longitud de la subsecuencia más larga del número perfecto en la array.
Un número es un número perfecto si es igual a la suma de sus divisores propios, es decir, la suma de sus divisores positivos excluyendo el propio número.
Ejemplos:
Entrada: arr[] = { 3, 6, 11, 2, 28, 21, 8128 }
Salida: 3
Explicación:
La subsecuencia de números perfectos más larga es {6, 28, 8128} y, por lo tanto, la respuesta es 3.Entrada: arr[] = { 6, 4, 10, 13, 9, 25 }
Salida: 1
Explicación:
La subsecuencia de números perfectos más larga es {6} y, por lo tanto, la respuesta es 1.
Enfoque:
Para resolver el problema mencionado anteriormente, siga los pasos que se detallan a continuación:
- Recorra la array dada y para cada elemento de la array, verifique si es un número perfecto o no .
- Si el elemento es un número perfecto, estará en la subsecuencia del número perfecto más largo. Por lo tanto, incremente la longitud requerida de la subsecuencia del número perfecto más largo en 1
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to find the length of
// Longest Perfect number Subsequence in an Array
#include <bits/stdc++.h>
using namespace std;
// Function to check if
// the number is a Perfect number
bool isPerfect(long long int n)
{
// To store sum of divisors
long long int sum = 1;
// Find all divisors and add them
for (long long int i = 2; i * i <= n; i++) {
if (n % i == 0) {
if (i * i != n)
sum = sum + i + n / i;
else
sum = sum + i;
}
}
// Check if sum of divisors is equal to
// n, then n is a perfect number
if (sum == n && n != 1)
return true;
return false;
}
// Function to find the longest subsequence
// which contain all Perfect numbers
int longestPerfectSubsequence(int arr[], int n)
{
int answer = 0;
// Find the length of longest
// Perfect number subsequence
for (int i = 0; i < n; i++) {
if (isPerfect(arr[i]))
answer++;
}
return answer;
}
// Driver code
int main()
{
int arr[] = { 3, 6, 11, 2, 28, 21, 8128 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << longestPerfectSubsequence(arr, n) << endl;
return 0;
}
Java
// Java program to find the length of
// longest perfect number subsequence
// in an array
class GFG {
// Function to check if the
// number is a perfect number
static boolean isPerfect(long n)
{
// To store sum of divisors
long sum = 1;
// Find all divisors and add them
for(long i = 2; i * i <= n; i++)
{
if (n % i == 0)
{
if (i * i != n)
sum = sum + i + n / i;
else
sum = sum + i;
}
}
// Check if sum of divisors is equal
// to n, then n is a perfect number
if (sum == n && n != 1)
{
return true;
}
return false;
}
// Function to find the longest subsequence
// which contain all Perfect numbers
static int longestPerfectSubsequence(int arr[],
int n)
{
int answer = 0;
// Find the length of longest
// perfect number subsequence
for(int i = 0; i < n; i++)
{
if (isPerfect(arr[i]) == true)
answer++;
}
return answer;
}
// Driver code
public static void main (String[] args)
{
int arr[] = { 3, 6, 11, 2, 28, 21, 8128 };
int n = arr.length;
System.out.println(longestPerfectSubsequence(arr, n));
}
}
// This code is contributed by AnkitRai01
Python3
# Python3 program to find the length of # Longest Perfect number Subsequence in an Array # Function to check if # the number is Perfect number def isPerfect( n ): # To store sum of divisors sum = 1 # Find all divisors and add them i = 2 while i * i <= n: if n % i == 0: sum = sum + i + n / i i += 1 # Check if sum of divisors is equal to # n, then n is a perfect number return (True if sum == n and n != 1 else False) # Function to find the longest subsequence # which contain all Perfect numbers def longestPerfectSubsequence( arr, n): answer = 0 # Find the length of longest # Perfect number subsequence for i in range (n): if (isPerfect(arr[i])): answer += 1 return answer # Driver code if __name__ == "__main__": arr = [ 3, 6, 11, 2, 28, 21, 8128 ] n = len(arr) print (longestPerfectSubsequence(arr, n))
C#
// C# program to find the length of
// longest perfect number subsequence
// in an array
using System;
class GFG {
// Function to check if the
// number is a perfect number
static bool isPerfect(long n)
{
// To store sum of divisors
long sum = 1;
// Find all divisors and add them
for(long i = 2; i * i <= n; i++)
{
if (n % i == 0)
{
if (i * i != n)
sum = sum + i + n / i;
else
sum = sum + i;
}
}
// Check if sum of divisors is equal
// to n, then n is a perfect number
if (sum == n && n != 1)
{
return true;
}
return false;
}
// Function to find the longest subsequence
// which contain all perfect numbers
static int longestPerfectSubsequence(int []arr,
int n)
{
int answer = 0;
// Find the length of longest
// perfect number subsequence
for(int i = 0; i < n; i++)
{
if (isPerfect(arr[i]) == true)
answer++;
}
return answer;
}
// Driver code
public static void Main (string[] args)
{
int []arr = { 3, 6, 11, 2, 28, 21, 8128 };
int n = arr.Length;
Console.WriteLine(longestPerfectSubsequence(arr, n));
}
}
// This code is contributed by AnkitRai01
Javascript
<script>
// Javascript program to find the length of
// Longest Perfect number Subsequence in an Array
// Function to check if
// the number is a Perfect number
function isPerfect(n)
{
// To store sum of divisors
var sum = 1;
// Find all divisors and add them
for (var i = 2; i * i <= n; i++) {
if (n % i == 0) {
if (i * i != n)
sum = sum + i + n / i;
else
sum = sum + i;
}
}
// Check if sum of divisors is equal to
// n, then n is a perfect number
if (sum == n && n != 1)
return true;
return false;
}
// Function to find the longest subsequence
// which contain all Perfect numbers
function longestPerfectSubsequence(arr, n)
{
var answer = 0;
// Find the length of longest
// Perfect number subsequence
for (var i = 0; i < n; i++) {
if (isPerfect(arr[i]))
answer++;
}
return answer;
}
// Driver code
var arr = [3, 6, 11, 2, 28, 21, 8128];
var n = arr.length;
document.write( longestPerfectSubsequence(arr, n));
</script>
Producción:
3
Complejidad de tiempo: O(N×√N)
Complejidad de espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por saurabhshadow y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA