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

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úmero poderoso . 
 

Un número n se dice Número Poderoso si, para todo factor primo p de él, p ² también lo divide. 
 

Ejemplos: 
 

Entrada: arr[] = {1, 7, 36, 4, 6, 28, 4} 
Salida: 2 
Subarreglo de longitud máxima con todos los elementos como número poderoso es {36, 4}
Entrada: arr[] = {25, 100, 2, 3, 9, 1} 
Salida: 2 
Sub-arreglo de longitud máxima con todos los elementos como Número poderoso es {25, 100} o {9, 1} 
 

Enfoque : 
 

• Atraviesa la array de izquierda a derecha. Inicialice una variable max_length y current_length con 0.
• Si el elemento actual es un número poderoso , incremente la variable longitud_actual y continúe . De lo contrario, establezca current_length = 0 .
• En cada paso, asigne max_length como max_length = max(current_length, max_length) .
• Imprime el valor de max_length al final.

// C++ program to find the length of the
// largest sub-array of an array every
// element of whose is a powerful number
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to check if the
// number is powerful
bool isPowerful(int n)
{
    // First divide the number repeatedly by 2
    while (n % 2 == 0) {
        int power = 0;
        while (n % 2 == 0) {
            n /= 2;
            power++;
        }
 
        // If only 2^1 divides n
        // (not higher powers),
        // then return false
        if (power == 1)
            return false;
    }
 
    // If n is not a power of 2
    // then this loop will execute
    // repeat above process
    for (int factor = 3;
         factor <= sqrt(n);
         factor += 2) {
 
        // Find highest power of "factor"
        // that divides n
        int power = 0;
        while (n % factor == 0) {
            n = n / factor;
            power++;
        }
 
        // If only factor^1 divides n
        // (not higher powers),
        // then return false
        if (power == 1)
            return false;
    }
 
    // n must be 1 now
    // if it is not a prime number.
    // Since prime numbers are not powerful,
    // we return false if n is not 1.
    return (n == 1);
}
 
// Function to return the length of the
// largest sub-array of an array every
// element of whose is a powerful number
int contiguousPowerfulNumber(int arr[], int n)
{
 
    int current_length = 0;
    int max_length = 0;
 
    for (int i = 0; i < n; i++) {
 
        // If arr[i] is
        // a Powerful number
        if (isPowerful(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 << contiguousPowerfulNumber(arr, n);
 
    return 0;
}

// Java program to find the length of the
// largest sub-array of an array every
// element of whose is a powerful number
import java.util.*;
 
class solution{
 
// Function to check if the
// number is powerful
static boolean isPowerful(int n)
{
    // First divide the number repeatedly by 2
    while (n % 2 == 0) {
        int power = 0;
        while (n % 2 == 0) {
            n /= 2;
            power++;
        }
 
        // If only 2^1 divides n
        // (not higher powers),
        // then return false
        if (power == 1)
            return false;
    }
 
    // If n is not a power of 2
    // then this loop will execute
    // repeat above process
    for (int factor = 3;
        factor <= Math.sqrt(n);
         factor += 2) {
 
        // Find highest power of "factor"
        // that divides n
        int power = 0;
        while (n % factor == 0) {
            n = n / factor;
            power++;
        }
 
        // If only factor^1 divides n
        // (not higher powers),
        // then return false
        if (power == 1)
            return false;
    }
 
    // n must be 1 now
    // if it is not a prime number.
    // Since prime numbers are not powerful,
    // we return false if n is not 1.
    return (n == 1);
}
 
// Function to return the length of the
// largest sub-array of an array every
// element of whose is a powerful number
static int contiguousPowerfulNumber(int[] arr, int n)
{
 
    int current_length = 0;
    int max_length = 0;
 
    for (int i = 0; i < n; i++) {
 
        // If arr[i] is
        // a Powerful number
        if (isPowerful(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.println(contiguousPowerfulNumber(arr, n));
 
}
}
 
// This code is contributed by Bhupendra_Singh

# Python 3 program to find the length of
# the largest sub-array of an array every
# element of whose is a powerful number
 
import math
 
# function to check if
# the number is powerful
def isPowerful(n):
   
    # First divide the number repeatedly by 2
    while (n % 2 == 0):
   
        power = 0
        while (n % 2 == 0):
           
            n = n//2
            power = power + 1
           
            
        # If only 2 ^ 1 divides
        # n (not higher powers),
        # then return false
        if (power == 1):
            return False
       
    
    # If n is not a power of 2
    # then this loop will execute
    # repeat above process
    for factor in range(3, int(math.sqrt(n))+1, 2):
       
        # Find highest power of
        # "factor" that divides n
        power = 0
        while (n % factor == 0):
           
            n = n//factor
            power = power + 1
           
    
        # If only factor ^ 1 divides
        # n (not higher powers),
        # then return false
        if (power == 1):
            return false
       
    
     # n must be 1 now if it
     # is not a prime number.
     # Since prime numbers are
     # not powerful, we return
     # false if n is not 1.
    return (n == 1)
 
 
# Function to return the length of the
# largest sub-array of an array every
# element of whose is a powerful number
def contiguousPowerfulNumber(arr, n):
    current_length = 0
    max_length = 0
 
    for i in range(0, n, 1):
         
        # If arr[i] is a
        # Powerful number
        if (isPowerful(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(contiguousPowerfulNumber(arr, n))

// C# program to find the length of the
// largest sub-array of an array every
// element of whose is a powerful number
using System;
 
class solution{
 
// Function to check if the
// number is powerful
static bool isPowerful(int n)
{
 
    // First divide the number repeatedly by 2
    while (n % 2 == 0) {
        int power = 0;
        while (n % 2 == 0) {
            n /= 2;
            power++;
        }
 
        // If only 2^1 divides n
        // (not higher powers),
        // then return false
        if (power == 1)
            return false;
    }
 
    // If n is not a power of 2
    // then this loop will execute
    // repeat above process
    for (int factor = 3;
             factor <= Math.Sqrt(n);
             factor += 2) {
 
        // Find highest power of "factor"
        // that divides n
        int power = 0;
        while (n % factor == 0) {
            n = n / factor;
            power++;
        }
 
        // If only factor^1 divides n
        // (not higher powers),
        // then return false
        if (power == 1)
            return false;
    }
 
    // n must be 1 now
    // if it is not a prime number.
    // Since prime numbers are not powerful,
    // we return false if n is not 1.
    return (n == 1);
}
 
// Function to return the length of the
// largest sub-array of an array every
// element of whose is a powerful number
static int contiguousPowerfulNumber(int[] arr, int n)
{
    int current_length = 0;
    int max_length = 0;
    for (int i = 0; i < n; i++) {
 
        // If arr[i] is
        // a Powerful number
        if (isPowerful(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.WriteLine(contiguousPowerfulNumber(arr, n));
}
}
 
// This code is contributed by gauravrajput1

<script>
 
// Javascript program to find the length of the
// largest sub-array of an array every
// element of whose is a powerful number
 
// Function to check if the
// number is powerful
function isPowerful(n)
{
    // First divide the number repeatedly by 2
    while (n % 2 == 0) {
        let power = 0;
        while (n % 2 == 0) {
            n /= 2;
            power++;
        }
   
        // If only 2^1 divides n
        // (not higher powers),
        // then return false
        if (power == 1)
            return false;
    }
   
    // If n is not a power of 2
    // then this loop will execute
    // repeat above process
    for (let factor = 3;
        factor <= Math.sqrt(n);
         factor += 2) {
   
        // Find highest power of "factor"
        // that divides n
        let power = 0;
        while (n % factor == 0) {
            n = n / factor;
            power++;
        }
   
        // If only factor^1 divides n
        // (not higher powers),
        // then return false
        if (power == 1)
            return false;
    }
   
    // n must be 1 now
    // if it is not a prime number.
    // Since prime numbers are not powerful,
    // we return false if n is not 1.
    return (n == 1);
}
   
// Function to return the length of the
// largest sub-array of an array every
// element of whose is a powerful number
function contiguousPowerfulNumber(arr, n)
{
   
    let current_length = 0;
    let max_length = 0;
   
    for (let i = 0; i < n; i++) {
   
        // If arr[i] is
        // a Powerful number
        if (isPowerful(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(contiguousPowerfulNumber(arr, n));
                   
</script>

2

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