Longitud de la subsecuencia más larga que consta de números no deficientes

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:
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:
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:

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>
Producción: 

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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *