Dada una serie de progresión geométrica en arr[] y Q consultas en forma de [L, R] , donde L es el límite izquierdo del rango y R es el límite derecho. La tarea es encontrar la suma de los elementos de la progresión geométrica en el rango dado.
Nota: El rango tiene un índice de 1 y 1 ≤ L, R ≤ N , donde N es el tamaño de arr.
Ejemplos:
Entrada: arr[] = {2, 4, 8, 16, 32, 64, 128, 256}, Q = [[2, 4], [2, 6], [5, 8]]
Salida:
28
124
480
Explicación:
Rango 1: arr = {4, 8, 16}. Por lo tanto suma = 28
Rango 2: arr = {4, 8, 16, 32, 64}. Por lo tanto suma = 124
Rango 3: arr = {32, 64, 128, 256}. Por lo tanto suma = 480Entrada: arr[] = {7, 7, 7, 7, 7, 7}, Q = [[1, 6], [2, 4], [3, 3]]
Salida:
42
21
7
Explicación:
Rango 1 : arr = {7, 7, 7, 7, 7, 7}. Por lo tanto suma = 42
Rango 2: arr = {7, 7, 7}. Por lo tanto suma = 21
Rango 3: arr = {7}. Por lo tanto suma = 7
Enfoque : dado que la secuencia dada es una progresión geométrica , la suma se puede encontrar fácilmente en dos pasos de manera eficiente:
- Obtiene el primer elemento del rango.
- Si d = 1, entonces multiplíquele d*k , de lo contrario, multiplíquele (d k – 1)/(d – 1) , donde d es la proporción común del GP y k es el número de elementos en el rango.
Por ejemplo:
suponga que a[i] es el primer elemento del rango, d es la razón común de GP yk es el número de elementos en el rango dado.
entonces la suma del rango seria
= a[i] + a[i+1] + a[i+2] + ….. + a[i+k-1]
= a[i] + (a[i] * d) + (a[ i] * d * d) + …. + (a[i] * d k)
= a[i] * (1 + d + … + d k )
= a[i] * (d k – 1)/(d – 1)
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to find the sum
// of elements of an GP in the
// given range
#include <bits/stdc++.h>
using namespace std;
// Function to find sum in the given range
int findSum(int arr[], int n,
int left, int right)
{
// Find the value of k
int k = right - left + 1;
// Find the common difference
int d = arr[1] / arr[0];
// Find the sum
int ans = arr[left - 1];
if (d == 1)
ans = ans * d * k;
else
ans = ans * ((int)pow(d, k) - 1 /
(d - 1));
return ans;
}
// Driver Code
int main()
{
int arr[] = { 2, 4, 8, 16, 32,
64, 128, 256 };
int queries = 3;
int q[][2] = { { 2, 4 }, { 2, 6 },
{ 5, 8 } };
int n = sizeof(arr) / sizeof(arr[0]);
for(int i = 0; i < queries; i++)
cout << (findSum(arr, n, q[i][0], q[i][1]))
<< endl;
return 0;
}
// This code is contributed by divyeshrabadiya07
Java
// Java program to find the sum
// of elements of an GP in the
// given range
import java.io.*;
import java.util.*;
class GFG{
// Function to find sum in the given range
static int findSum(int[] arr, int n,
int left, int right)
{
// Find the value of k
int k = right - left + 1;
// Find the common difference
int d = arr[1] / arr[0];
// Find the sum
int ans = arr[left - 1];
if (d == 1)
ans = ans * d * k;
else
ans = ans * ((int)Math.pow(d, k) - 1 /
(d - 1));
return ans;
}
// Driver Code
public static void main(String args[])
{
int[] arr = { 2, 4, 8, 16, 32,
64, 128, 256 };
int queries = 3;
int[][] q = { { 2, 4 }, { 2, 6 }, { 5, 8 } };
int n = arr.length;
for(int i = 0; i < queries; i++)
System.out.println(findSum(arr, n, q[i][0],
q[i][1]));
}
}
// This code is contributed by offbeat
Python3
# Python3 program to # find the sum of elements # of an GP in the given range # Function to find sum in the given range def findSum(arr, n, left, right): # Find the value of k k = right - left + 1 # Find the common difference d = arr[1] // arr[0] # Find the sum ans = arr[left - 1] if d == 1: ans = ans * d * k else: ans = ans * (d ** k - 1) // (d -1) return ans # Driver code if __name__ == '__main__': arr = [ 2, 4, 8, 16, 32, 64, 128, 256 ] queries = 3 q = [[ 2, 4 ], [ 2, 6 ], [ 5, 8 ]] n = len(arr) for i in range(queries): print(findSum(arr, n, q[i][0], q[i][1]))
C#
// C# program to find the sum
// of elements of an GP in the
// given range
using System;
class GFG{
// Function to find sum in the given range
static int findSum(int[] arr, int n,
int left, int right)
{
// Find the value of k
int k = right - left + 1;
// Find the common difference
int d = arr[1] / arr[0];
// Find the sum
int ans = arr[left - 1];
if (d == 1)
ans = ans * d * k;
else
ans = ans * ((int)Math.Pow(d, k) - 1 /
(d - 1));
return ans;
}
// Driver Code
public static void Main(string []args)
{
int[] arr = { 2, 4, 8, 16, 32,
64, 128, 256 };
int queries = 3;
int[,] q = { { 2, 4 }, { 2, 6 }, { 5, 8 } };
int n = arr.Length;
for(int i = 0; i < queries; i++)
Console.Write(findSum(arr, n, q[i, 0],
q[i, 1]) + "\n");
}
}
// This code is contributed by rutvik_56
Javascript
<script>
// JavaScript program to find the sum
// of elements of an GP in the
// given range
// Function to find sum in the given range
function findSum(arr, n, left, right) {
// Find the value of k
let k = right - left + 1;
// Find the common difference
let d = arr[1] / arr[0];
// Find the sum
let ans = arr[left - 1];
if (d == 1)
ans = ans * d * k;
else
ans = ans * (Math.pow(d, k) - 1 / (d - 1));
return ans;
}
// Driver Code
let arr = [2, 4, 8, 16, 32,
64, 128, 256];
let queries = 3;
let q = [[2, 4], [2, 6],
[5, 8]];
let n = arr.length;
for (let i = 0; i < queries; i++)
document.write(findSum(arr, n, q[i][0], q[i][1]));
// This code is contributed by blalverma92
</script>
28 124 480
- Complejidad del tiempo: O(Q)
- Complejidad del espacio: O(1)
Publicación traducida automáticamente
Artículo escrito por SHUBHAMSINGH10 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA