Longitud del subarreglo más largo con producto igual a una potencia de 2

Posted on by Rudeus Greyrat

Dado un arreglo arr[] que consta de N enteros positivos, la tarea es encontrar la longitud del subarreglo más largo que tenga un producto de elementos de ese subarreglo igual a una potencia perfecta de 2 .

Ejemplos:

Entrada: arr[] = {2, 5, 4, 4, 6}
Salida: 2
Explicación:
El subarreglo de longitud máxima cuyo producto es potencia perfecta de 2 es {4, 4}.
Producto = 4 * 4 = 16, que es una potencia perfecta de 2.

Entrada : arr[] = {2, 5, 4, 6, 8, 8, 2}
Salida: 3
Explicación:
El subarreglo que tiene la longitud máxima cuyo producto es la potencia perfecta de 2 es {8, 8, 2}.
Producto = 8 * 8 * 2 = 128, que es una potencia perfecta de 2.

 

Enfoque ingenuo: el enfoque más simple es generar todos los subarreglos posibles del arreglo dado y verificar si el producto de los elementos de cualquier subarreglo es una potencia perfecta de 2 o no. Si se determina que es cierto, actualice la longitud máxima a la longitud de este subarreglo. Finalmente, imprima la longitud máxima del subarreglo obtenido después de verificar todos los subarreglo posibles. 

Complejidad de Tiempo: O(N 3 )
Espacio Auxiliar: O(1)

Enfoque eficiente: para optimizar el enfoque anterior, la idea se basa en el hecho de que para que cualquier número sea una potencia de 2, también se puede expresar como el producto de números que tienen una potencia perfecta de 2. Por lo tanto, la idea es usar el Algoritmo de Kadane para encontrar la longitud máxima del subarreglo que tiene todos los elementos con potencia perfecta de 2 . A continuación se muestran los pasos:

  • Inicialice maxLength y ans como 0 que almacenará la longitud máxima de los subarreglos y la longitud máxima resultante del subarreglo, respectivamente.
  • Recorre la array dada y haz lo siguiente:
  • Imprime el valor de ans como la longitud máxima después de los pasos anteriores.

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 whether a number
// is power of 2 or not
bool isPower(int x)
{
    return (x && (!(x & (x - 1))));
}
 
// Function to find maximum length
// subarray having product of element
// as a perfect power of 2
int maximumlength(int arr[], int N)
{
    // Stores current subarray length
    int max_length = 0;
 
    // Stores maximum subarray length
    int max_len_subarray = 0;
 
    // Traverse the given array
    for (int i = 0; i < N; i++) {
 
        // If arr[i] is power of 2
        if (isPower(arr[i]) == 1) {
 
            // Increment max_length
            max_length++;
 
            // Update max_len_subarray
            max_len_subarray
                = max(max_length,
                      max_len_subarray);
        }
 
        // Otherwise
        else {
            max_length = 0;
        }
    }
 
    // Print the maximum length
    cout << max_len_subarray;
}
 
// Driver Code
int main()
{
    // Given arr[]
    int arr[] = { 2, 5, 4, 6, 8, 8, 2 };
 
    int N = sizeof(arr) / sizeof(arr[0]);
 
    // Function Call
    maximumlength(arr, N);
 
    return 0;
}

Java

// Java program for the above approach
import java.util.*;
 
class GFG{
     
// Function to check whether a number
// is power of 2 or not
public static boolean isPower(int x)
{
    if (x != 0 && (x & (x - 1)) == 0)
        return true;
         
    return false;
}
 
// Function to find maximum length
// subarray having product of element
// as a perfect power of 2
public static void maximumlength(int arr[],
                                 int N)
{
     
    // Stores current subarray length
    int max_length = 0;
 
    // Stores maximum subarray length
    int max_len_subarray = 0;
 
    // Traverse the given array
    for(int i = 0; i < N; i++)
    {
         
        // If arr[i] is power of 2
        if (isPower(arr[i]))
        {
             
            // Increment max_length
            max_length++;
 
            // Update max_len_subarray
            max_len_subarray = Math.max(max_length,
                                        max_len_subarray);
        }
 
        // Otherwise
        else
        {
            max_length = 0;
        }
    }
 
    // Print the maximum length
    System.out.println(max_len_subarray);
}
 
// Driver Code
public static void main(String args[])
{
     
    // Given arr[]
    int arr[] = { 2, 5, 4, 6, 8, 8, 2 };
 
    int N = arr.length;
 
    // Function Call
    maximumlength(arr, N);
}
}
 
// This code is contributed by hemanthswarna1506

Python3

# Python3 program for the
# above approach
 
# Function to check whether
# a number is power of 2
# or not
def isPower(x):
   
    if (x != 0 and
       (x & (x - 1)) == 0):
        return True;
 
    return False;
 
# Function to find maximum
# length subarray having
# product of element
# as a perfect power of 2
def maximumlength(arr, N):
   
    # Stores current
    # subarray length
    max_length = 0;
 
    # Stores maximum
    # subarray length
    max_len_subarray = 0;
 
    # Traverse the given array
    for i in range(N):
 
        # If arr[i] is power of 2
        if (isPower(arr[i])):
 
            # Increment max_length
            max_length += 1;
 
            # Update max_len_subarray
            max_len_subarray = max(max_length,
                                   max_len_subarray);
 
        # Otherwise
        else:
            max_length = 0;
 
    # Print maximum length
    print(max_len_subarray);
 
# Driver Code
if __name__ == '__main__':
   
    # Given arr
    arr = [2, 5, 4,
           6, 8, 8, 2];
 
    N = len(arr);
 
    # Function Call
    maximumlength(arr, N);
 
# This code is contributed by gauravrajput1

C#

// C# program for the above approach
using System;
  
class GFG{
      
// Function to check whether a number
// is power of 2 or not
public static bool isPower(int x)
{
    if (x != 0 && (x & (x - 1)) == 0)
        return true;
          
    return false;
}
  
// Function to find maximum length
// subarray having product of element
// as a perfect power of 2
public static void maximumlength(int[] arr,
                                 int N)
{
     
    // Stores current subarray length
    int max_length = 0;
  
    // Stores maximum subarray length
    int max_len_subarray = 0;
  
    // Traverse the given array
    for(int i = 0; i < N; i++)
    {
         
        // If arr[i] is power of 2
        if (isPower(arr[i]))
        {
             
            // Increment max_length
            max_length++;
  
            // Update max_len_subarray
            max_len_subarray = Math.Max(max_length,
                                        max_len_subarray);
        }
  
        // Otherwise
        else
        {
            max_length = 0;
        }
    }
  
    // Print the maximum length
    Console.WriteLine(max_len_subarray);
}
  
// Driver Code
public static void Main()
{
     
    // Given arr[]
    int[] arr = { 2, 5, 4, 6, 8, 8, 2 };
  
    int N = arr.Length;
  
    // Function Call
    maximumlength(arr, N);
}
}
 
// This code is contributed by sanjoy_62

Javascript

<script>
 
// JavaScript program for the above approach
 
// Function to check whether a number
// is power of 2 or not
function isPower(x)
{
    return (x && (!(x & (x - 1))));
}
 
// Function to find maximum length
// subarray having product of element
// as a perfect power of 2
function maximumlength(arr, N)
{
    // Stores current subarray length
    var max_length = 0;
 
    // Stores maximum subarray length
    var max_len_subarray = 0;
 
    // Traverse the given array
    for (var i = 0; i < N; i++) {
 
        // If arr[i] is power of 2
        if (isPower(arr[i]) == 1) {
 
            // Increment max_length
            max_length++;
 
            // Update max_len_subarray
            max_len_subarray
                = Math.max(max_length,
                      max_len_subarray);
        }
 
        // Otherwise
        else {
            max_length = 0;
        }
    }
 
    // Print the maximum length
    document.write( max_len_subarray);
}
 
// Driver Code
 
// Given arr[]
var arr = [2, 5, 4, 6, 8, 8, 2];
var N = arr.length;
 
// Function Call
maximumlength(arr, N);
 
</script>
Producción

3

Complejidad temporal: O(N)
Espacio auxiliar: O(1)

Publicación traducida automáticamente

Artículo escrito por sallagondaavinashreddy7 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 *