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