Encuentre la posición i para dividir la array de manera que el prefijo sum hasta i-1, i y el sufijo sum hasta i+1 estén en GP con una relación común K

Dada una array , arr[] y un entero positivo K. La tarea es encontrar la posición, digamos i , del elemento en arr[] tal que el prefijo suma hasta i-1 , i y  el sufijo suma hasta i+1 estén en Progresión geométrica con una relación común K.

Ejemplos :

Entrada : arr[] = { 5, 1, 4, 20, 6, 15, 9, 10 }, K = 2
Salida : 4
Explicación : Las siguientes operaciones se realizan para obtener el GP requerido.
La suma del elemento de la posición 1 a la 3 es 5 + 1 + 4 = 10 y de la 5 a la 8 es 6 + 15 + 9 + 10 = 40.
Y el elemento en la posición 4 es 20.
Por lo tanto, 10, 20, 40 es una serie de progresión geométrica con razón común K.

Entrada : arr[] ={ -3, 5, 0, 2, 1, 25, 25, 100 }, K = 5 
Salida : 6 

 

Enfoque : El problema dado se puede resolver utilizando la búsqueda lineal y la suma básica de prefijos . Siga los pasos a continuación para resolver el problema dado.

  • Si el tamaño de la array es inferior a 3, no es posible ninguna secuencia, así que simplemente devuelva -1.
  • Inicialice una variable, digamos, arrSum para almacenar la suma de todos los elementos de arr[] .
  • Calcule la suma de la array arr[] y guárdela en arrSum .
  • si arrSum % R != 0 , entonces devuelve 0 . Donde R = K * K + 1 + K + 1 .
  • Inicialice una variable, digamos mid = K * (Sum / R) para almacenar el elemento medio de la serie GP con una relación común como K.
  • Tome una variable, digamos temp , para almacenar resultados temporales.
  • Iterar arr[] desde el índice 1 hasta ( tamaño de arr[]) – 2 con la variable i .
    • temperatura = temperatura + arr[i-1]
    • si arr[i] = medio
      • si temp = mid/k , devuelve (i+1) como respuesta.
      • de lo contrario devuelve 0 .
  • Si el bucle termina y ningún elemento en arr[] es igual a mid, simplemente devuelve 0 .

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

C++

// C++ program for the above approach
#include <iostream>
using namespace std;
 
// Function to check if there is
// an element forming G.P. series
// having common ratio k
int checkArray(int arr[], int N, int k)
{
 
    // If size of array is less than
    // three then return -1
    if (N < 3)
        return -1;
 
    // Initialize the variables
    int i, Sum = 0, temp = 0;
 
    // Calculate total sum of array
    for (i = 0; i < N; i++)
        Sum += arr[i];
 
    int R = (k * k + k + 1);
 
    if (Sum % R != 0)
        return 0;
 
    // Calculate Middle element of G.P. series
    int Mid = k * (Sum / R);
 
    // Iterate over the range
    for (i = 1; i < N - 1; i++) {
 
        // Store the first element of G.P.
        // series in the variable temp
        temp += arr[i - 1];
 
        if (arr[i] == Mid) {
 
            // Return position of middle element
            // of the G.P. series if the first
            // element is in G.P. of common ratio k
            if (temp == Mid / k)
                return i + 1;
 
            // Else return 0
            else
                return 0;
        }
    }
 
    // if middle element is not found in arr[]
    return 0;
}
 
// Driver Code
int main()
{
    // Given array
    int arr[] = { 5, 1, 4, 20, 6, 15, 9, 10 };
 
    int N = sizeof(arr) / sizeof(arr[0]);
 
    int K = 2;
 
    cout << checkArray(arr, N, K) << endl;
 
    return 0;
}

Java

// Java program for the above approach
 
import java.io.*;
 
class GFG {
   
// Function to check if there is
// an element forming G.P. series
// having common ratio k
static int checkArray(int arr[], int N, int k)
{
 
    // If size of array is less than
    // three then return -1
    if (N < 3)
        return -1;
 
    // Initialize the variables
    int i, Sum = 0, temp = 0;
 
    // Calculate total sum of array
    for (i = 0; i < N; i++)
        Sum += arr[i];
 
    int R = (k * k + k + 1);
 
    if (Sum % R != 0)
        return 0;
 
    // Calculate Middle element of G.P. series
    int Mid = k * (Sum / R);
 
    // Iterate over the range
    for (i = 1; i < N - 1; i++) {
 
        // Store the first element of G.P.
        // series in the variable temp
        temp += arr[i - 1];
 
        if (arr[i] == Mid) {
 
            // Return position of middle element
            // of the G.P. series if the first
            // element is in G.P. of common ratio k
            if (temp == Mid / k)
                return i + 1;
 
            // Else return 0
            else
                return 0;
        }
    }
 
    // if middle element is not found in arr[]
    return 0;
}
 
// Driver Code
public static void main (String[] args) {
   
    // Given array
    int arr[] = { 5, 1, 4, 20, 6, 15, 9, 10 };
 
    int N = arr.length;
 
    int K = 2;
 
       System.out.println(checkArray(arr, N, K));
}
}
 
