Cuente los subarreglos de al menos tamaño 3 formando una progresión geométrica (GP)

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. {1, 2, 4}
  2. {2, 4, 8}
  3. {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. {1, 2, 4}
  2. {2, 4, 8}
  3. {4, 8, 16}
  4. {1, 2, 4, 8}
  5. {2, 4, 8, 16}
  6. {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)

Publicación traducida automáticamente

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