Dada una array arr[] de N enteros, la tarea es encontrar el recuento de todas las subarreglas de la array dada de al menos tamaño 3 que forman una progresión geométrica .
Ejemplos:
Entrada: arr[] = {1, 2, 4, 8}
Salida: 3
Explicación: Los subarreglos necesarios que forman una progresión geométrica son:
- {1, 2, 4}
- {2, 4, 8}
- {1, 2, 4, 8}
Entrada: arr[] = {1, 2, 4, 8, 16, 24}
Salida: 6
Explicación: Los subarreglos necesarios que forman la progresión geométrica son:
- {1, 2, 4}
- {2, 4, 8}
- {4, 8, 16}
- {1, 2, 4, 8}
- {2, 4, 8, 16}
- {1, 2, 4, 8, 16}
Enfoque ingenuo: el enfoque más simple es generar todos los subarreglos de tamaño de al menos 3 y contar todos esos subarreglos que forman una progresión geométrica . Imprima el conteo después de verificar todos los subarreglos.
Complejidad temporal: O(N 3 )
Espacio auxiliar: O(N)
Enfoque eficiente: la idea es usar una propiedad de la progresión geométrica , es decir, {a, b, c} es GP si y solo si a*c = b . Siga los pasos a continuación para resolver el problema:
- Inicialice una variable, res , y cuente con 0 para almacenar los subarreglos totales que forman la progresión geométrica y la longitud del subarreglo actual.
- Recorra la array dada sobre el rango [2, N – 1] e incremente el valor de count si el elemento actual forma una progresión geométrica, es decir, arr[i]*arr[i – 2] = arr[i – 1]*arr [i – 1] De lo contrario, establezca el recuento en cero.
- Agregue count a res para cada iteración en los pasos anteriores.
- Después de los pasos anteriores, imprima el valor de res como el conteo resultante.
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 count all the subarrays
// of size at least 3 forming GP
int numberOfGP(int L[], int N)
{
// If array size is less than 3
if (N <= 2)
return 0;
// Stores the count of subarray
int count = 0;
// Stores the count of subarray
// for each iteration
int res = 0;
// Traverse the array
for (int i = 2; i < N; ++i) {
// Check if L[i] forms GP
if (L[i - 1] * L[i - 1]
== L[i] * L[i - 2]) {
++count;
}
// Otherwise, update count to 0
else {
count = 0;
}
// Update the final count
res += count;
}
// Return the final count
return res;
}
// Driver Code
int main()
{
// Given array arr[]
int arr[] = { 1, 2, 4, 8, 16, 24 };
int N = sizeof(arr) / sizeof(arr[0]);
// Function Call
cout << numberOfGP(arr, N);
return 0;
}
Java
// Java program for the
// above approach
import java.util.*;
class GFG{
// Function to count all
// the subarrays of size
// at least 3 forming GP
static int numberOfGP(int L[],
int N)
{
// If array size
// is less than 3
if (N <= 2)
return 0;
// Stores the count
// of subarray
int count = 0;
// Stores the count
// of subarray for
// each iteration
int res = 0;
// Traverse the array
for (int i = 2; i < N; ++i)
{
// Check if L[i] forms GP
if (L[i - 1] * L[i - 1] ==
L[i] * L[i - 2])
{
++count;
}
// Otherwise, update
// count to 0
else
{
count = 0;
}
// Update the
// final count
res += count;
}
// Return the final count
return res;
}
// Driver Code
public static void main(String[] args)
{
// Given array arr[]
int arr[] = {1, 2, 4,
8, 16, 24};
int N = arr.length;
// Function Call
System.out.print(numberOfGP(arr, N));
}
}
// This code is contributed by gauravrajput1
Python3
# Python3 program for the above approach # Function to count all the subarrays # of size at least 3 forming GP def numberOfGP(L, N): # If array size is less than 3 if (N <= 2): return 0 # Stores the count of subarray count = 0 # Stores the count of subarray # for each iteration res = 0 # Traverse the array for i in range(2, N): # Check if L[i] forms GP if (L[i - 1] * L[i - 1] == L[i] * L[i - 2]): count += 1 # Otherwise, update count to 0 else: count = 0 # Update the final count res += count # Return the final count return res # Driver Code if __name__ == '__main__': # Given array arr[] arr = [ 1, 2, 4, 8, 16, 24 ] N = len(arr) # Function Call print(numberOfGP(arr, N)) # This code is contributed by mohit kumar 29
C#
// C# program for the
// above approach
using System;
class GFG {
// Function to count all
// the subarrays of size
// at least 3 forming GP
static int numberOfGP(int[] L,
int N)
{
// If array size
// is less than 3
if (N <= 2)
return 0;
// Stores the count
// of subarray
int count = 0;
// Stores the count
// of subarray for
// each iteration
int res = 0;
// Traverse the array
for (int i = 2; i < N; ++i)
{
// Check if L[i] forms GP
if (L[i - 1] * L[i - 1] ==
L[i] * L[i - 2])
{
++count;
}
// Otherwise, update
// count to 0
else
{
count = 0;
}
// Update the
// final count
res += count;
}
// Return the final
// count
return res;
}
// Driver Code
public static void Main(String[] args)
{
// Given array arr[]
int[] arr = {1, 2, 4, 8, 16, 24};
int N = arr.Length;
// Function Call
Console.Write(numberOfGP(arr, N));
}
}
// This code is contributed by Chitranayal
Javascript
<script>
// Javascript program for the above approach
// Function to count all the subarrays
// of size at least 3 forming GP
function numberOfGP(L, N)
{
// If array size is less than 3
if (N <= 2)
return 0;
// Stores the count of subarray
let count = 0;
// Stores the count of subarray
// for each iteration
let res = 0;
// Traverse the array
for (let i = 2; i < N; ++i) {
// Check if L[i] forms GP
if (L[i - 1] * L[i - 1]
== L[i] * L[i - 2]) {
++count;
}
// Otherwise, update count to 0
else {
count = 0;
}
// Update the final count
res += count;
}
// Return the final count
return res;
}
// Driver Code
// Given array arr[]
let arr = [ 1, 2, 4, 8, 16, 24];
let N = arr.length;
// Function Call
document.write(numberOfGP(arr, N));
// This code is contributed by Mayank Tyagi
</script>
Producción
6
Complejidad temporal: O(N)
Espacio auxiliar: O(N)