// This code is contributed by Dharanendra L V.

Python3

# python program for the above approach
 
# Function to check if there is
# an element forming G.P. series
# having common ratio k
def checkArray(arr, N, k):
 
        # If size of array is less than
        # three then return -1
    if (N < 3):
        return -1
 
        # Initialize the variables
    Sum = 0
    temp = 0
 
    # Calculate total sum of array
    for i in range(0, N):
        Sum += arr[i]
 
    R = (k * k + k + 1)
 
    if (Sum % R != 0):
        return 0
 
        # Calculate Middle element of G.P. series
    Mid = k * (Sum // R)
 
    # Iterate over the range
    for i in range(1, N-1):
 
                # Store the first element of G.P.
                # series in the variable temp
        temp += arr[i - 1]
 
        if (arr[i] == Mid):
 
                        # Return position of middle element
                        # of the G.P. series if the first
                        # element is in G.P. of common ratio k
            if (temp == Mid // k):
                return i + 1
 
                # Else return 0
            else:
                return 0
 
        # if middle element is not found in arr[]
    return 0
 
# Driver Code
if __name__ == "__main__":
 
    # Given array
    arr = [5, 1, 4, 20, 6, 15, 9, 10]
    N = len(arr)
    K = 2
 
    print(checkArray(arr, N, K))
 
    # This code is contributed by rakeshsahni

C#

// C# program for the above approach
using System;
class GFG {
 
    // Function to check if there is
    // an element forming G.P. series
    // having common ratio k
    static int checkArray(int[] arr, int N, int k)
    {
 
        // If size of array is less than
        // three then return -1
        if (N < 3)
            return -1;
 
        // Initialize the variables
        int i, Sum = 0, temp = 0;
 
        // Calculate total sum of array
        for (i = 0; i < N; i++)
            Sum += arr[i];
 
        int R = (k * k + k + 1);
 
        if (Sum % R != 0)
            return 0;
 
        // Calculate Middle element of G.P. series
        int Mid = k * (Sum / R);
 
        // Iterate over the range
        for (i = 1; i < N - 1; i++) {
 
            // Store the first element of G.P.
            // series in the variable temp
            temp += arr[i - 1];
 
            if (arr[i] == Mid) {
 
                // Return position of middle element
                // of the G.P. series if the first
                // element is in G.P. of common ratio k
                if (temp == Mid / k)
                    return i + 1;
 
                // Else return 0
                else
                    return 0;
            }
        }
 
        // if middle element is not found in arr[]
        return 0;
    }
 
    // Driver Code
    public static void Main(string[] args)
    {
 
        // Given array
        int[] arr = { 5, 1, 4, 20, 6, 15, 9, 10 };
 
        int N = arr.Length;
 
        int K = 2;
 
        Console.WriteLine(checkArray(arr, N, K));
    }
}
 
// This code is contributed by ukasp.

Javascript

<script>
        // JavaScript Program to implement
        // the above approach
 
        // Function to check if there is
        // an element forming G.P. series
        // having common ratio k
        function checkArray(arr, N, k) {
 
            // If size of array is less than
            // three then return -1
            if (N < 3)
                return -1;
 
            // Initialize the variables
            let i, Sum = 0, temp = 0;
 
            // Calculate total sum of array
            for (i = 0; i < N; i++)
                Sum += arr[i];
 
            let R = (k * k + k + 1);
 
            if (Sum % R != 0)
                return 0;
 
            // Calculate Middle element of G.P. series
            let Mid = k * (Sum / R);
 
            // Iterate over the range
            for (i = 1; i < N - 1; i++) {
 
                // Store the first element of G.P.
                // series in the variable temp
                temp += arr[i - 1];
 
                if (arr[i] == Mid) {
 
                    // Return position of middle element
                    // of the G.P. series if the first
                    // element is in G.P. of common ratio k
                    if (temp == Mid / k)
                        return i + 1;
 
                    // Else return 0
                    else
                        return 0;
                }
            }
 
            // if middle element is not found in arr[]
            return 0;
        }
 
        // Driver Code
 
        // Given array
        let arr = [5, 1, 4, 20, 6, 15, 9, 10];
        let N = arr.length;
        let K = 2;
        document.write(checkArray(arr, N, K) + "<br>");
 
// This code is contributed by Potta Lokesh
    </script>
Producción

4

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

Publicación traducida automáticamente

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