Dado un arreglo ordenado arr[] que consta de números distintos, la tarea es encontrar la longitud del subarreglo más largo que forma una progresión geométrica .
Ejemplos:
Entrada: arr[]={1, 2, 4, 7, 14, 28, 56, 89}
Salida: 4
Explicación:
Los subarreglos {1, 2, 4} y {7, 14, 28, 56} forman un GP .
Dado que {7, 14, 28, 56} es el más largo, la salida requerida es 4.Entrada: arr[]={3, 6, 7, 12, 24, 28, 56}
Salida: 2
Enfoque ingenuo: el enfoque más simple para resolver el problema es generar todos los subarreglos posibles y, para cada subarreglo, verificar si forma un GP o no. Siga actualizando la longitud máxima de dichos subarreglos encontrados. Finalmente, imprima la longitud máxima obtenida.
Complejidad temporal: O(N 3 )
Espacio auxiliar: O(N)
Enfoque eficiente: el enfoque anterior se puede optimizar mediante los siguientes pasos:
- Recorra la array y seleccione un par de elementos adyacentes, es decir, arr[i] y arr[i+1] , como los dos primeros términos de la progresión geométrica.
- Si arr[i+1] no es divisible por arr[i] , entonces no se puede considerar para la razón común. De lo contrario, tome arr[i+1] / arr[i] como la razón común para la Progresión Geométrica actual.
- Aumente y almacene la longitud de la progresión geométrica si los elementos posteriores tienen la misma proporción común. De lo contrario, actualice la proporción común igual a la proporción del nuevo par de elementos adyacentes.
- Finalmente, devuelve la longitud del subarreglo más largo que forma una progresión geométrica como salida.
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 return the length of
// the longest subarray forming a
// GP in a sorted array
int longestGP(int A[], int N)
{
// Base Case
if (N < 2)
return N;
// Stores the length of GP
// and the common ratio
int length = 1, common_ratio = 1;
// Stores the maximum
// length of the GP
int maxlength = 1;
// Traverse the array
for (int i = 0; i < N - 1; i++) {
// Check if the common ratio
// is valid for GP
if (A[i + 1] % A[i] == 0) {
// If the current common ratio
// is equal to previous common ratio
if (A[i + 1] / A[i] == common_ratio) {
// Increment the length of the GP
length = length + 1;
// Store the max length of GP
maxlength
= max(maxlength, length);
}
// Otherwise
else {
// Update the common ratio
common_ratio = A[i + 1] / A[i];
// Update the length of GP
length = 2;
}
}
else {
// Store the max length of GP
maxlength
= max(maxlength, length);
// Update the length of GP
length = 1;
}
}
// Store the max length of GP
maxlength = max(maxlength, length);
// Return the max length of GP
return maxlength;
}
// Driver Code
int main()
{
// Given array
int arr[] = { 1, 2, 4, 7, 14, 28, 56, 89 };
// Length of the array
int N = sizeof(arr) / sizeof(arr[0]);
// Function Call
cout << longestGP(arr, N);
return 0;
}
Java
// Java program to implement
// the above approach
import java.io.*;
class GFG{
// Function to return the length of
// the longest subarray forming a
// GP in a sorted array
static int longestGP(int A[], int N)
{
// Base Case
if (N < 2)
return N;
// Stores the length of GP
// and the common ratio
int length = 1, common_ratio = 1;
// Stores the maximum
// length of the GP
int maxlength = 1;
// Traverse the array
for(int i = 0; i < N - 1; i++)
{
// Check if the common ratio
// is valid for GP
if (A[i + 1] % A[i] == 0)
{
// If the current common ratio
// is equal to previous common ratio
if (A[i + 1] / A[i] == common_ratio)
{
// Increment the length of the GP
length = length + 1;
// Store the max length of GP
maxlength = Math.max(maxlength, length);
}
// Otherwise
else
{
// Update the common ratio
common_ratio = A[i + 1] / A[i];
// Update the length of GP
length = 2;
}
}
else
{
// Store the max length of GP
maxlength = Math.max(maxlength, length);
// Update the length of GP
length = 1;
}
}
// Store the max length of GP
maxlength = Math.max(maxlength, length);
// Return the max length of GP
return maxlength;
}
// Driver code
public static void main (String[] args)
{
// Given array
int arr[] = { 1, 2, 4, 7, 14, 28, 56, 89 };
// Length of the array
int N = arr.length;
// Function call
System.out.println(longestGP(arr, N));
}
}
// This code is contributed by jana_sayantan
Python3
# Python3 program to implement # the above approach # Function to return the length of # the longest subarray forming a # GP in a sorted array def longestGP(A, N): # Base Case if (N < 2): return N # Stores the length of GP # and the common ratio length = 1 common_ratio = 1 # Stores the maximum # length of the GP maxlength = 1 # Traverse the array for i in range(N - 1): # Check if the common ratio # is valid for GP if (A[i + 1] % A[i] == 0): # If the current common ratio # is equal to previous common ratio if (A[i + 1] // A[i] == common_ratio): # Increment the length of the GP length = length + 1 # Store the max length of GP maxlength = max(maxlength, length) # Otherwise else: # Update the common ratio common_ratio = A[i + 1] // A[i] # Update the length of GP length = 2 else: # Store the max length of GP maxlength = max(maxlength, length) # Update the length of GP length = 1 # Store the max length of GP maxlength = max(maxlength, length) # Return the max length of GP return maxlength # Driver Code # Given array arr = [ 1, 2, 4, 7, 14, 28, 56, 89 ] # Length of the array N = len(arr) # Function call print(longestGP(arr, N)) # This code is contributed by sanjoy_62
C#
// C# program to implement
// the above approach
using System;
class GFG{
// Function to return the length of
// the longest subarray forming a
// GP in a sorted array
static int longestGP(int []A, int N)
{
// Base Case
if (N < 2)
return N;
// Stores the length of GP
// and the common ratio
int length = 1, common_ratio = 1;
// Stores the maximum
// length of the GP
int maxlength = 1;
// Traverse the array
for(int i = 0; i < N - 1; i++)
{
// Check if the common ratio
// is valid for GP
if (A[i + 1] % A[i] == 0)
{
// If the current common ratio
// is equal to previous common ratio
if (A[i + 1] / A[i] == common_ratio)
{
// Increment the length of the GP
length = length + 1;
// Store the max length of GP
maxlength = Math.Max(maxlength,
length);
}
// Otherwise
else
{
// Update the common ratio
common_ratio = A[i + 1] /
A[i];
// Update the length of GP
length = 2;
}
}
else
{
// Store the max length of GP
maxlength = Math.Max(maxlength,
length);
// Update the length of GP
length = 1;
}
}
// Store the max length of GP
maxlength = Math.Max(maxlength,
length);
// Return the max length of GP
return maxlength;
}
// Driver code
public static void Main(String[] args)
{
// Given array
int []arr = {1, 2, 4, 7,
14, 28, 56, 89};
// Length of the array
int N = arr.Length;
// Function call
Console.WriteLine(longestGP(arr, N));
}
}
// This code is contributed by shikhasingrajput
Javascript
<script>
// JavaScript implementation of the above approach
// Function to return the length of
// the longest subarray forming a
// GP in a sorted array
function longestGP(A, N)
{
// Base Case
if (N < 2)
return N;
// Stores the length of GP
// and the common ratio
let length = 1, common_ratio = 1;
// Stores the maximum
// length of the GP
let maxlength = 1;
// Traverse the array
for(let i = 0; i < N - 1; i++)
{
// Check if the common ratio
// is valid for GP
if (A[i + 1] % A[i] == 0)
{
// If the current common ratio
// is equal to previous common ratio
if (A[i + 1] / A[i] == common_ratio)
{
// Increment the length of the GP
length = length + 1;
// Store the max length of GP
maxlength = Math.max(maxlength, length);
}
// Otherwise
else
{
// Update the common ratio
common_ratio = A[i + 1] / A[i];
// Update the length of GP
length = 2;
}
}
else
{
// Store the max length of GP
maxlength = Math.max(maxlength, length);
// Update the length of GP
length = 1;
}
}
// Store the max length of GP
maxlength = Math.max(maxlength, length);
// Return the max length of GP
return maxlength;
}
// Driver code
// Given array
let arr = [ 1, 2, 4, 7, 14, 28, 56, 89 ];
// Length of the array
let N = arr.length;
// Function call
document.write(longestGP(arr, N));
// This code is contributed by code_hunt.
</script>
Producción:
4
Complejidad de tiempo: O(N)
Complejidad de espacio: O(1)
Publicación traducida automáticamente
Artículo escrito por rimjhim_25 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA