Dada una serie aritmética 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 AP 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, 6, 8, 10, 12, 14, 16}, Q = [[2, 4], [2, 6], [5, 8]]
Salida:
18
40
52
Explicación:
Rango 1: arr = {4, 6, 8}. Por lo tanto suma = 18
Rango 2: arr = {4, 6, 8, 10, 12}. Por lo tanto suma = 40
Rango 3: arr = {10, 12, 14, 16}. Por lo tanto suma = 52
Entrada: arr[] = {7, 14, 21, 28, 35, 42}, Q = [[1, 6], [2, 4], [3, 3]]
Salida:
147
63
21
Explicación:
Rango 1: arr = {7, 14, 21, 28, 35, 42}. Por lo tanto suma = 147
Rango 2: arr = {14, 21, 28}. Por lo tanto suma = 63
Rango 3: arr = {21}. Por lo tanto suma = 21
Enfoque : dado que la secuencia dada es una progresión aritmética , la suma se puede encontrar fácilmente en dos pasos de manera eficiente:
- Multiplique el primer elemento del rango por el número de elementos en el rango.
- Súmale (d*k*(k+1))/2 , donde d es la diferencia común del AP y k es (número de elementos en el rango – 1) que corresponde al número de espacios.
Por ejemplo:
suponga que a[i] es el primer elemento del rango, d es la diferencia común de AP y k+1 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]
= a[i] + a[i] + d + a[i] + 2 * d+…. + a[i] + k * d
= a[i] * (k + 1) + d * (1 + 2 + … + k)
= a[i] * (k + 1) + (d * k * ( k+1))/2
A continuación se muestra la implementación del enfoque anterior:
CPP
// C++ program to find the sum of elements // of an AP 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; // Find the common difference int d = arr[1] - arr[0]; // Find the sum int ans = arr[left - 1] * (k + 1); ans = ans + (d * (k * (k + 1))) / 2; return ans; } // Driver code int main() { int arr[] = { 2, 4, 6, 8, 10, 12, 14, 16 }; int queries = 3; int q[queries][2] = { { 2, 4 }, { 2, 6 }, { 5, 6 } }; 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; }
Java
// Java program to find the sum of elements // of an AP in the given range 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; // Find the common difference int d = arr[1] - arr[0]; // Find the sum int ans = arr[left - 1] * (k + 1); ans = ans + (d * (k * (k + 1))) / 2; return ans; } // Driver code public static void main(String[] args) { int arr[] = { 2, 4, 6, 8, 10, 12, 14, 16 }; int queries = 3; int q[][] = { { 2, 4 }, { 2, 6 }, { 5, 6 } }; int n = arr.length; for (int i = 0; i < queries; i++) System.out.print(findSum(arr, n, q[i][0], q[i][1]) +"\n"); } } // This code is contributed by Princi Singh
Python3
# Python program to find the sum of elements # of an AP 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; # Find the common difference d = arr[1] - arr[0]; # Find the sum ans = arr[left - 1] * (k + 1); ans = ans + (d * (k * (k + 1))) // 2; return ans; # Driver code if __name__ == '__main__': arr = [ 2, 4, 6, 8, 10, 12, 14, 16 ]; queries = 3; q = [[ 2, 4 ],[ 2, 6 ],[ 5, 6 ]]; n = len(arr); for i in range(queries): print(findSum(arr, n, q[i][0], q[i][1])); # This code is contributed by sapnasingh4991
C#
// C# program to find the sum of elements // of an AP 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; // Find the common difference int d = arr[1] - arr[0]; // Find the sum int ans = arr[left - 1] * (k + 1); ans = ans + (d * (k * (k + 1))) / 2; return ans; } // Driver code public static void Main(String[] args) { int []arr = { 2, 4, 6, 8, 10, 12, 14, 16 }; int queries = 3; int [,]q = { { 2, 4 }, { 2, 6 }, { 5, 6 } }; 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 PrinciRaj1992
Javascript
<script> // JavaScript program to find the sum of elements // of an AP 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; // Find the common difference let d = arr[1] - arr[0]; // Find the sum let ans = arr[left - 1] * (k + 1); ans = ans + (d * (k * (k + 1))) / 2; return ans; } // Driver Code let arr = [ 2, 4, 6, 8, 10, 12, 14, 16 ]; let queries = 3; let q = [[ 2, 4 ], [ 2, 6 ], [ 5, 6 ]]; let n = arr.length; for (let i = 0; i < queries; i++) document.write(findSum(arr, n, q[i][0], q[i][1]) +"<br/>"); </script>
18 40 22
Complejidad temporal: O(1)
Complejidad espacial: O(1)
Publicación traducida automáticamente
Artículo escrito por AmanGupta65 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA