Dada una array arr[] que consta de N números naturales , la tarea es encontrar la longitud de la subsecuencia más larga de la array que no contiene ningún número deficiente .
Ejemplos:
Entrada: arr[] = {13, 55, 240, 32, 24, 27, 56, 80, 100, 330, 89}
Salida: 6
Explicación:
Los elementos de array que no son números deficientes son {240, 24, 56, 80 , 100, 330}
Los divisores de 13 son {1, 13}. Por lo tanto, suma de divisores = 14, que es menor que 26 ( = 2 * 13)
Los divisores de 55 son {1, 5, 11, 55}. Por lo tanto, suma de divisores = 72, que es menor que 110 ( = 2 * 55).
Los divisores de 32 son {1, 2, 4, 8, 16, 32}. Por lo tanto, suma de divisores = 63, que es menor que 64 ( = 2 * 32).
Los divisores de 27 son {1, 3, 9, 27}. Por lo tanto, suma de divisores = 40, que es menor que 54 ( = 2 * 27).
Los divisores de 89 son {1, 89}. Por lo tanto, suma de divisores = 90, que es menor que 178 ( = 2 * 89).
Por lo tanto, el conteo requerido es 6.Entrada: arr[] = {1, 2, 3, 4, 5, 6}
Salida: 6
Explicación: Los elementos de array que son números no deficientes son {1, 2, 3, 4, 5, 6}
Enfoque: La idea para resolver el problema es simplemente contar la cantidad de números deficientes presentes en la array. El conteo de todos los elementos restantes de la array será la longitud requerida de la subsecuencia más larga. Siga los pasos a continuación para resolver el problema:
- Inicialice una variable, digamos res , para almacenar el recuento de elementos de array que no son deficientes.
- Atraviesa la array arr[]. Para cada elemento de la array, verifique si es un número deficiente o no .
- Calcule la suma de todos los divisores del elemento de array actual y devuelva verdadero, si la suma es menor que 2 * arr[i] . De lo contrario, devuelve falso .
- Si se encuentra que es falso para un elemento de array, aumente res .
- Después de completar los pasos anteriores, imprima el valor de res como la respuesta requerida.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to check if n is
// a deficient number or not
bool isNonDeficient(int n)
{
// Stores sum of divisors
int sum = 0;
// Iterate over the range [1, sqrt(N)]
for (int i = 1; i <= sqrt(n); i++) {
// If n is divisible by i
if (n % i == 0) {
// If divisors are equal,
// add only one of them
if (n / i == i) {
sum = sum + i;
}
// Otherwise add both
else {
sum = sum + i;
sum = sum + (n / i);
}
}
}
return sum >= 2 * n;
}
// Function to print the longest
// subsequence which does not
// contain any deficient numbers
int LongestNonDeficientSubsequence(int arr[], int n)
{
// Stores the count of array
// elements which are non-deficient
int res = 0;
// Traverse the array
for (int i = 0; i < n; i++) {
// If element is non-deficient
if (isNonDeficient(arr[i])) {
res += 1;
}
}
// Return the answer
return res;
}
// Driver Code
int main()
{
int arr[]
= { 13, 55, 240, 32, 24, 27,
56, 80, 100, 330, 89 };
int N = sizeof(arr) / sizeof(arr[0]);
cout << LongestNonDeficientSubsequence(arr, N);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
// Function to check if n is
// a deficient number or not
static boolean isNonDeficient(int n)
{
// Stores sum of divisors
int sum = 0;
// Iterate over the range [1, sqrt(N)]
for(int i = 1; i <= Math.sqrt(n); i++)
{
// If n is divisible by i
if (n % i == 0)
{
// If divisors are equal,
// add only one of them
if (n / i == i)
{
sum = sum + i;
}
// Otherwise add both
else
{
sum = sum + i;
sum = sum + (n / i);
}
}
}
return sum >= 2 * n;
}
// Function to print the longest
// subsequence which does not
// contain any deficient numbers
static int LongestNonDeficientSubsequence(int arr[],
int n)
{
// Stores the count of array
// elements which are non-deficient
int res = 0;
// Traverse the array
for(int i = 0; i < n; i++)
{
// If element is non-deficient
if (isNonDeficient(arr[i]))
{
res += 1;
}
}
// Return the answer
return res;
}
// Driver Code
public static void main(String[] args)
{
int arr[] = { 13, 55, 240, 32, 24, 27,
56, 80, 100, 330, 89 };
int N = arr.length;
System.out.print(
LongestNonDeficientSubsequence(arr, N));
}
}
// This code is contributed by splevel62
Python3
# Python3 program for the above approach import math # Function to check if n is # a deficient number or not def isNonDeficient(n): # Stores sum of divisors sum = 0 # Iterate over the range [1, sqrt(N)] for i in range(1, int(math.sqrt(n)) + 1): # If n is divisible by i if (n % i == 0): # If divisors are equal, # add only one of them if (n // i == i): sum = sum + i # Otherwise add both else: sum = sum + i sum = sum + (n // i) return sum >= 2 * n # Function to print the longest # subsequence which does not # contain any deficient numbers def LongestNonDeficientSubsequence(arr, n): # Stores the count of array # elements which are non-deficient res = 0 # Traverse the array for i in range(n): # If element is non-deficient if (isNonDeficient(arr[i])): res += 1 # Return the answer return res # Driver Code if __name__ == "__main__": arr = [ 13, 55, 240, 32, 24, 27, 56, 80, 100, 330, 89 ] N = len(arr) print(LongestNonDeficientSubsequence(arr, N)) # This code is contributed by chitranayal
C#
// C# program for above approach
using System;
public class GFG
{
// Function to check if n is
// a deficient number or not
static bool isNonDeficient(int n)
{
// Stores sum of divisors
int sum = 0;
// Iterate over the range [1, sqrt(N)]
for(int i = 1; i <= Math.Sqrt(n); i++)
{
// If n is divisible by i
if (n % i == 0)
{
// If divisors are equal,
// add only one of them
if (n / i == i)
{
sum = sum + i;
}
// Otherwise add both
else
{
sum = sum + i;
sum = sum + (n / i);
}
}
}
return sum >= 2 * n;
}
// Function to print the longest
// subsequence which does not
// contain any deficient numbers
static int LongestNonDeficientSubsequence(int[] arr,
int n)
{
// Stores the count of array
// elements which are non-deficient
int res = 0;
// Traverse the array
for(int i = 0; i < n; i++)
{
// If element is non-deficient
if (isNonDeficient(arr[i]))
{
res += 1;
}
}
// Return the answer
return res;
}
// Driver code
public static void Main(String[] args)
{
int[] arr = { 13, 55, 240, 32, 24, 27,
56, 80, 100, 330, 89 };
int N = arr.Length;
Console.WriteLine(
LongestNonDeficientSubsequence(arr, N));
}
}
// This code is contributed by splevel62.
Javascript
<script>
// Js program for the above approach
// Function to check if n is
// a deficient number or not
function isNonDeficient( n)
{
// Stores sum of divisors
let sum = 0;
// Iterate over the range [1, sqrt(N)]
for (let i = 1; i <= Math.floor(Math.sqrt(n)); i++) {
// If n is divisible by i
if (n % i == 0) {
// If divisors are equal,
// add only one of them
if (Math.floor(n / i) == i) {
sum = sum + i;
}
// Otherwise add both
else {
sum = sum + i;
sum = sum + Math.floor(n / i);
}
}
}
return sum >= 2 * n;
}
// Function to print the longest
// subsequence which does not
// contain any deficient numbers
function LongestNonDeficientSubsequence( arr, n)
{
// Stores the count of array
// elements which are non-deficient
let res = 0;
// Traverse the array
for (let i = 0; i < n; i++) {
// If element is non-deficient
if (isNonDeficient(arr[i])) {
res += 1;
}
}
// Return the answer
return res;
}
// Driver Code
let arr
= [ 13, 55, 240, 32, 24, 27,
56, 80, 100, 330, 89 ];
let N = arr.length;
document.write( LongestNonDeficientSubsequence(arr, N));
</script>
6
Complejidad temporal: O(N 3/2 )
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por crisscross y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA