Subarreglo más largo en el que todos los elementos son un factor de K

Posted on by Rudeus Greyrat

Dado un arreglo A[] de tamaño N y un entero positivo K , la tarea es encontrar la longitud del subarreglo más largo tal que todos los elementos del subarreglo sean un factor de K .

Ejemplos:

Entrada: A[] = {2, 8, 3, 10, 6, 7, 4, 9}, K = 60
Salida: 3
Explicación: El subarreglo más largo en el que todos los elementos son un factor de K (= 60) es { 3, 10, 6}. Por lo tanto, la salida requerida es 3.

Entrada: A[] = {7, 20, 8, 10, 5}, K = 20
Salida: 2
Explicación: El subarreglo más largo en el que todos los elementos son un factor de K (= 20) es {10, 5}. Por lo tanto, la salida requerida es 2.

 

Enfoque ingenuo: este enfoque más simple para resolver este problema es atravesar la array y generar todos los subarreglos posibles de la array dada. Para cada subarreglo, verifique si todos sus elementos son un factor de K o no. Si se encuentra que es cierto, entonces almacene la longitud del subarreglo si es el máximo obtenido hasta entonces. Finalmente, imprima la longitud máxima obtenida como respuesta requerida.

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

Enfoque eficiente: para optimizar el enfoque anterior, la idea es atravesar la array y verificar si arr[i] es un factor de K o no. Si se encuentra que es cierto, entonces incremente la longitud del subarreglo. De lo contrario, almacene la longitud del subarreglo si es el máximo obtenido hasta el momento y reinicie a 0 . Siga los pasos a continuación para resolver el problema:

  • Inicialice una variable, digamos MaxLen , para almacenar la longitud del subarreglo más largo de modo que cada elemento del subarreglo sea un factor de K .
  • Inicialice una variable, digamos Len , para almacenar la longitud del subarreglo actual.
  • Recorra la array y verifique si K % arr[i] = 0 o no. Si se determina que es cierto, incremente el valor de Len y actualice el valor de MaxLen = max(Len, MaxLen).
  • Finalmente, imprima el valor de MaxLen .

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

C++

// C++ program to implement
// the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the length of the longest
// subarray in which all elements are a factor of K
int find_longest_subarray(int A[], int N, int K)
{
 
    // Stores length of the longest subarray
    // in which all elements are a factor of K
    int MaxLen = 0;
 
    // Stores length of
    // the current subarray
    int Len = 0;
 
    // Traverse the array arr[]
    for (int i = 0; i < N; i++) {
 
        // If A[i] is a factor of K
        if (K % A[i] == 0) {
 
            // Update Len
            Len++;
 
            // Update MaxLen
            MaxLen = max(MaxLen, Len);
        }
 
        else {
            // Reset Len
            Len = 0;
        }
    }
 
    return MaxLen;
}
 
// Driver Code
int main()
{
    int A[] = { 2, 8, 3, 10, 6, 7, 4, 9 };
    int N = sizeof(A) / sizeof(A[0]);
    ;
    int K = 60;
 
    cout << find_longest_subarray(A, N, K);
    return 0;
}

Java

// Java program to implement
// the above approach
 
import java.util.*;
 
class GFG {
 
    // Function to find the length of the longest
    // subarray in which all elements are a factor of K
    static int find_longest_subarray(int[] A, int N,
                                     int K)
    {
        // Stores length of the longest subarray
        // in which all elements are a factor of K
        int MaxLen = 0;
 
        // Stores length of
        // the current subarray
        int Len = 0;
 
        // Traverse the array arr[]
        for (int i = 0; i < N; i++) {
 
            // If A[i] is a
            // factor of K
            if (K % A[i] == 0) {
 
                // Update Len
                Len++;
 
                // Update MaxLen
                MaxLen = Math.max(
                    MaxLen, Len);
            }
 
            // If A[i] is not a
            // factor of K
            else {
 
                // Update Len
                Len = 0;
            }
        }
 
        return MaxLen;
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        int[] A = { 2, 8, 3, 10, 6, 7, 4, 9 };
        int N = A.length;
        int K = 60;
        System.out.println(
            find_longest_subarray(A, N, K));
    }
}

Python3

# Python3 program to implement
# the above approach
  
# Function to find the length of the
# longest subarray in which all
# elements are a factor of K
def find_longest_subarray(A, N, K):
     
    # Stores length of the longest
    # subarray in which all elements
    # are a factor of K
    MaxLen = 0
  
    # Stores length of the
    # current subarray
    Len = 0
  
    # Traverse the array arr[]
    for i in range(N):
         
        # If A[i] is a factor of K
        if (K % A[i] == 0):
  
            # Update Len
            Len += 1
  
            # Update MaxLen
            MaxLen = max(MaxLen, Len)
             
        # If A[i] is not a
        # factor of K  
        else:
             
            # Reset Len
            Len = 0
             
    return MaxLen
 
# Driver Code
A = [ 2, 8, 3, 10, 6, 7, 4, 9 ]
N = len(A)
     
K = 60
  
print(find_longest_subarray(A, N, K))
  
# This code is contributed by susmitakundugoaldanga

C#

// C# program to implement
// the above approach
using System;
 
class GFG{
 
// Function to find the length of the longest
// subarray in which all elements are a factor of K
static int find_longest_subarray(int[] A, int N,
                                 int K)
{
     
    // Stores length of the longest subarray
    // in which all elements are a factor of K
    int MaxLen = 0;
 
    // Stores length of
    // the current subarray
    int Len = 0;
 
    // Traverse the array arr[]
    for(int i = 0; i < N; i++)
    {
         
        // If A[i] is a
        // factor of K
        if (K % A[i] == 0)
        {
             
            // Update Len
            Len++;
 
            // Update MaxLen
            MaxLen = Math.Max(MaxLen, Len);
        }
 
        // If A[i] is not a
        // factor of K
        else
        {
             
            // Update Len
            Len = 0;
        }
    }
    return MaxLen;
}
 
// Driver Code
public static void Main(string[] args)
{
    int[] A = { 2, 8, 3, 10, 6, 7, 4, 9 };
    int N = A.Length;
    int K = 60;
     
    Console.WriteLine(find_longest_subarray(
        A, N, K));
}
}
 
// This code is contributed by chitranayal

Javascript

<script>
 
// Javascript program to implement
// the above approach
 
// Function to find the length of the longest
// subarray in which all elements are a factor of K
function find_longest_subarray(A, N, K)
{
     
    // Stores length of the longest subarray
    // in which all elements are a factor of K
    let MaxLen = 0;
 
    // Stores length of
    // the current subarray
    let Len = 0;
 
    // Traverse the array arr[]
    for(let i = 0; i < N; i++)
    {
         
        // If A[i] is a
        // factor of K
        if (K % A[i] == 0)
        {
             
            // Update Len
            Len++;
 
            // Update MaxLen
            MaxLen = Math.max(MaxLen, Len);
        }
 
        // If A[i] is not a
        // factor of K
        else
        {
 
            // Update Len
            Len = 0;
        }
    }
    return MaxLen;
}
 
// Driver code
let A = [ 2, 8, 3, 10, 6, 7, 4, 9 ];
let N = A.length;
let K = 60;
 
document.write(find_longest_subarray(A, N, K));
 
// This code is contributed by code_hunt
 
</script>
Producción: 

3

 

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

Publicación traducida automáticamente

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