Longitud del subarreglo más grande cuyos elementos son Número perfecto

Dado un arreglo arr[] de elementos enteros, la tarea es encontrar la longitud del subarreglo más grande de arr[] tal que todos los elementos del subarreglo sean números perfectos .
 

Un número perfecto es un entero positivo que es igual a la suma de sus divisores propios . 
 

Ejemplos: 
 

Entrada: arr[] = {1, 7, 36, 4, 6, 28, 4} 
Salida: 2 
Explicación: 
la subarray de longitud máxima con todos los elementos como número perfecto es {6, 28}.
Entrada: arr[] = {25, 100, 2, 3, 9, 1} 
Salida: 0 
Explicación: 
Ninguno de los números es un número perfecto 
 

Acercarse: 
 

• Recorra la array de izquierda a derecha e inicialice una variable max_length y current_length con 0.
• Si el elemento actual es un número perfecto, incremente la variable longitud_actual y continúe con el proceso. De lo contrario, establezca current_length en 0.
• En cada paso, asigne max_length como max_length = max(current_length, max_length) .
• Imprime el valor de max_length al final, ya que almacenará el resultado requerido.

A continuación se muestra la implementación del enfoque anterior:
 

// C++ program to find the length of the
// largest sub-array of an array every
// element of whose is a perfect number
 
#include <bits/stdc++.h>
using namespace std;
 
// Function that returns true if n is perfect
bool isPerfect(long long int n)
{
    // Variable 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 return the length of the
// largest sub-array of an array every
// element of whose is a perfect number
int contiguousPerfectNumber(int arr[], int n)
{
 
    int current_length = 0;
    int max_length = 0;
 
    for (int i = 0; i < n; i++) {
 
        // Check if arr[i] is a perfect number
        if (isPerfect(arr[i]))
            current_length++;
        else
            current_length = 0;
 
        max_length = max(max_length,
                         current_length);
    }
 
    return max_length;
}
 
// Driver code
int main()
{
    int arr[] = { 1, 7, 36, 4, 6, 28, 4 };
    int n = sizeof(arr) / sizeof(arr[0]);
 
    cout << contiguousPerfectNumber(arr, n);
 
    return 0;
}

// Java program to find the length of the
// largest sub-array of an array every
// element of whose is a perfect number
 
import java.util.*;    
 
class GFG
{
    // Function that returns true if n is perfect
    static boolean isPerfect(int n)
    {
        // Variable to store sum of divisors
        int sum = 1;
        int i;
         
        // Find all divisors and add them
        for ( 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 return the length of the
    // largest sub-array of an array every
    // element of whose is a perfect number
    static int contiguousPerfectNumber(int arr[], int n)
    {
     
        int current_length = 0;
        int max_length = 0;
        int i;
        for (i = 0; i < n; i++) {
     
            // Check if arr[i] is a perfect number
            if (isPerfect(arr[i]))
                current_length++;
            else
                current_length = 0;
     
            max_length = Math.max(max_length,
                            current_length);
        }
     
        return max_length;
    }
     
    // Driver code
    public static void main(String []args)
    {
        int arr[] = { 1, 7, 36, 4, 6, 28, 4 };
        int n = arr.length;
     
        System.out.print(contiguousPerfectNumber(arr, n));
     
    }
}
 
//This code is contributed by chitranayal

# Python 3 program to find the length of
# the largest sub-array of an array every
# element of whose is a perfect number
 
 
# Function that returns true if n is perfect
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 the 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 return the length of the
# largest sub-array of an array every
# element of whose is a perfect number
def contiguousPerfectNumber(arr, n):
    current_length = 0
    max_length = 0
 
    for i in range(0, n, 1):
         
        # check if arr[i] is a perfect number
        if (isPerfect(arr[i])):
            current_length += 1
        else:
            current_length = 0
 
        max_length = max(max_length,
                        current_length)
     
    return max_length
 
# Driver code
if __name__ == '__main__':
    arr = [1, 7, 36, 4, 6, 28, 4]
    n = len(arr)
 
    print(contiguousPerfectNumber(arr, n))

// C# program to find the length of the
// largest sub-array of an array every
// element of whose is a perfect number
using System;
 
class GFG{
     
// Function that returns true if n is perfect
static bool isPerfect(int n)
{
     
    // Variable to store sum of divisors
    int sum = 1;
    int i;
         
    // Find all divisors and add them
    for(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 return the length of the
// largest sub-array of an array every
// element of whose is a perfect number
static int contiguousPerfectNumber(int []arr,
                                   int n)
{
    int current_length = 0;
    int max_length = 0;
    int i;
    for(i = 0; i < n; i++)
    {
        
       // Check if arr[i] is a perfect number
       if (isPerfect(arr[i]))
       {
           current_length++;
       }
       else
       {
           current_length = 0;
       }
       max_length = Math.Max(max_length,
                             current_length);
    }
    return max_length;
}
     
// Driver code
public static void Main(String []args)
{
    int []arr = { 1, 7, 36, 4, 6, 28, 4 };
    int n = arr.Length;
     
    Console.Write(contiguousPerfectNumber(arr, n));
}
}
 
// This code is contributed by sapnasingh4991

<script>
 
// Javascript program to find the length of the
// largest sub-array of an array every
// element of whose is a perfect number
  
    // Function that returns true if n is perfect
    function isPerfect(n)
    {
        // Variable to store sum of divisors
        let sum = 1;
        let i;
           
        // Find all divisors and add them
        for ( 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 return the length of the
    // largest sub-array of an array every
    // element of whose is a perfect number
    function contiguousPerfectNumber(arr, n)
    {
       
        let current_length = 0;
        let max_length = 0;
        let i;
        for (i = 0; i < n; i++) {
       
            // Check if arr[i] is a perfect number
            if (isPerfect(arr[i]))
                current_length++;
            else
                current_length = 0;
       
            max_length = Math.max(max_length,
                            current_length);
        }
       
        return max_length;
    }
 
// Driver Code
     
    let arr = [ 1, 7, 36, 4, 6, 28, 4 ];
    let n = arr.length;
       
    document.write(contiguousPerfectNumber(arr, n));
             
</script>

2

Complejidad de tiempo: O(N×√N)
Complejidad de espacio auxiliar: O(1)