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