Dada una array arr[] de N enteros y Q consultas donde cada fila consta de dos números L y R que denotan el rango [L, R] , la tarea es encontrar el valor de la suma y resta alternativas del elemento de la array entre el rango [izquierda, derecha] .
Ejemplos:
Entrada: arr[] = {10, 13, 15, 2, 45, 31, 22, 3, 27}, Q[][] = {{2, 5}, {6, 8}, {1, 7} , {4, 8}, {0, 5}}
Salida: 27 46 -33 60 24
Explicación:
El resultado de la consulta {2, 5} es 27 (15 – 2 + 45 – 31)
Resultado de la consulta {6, 8} es 46 ( 22 – 3 + 27)
El resultado de la consulta {1, 7} es -33 ( 13 – 15 + 2 – 45 + 31 – 22 + 3)
El resultado de la consulta {4, 8} es 60 ( 45 – 31 + 22 – 3 + 27)
El resultado de la consulta {0, 5} es 24 (10 – 13 + 15 – 2 + 45 – 31)Entrada: arr[] = {1, 1, 1, 1, 1, 1, 1, 1, 1}, Q[] = {{2, 5}, {6, 8}, {1, 7}, { 4, 8}, {0, 5}}
Salida: 0 1 1 1 0
Enfoque ingenuo: la idea ingenua es iterar desde el índice L a R para cada consulta y encontrar el valor de sumar y restar alternativamente los elementos de la array e imprimir el valor después de realizar las operaciones.
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;
// Structure to represent a range query
struct Query {
int L, R;
};
// Function to find the result of
// alternatively adding and subtracting
// elements in the range [L, R]
int findResultUtil(int arr[],
int L, int R)
{
int result = 0;
// A boolean variable flag to
// alternatively add and subtract
bool flag = false;
// Iterate from [L, R]
for (int i = L; i <= R; i++) {
// if flag is false, then
// add & toggle the flag
if (flag == false) {
result = result + arr[i];
flag = true;
}
// if flag is true subtract
// and toggle the flag
else {
result = result - arr[i];
flag = false;
}
}
// Return the final result
return result;
}
// Function to find the value
// for each query
void findResult(int arr[], int n,
Query q[], int m)
{
// Iterate for each query
for (int i = 0; i < m; i++) {
cout << findResultUtil(arr,
q[i].L,
q[i].R)
<< " ";
}
}
// Driver Code
int main()
{
// Given array
int arr[] = { 10, 13, 15, 2, 45,
31, 22, 3, 27 };
int n = sizeof(arr) / sizeof(arr[0]);
// Given Queries
Query q[] = { { 2, 5 }, { 6, 8 },
{ 1, 7 }, { 4, 8 },
{ 0, 5 } };
int m = sizeof(q) / sizeof(q[0]);
// Function Call
findResult(arr, n, q, m);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
// Structure to represent a range query
static class Query
{
int L, R;
public Query(int l, int r)
{
super();
L = l;
R = r;
}
};
// Function to find the result of
// alternatively adding and subtracting
// elements in the range [L, R]
static int findResultUtil(int arr[],
int L, int R)
{
int result = 0;
// A boolean variable flag to
// alternatively add and subtract
boolean flag = false;
// Iterate from [L, R]
for(int i = L; i <= R; i++)
{
// If flag is false, then
// add & toggle the flag
if (flag == false)
{
result = result + arr[i];
flag = true;
}
// If flag is true subtract
// and toggle the flag
else
{
result = result - arr[i];
flag = false;
}
}
// Return the final result
return result;
}
// Function to find the value
// for each query
static void findResult(int arr[], int n,
Query q[], int m)
{
// Iterate for each query
for(int i = 0; i < m; i++)
{
System.out.print(findResultUtil(arr,
q[i].L, q[i].R) + " ");
}
}
// Driver Code
public static void main(String[] args)
{
// Given array
int arr[] = { 10, 13, 15, 2, 45,
31, 22, 3, 27 };
int n = arr.length;
// Given Queries
Query q[] = { new Query(2, 5), new Query(6, 8),
new Query(1, 7), new Query(4, 8),
new Query(0, 5) };
int m = q.length;
// Function call
findResult(arr, n, q, m);
}
}
// This code is contributed by Princi Singh
Python3
# Python3 program for the above approach # Function to find the result of # alternatively adding and subtracting # elements in the range [L, R] def findResultUtil(arr, L, R): result = 0 # A boolean variable flag to # alternatively add and subtract flag = False # Iterate from [L, R] for i in range(L, R + 1): # If flag is False, then # add & toggle the flag if (flag == False): result = result + arr[i] flag = True # If flag is True subtract # and toggle the flag else: result = result - arr[i] flag = False # Return the final result return result # Function to find the value # for each query def findResult(arr, n, q, m): # Iterate for each query for i in range(m): print(findResultUtil(arr, q[i][0], q[i][1]), end = " ") # Driver Code if __name__ == '__main__': # Given array arr = [ 10, 13, 15, 2, 45, 31, 22, 3, 27 ] n = len(arr) # Given Queries q = [ [ 2, 5 ], [ 6, 8 ], [ 1, 7 ], [ 4, 8 ], [ 0, 5 ] ] m = len(q) # Function Call findResult(arr, n, q, m) # This code is contributed by mohit kumar 29
C#
// C# program for the above approach
using System;
class GFG{
// Structure to represent a range query
class Query
{
public int L, R;
public Query(int l, int r)
{
L = l;
R = r;
}
};
// Function to find the result of
// alternatively adding and subtracting
// elements in the range [L, R]
static int findResultUtil(int []arr,
int L, int R)
{
int result = 0;
// A bool variable flag to
// alternatively add and subtract
bool flag = false;
// Iterate from [L, R]
for(int i = L; i <= R; i++)
{
// If flag is false, then
// add & toggle the flag
if (flag == false)
{
result = result + arr[i];
flag = true;
}
// If flag is true subtract
// and toggle the flag
else
{
result = result - arr[i];
flag = false;
}
}
// Return the readonly result
return result;
}
// Function to find the value
// for each query
static void findResult(int []arr, int n,
Query []q, int m)
{
// Iterate for each query
for(int i = 0; i < m; i++)
{
Console.Write(findResultUtil(arr,
q[i].L, q[i].R) + " ");
}
}
// Driver Code
public static void Main(String[] args)
{
// Given array
int []arr = { 10, 13, 15, 2, 45,
31, 22, 3, 27 };
int n = arr.Length;
// Given Queries
Query []q = { new Query(2, 5), new Query(6, 8),
new Query(1, 7), new Query(4, 8),
new Query(0, 5) };
int m = q.Length;
// Function call
findResult(arr, n, q, m);
}
}
// This code is contributed by gauravrajput1
Javascript
<script>
// Javascript program for the above approach
// Function to find the result of
// alternatively adding and subtracting
// elements in the range [L, R]
function findResultUtil(arr, L, R)
{
var result = 0;
// A boolean variable flag to
// alternatively add and subtract
var flag = false;
// Iterate from [L, R]
for (var i = L; i <= R; i++) {
// if flag is false, then
// add & toggle the flag
if (flag == false) {
result = result + arr[i];
flag = true;
}
// if flag is true subtract
// and toggle the flag
else {
result = result - arr[i];
flag = false;
}
}
// Return the final result
return result;
}
// Function to find the value
// for each query
function findResult(arr, n, q, m)
{
// Iterate for each query
for (var i = 0; i < m; i++) {
document.write( findResultUtil(arr,
q[i][0],
q[i][1])
+ " ");
}
}
// Driver Code
// Given array
var arr = [10, 13, 15, 2, 45,
31, 22, 3, 27 ];
var n = arr.length;
// Given Queries
var q = [ [ 2, 5 ], [ 6, 8 ],
[ 1, 7 ], [ 4, 8 ],
[ 0, 5 ] ];
var m = q.length;
// Function Call
findResult(arr, n, q, m);
</script>
Producción:
27 46 -33 60 24
Complejidad temporal: O(N*Q)
Espacio auxiliar: O(1)
Enfoque eficiente: el enfoque eficiente es usar Prefix Sum Array para resolver el problema anterior. A continuación se muestran los pasos:
- Inicialice el primer elemento de la array de prefijos (por ejemplo , pre[] ) en el primer elemento de arr[] .
- Recorra un índice de 1 a N-1 y sume y reste alternativamente los elementos de arr[i] de pre[i-1] y guárdelo en pre[i] para hacer una array de prefijos.
- Ahora, itere a través de cada consulta de 1 a Q y encuentre el resultado sobre la base de los siguientes casos:
- Caso 1: si L es cero, el resultado es pre[R] .
- Caso 2: si L no es cero, encuentre el resultado usando la ecuación:
result = Query(L, R) = pre[R] – pre[L - 1]
- Si L es impar, multiplique el resultado anterior por -1 .
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;
// Structure to represent a query
struct Query {
int L, R;
};
// This function fills the Prefix Array
void fillPrefixArray(int arr[], int n,
int prefixArray[])
{
// Initialise the prefix array
prefixArray[0] = arr[0];
// Iterate all the element of arr[]
// and update the prefix array
for (int i = 1; i < n; i++) {
// If n is even then, add the
// previous value of prefix array
// with the current value of arr
if (i % 2 == 0) {
prefixArray[i]
= prefixArray[i - 1]
+ arr[i];
}
// if n is odd, then subtract
// the previous value of prefix
// Array from current value
else {
prefixArray[i]
= prefixArray[i - 1]
- arr[i];
}
}
}
// Function to find the result of
// alternatively adding and subtracting
// elements in the range [L< R]
int findResultUtil(int prefixArray[],
int L, int R)
{
int result;
// Case 1 : when L is zero
if (L == 0) {
result = prefixArray[R];
}
// Case 2 : When L is non zero
else {
result = prefixArray[R]
- prefixArray[L - 1];
}
// If L is odd means range starts from
// odd position multiply result by -1
if (L & 1) {
result = result * (-1);
}
// Return the final result
return result;
}
// Function to find the sum of all
// alternative add and subtract
// between ranges [L, R]
void findResult(int arr[], int n,
Query q[], int m)
{
// Declare prefix array
int prefixArray[n];
// Function Call to fill prefix arr[]
fillPrefixArray(arr, n, prefixArray);
// Iterate for each query
for (int i = 0; i < m; i++) {
cout << findResultUtil(prefixArray,
q[i].L,
q[i].R)
<< " ";
}
}
// Driver Code
int main()
{
// Given array
int arr[] = { 10, 13, 15, 2, 45,
31, 22, 3, 27 };
int n = sizeof(arr) / sizeof(arr[0]);
// Given Queries
Query q[] = { { 2, 5 }, { 6, 8 },
{ 1, 7 }, { 4, 8 },
{ 0, 5 } };
int m = sizeof(q) / sizeof(q[0]);
// Function Call
findResult(arr, n, q, m);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
// Structure to represent a query
static class Query
{
int L, R;
public Query(int l, int r)
{
super();
L = l;
R = r;
}
};
// This function fills the Prefix Array
static void fillPrefixArray(int arr[], int n,
int prefixArray[])
{
// Initialise the prefix array
prefixArray[0] = arr[0];
// Iterate all the element of arr[]
// and update the prefix array
for (int i = 1; i < n; i++)
{
// If n is even then, add the
// previous value of prefix array
// with the current value of arr
if (i % 2 == 0)
{
prefixArray[i] = prefixArray[i - 1] +
arr[i];
}
// if n is odd, then subtract
// the previous value of prefix
// Array from current value
else
{
prefixArray[i] = prefixArray[i - 1] -
arr[i];
}
}
}
// Function to find the result of
// alternatively adding and subtracting
// elements in the range [L< R]
static int findResultUtil(int prefixArray[],
int L, int R)
{
int result;
// Case 1 : when L is zero
if (L == 0)
{
result = prefixArray[R];
}
// Case 2 : When L is non zero
else
{
result = prefixArray[R] -
prefixArray[L - 1];
}
// If L is odd means range starts from
// odd position multiply result by -1
if (L % 2 == 1)
{
result = result * (-1);
}
// Return the final result
return result;
}
// Function to find the sum of all
// alternative add and subtract
// between ranges [L, R]
static void findResult(int arr[], int n,
Query q[], int m)
{
// Declare prefix array
int []prefixArray = new int[n];
// Function Call to fill prefix arr[]
fillPrefixArray(arr, n, prefixArray);
// Iterate for each query
for (int i = 0; i < m; i++)
{
System.out.print(findResultUtil(
prefixArray, q[i].L,
q[i].R) + " ");
}
}
// Driver Code
public static void main(String[] args)
{
// Given array
int arr[] = { 10, 13, 15, 2, 45,
31, 22, 3, 27 };
int n = arr.length;
// Given Queries
Query q[] = {new Query( 2, 5 ), new Query( 6, 8 ),
new Query( 1, 7 ), new Query( 4, 8 ),
new Query( 0, 5 )};
int m = q.length;
// Function Call
findResult(arr, n, q, m);
}
}
// This code is contributed by PrinciRaj1992
Python3
# Python program for the above approach # Structure to represent a query class Query: def __init__(self,l,r): self.L = l self.R = r # This function fills the Prefix Array def fillPrefixArray(arr, n, prefixArray): # Initialise the prefix array prefixArray[0] = arr[0] # Iterate all the element of arr[] # and update the prefix array for i in range(1,n): # If n is even then, add the # previous value of prefix array # with the current value of arr if (i % 2 == 0): prefixArray[i] = prefixArray[i - 1] + arr[i] # if n is odd, then subtract # the previous value of prefix # Array from current value else: prefixArray[i] = prefixArray[i - 1] - arr[i] # Function to find the result of # alternatively adding and subtracting # elements in the range [L< R] def findResultUtil(prefixArray, L, R): # Case 1 : when L is zero if (L == 0): result = prefixArray[R] # Case 2 : When L is non zero else: result = prefixArray[R] - prefixArray[L - 1] # If L is odd means range starts from # odd position multiply result by -1 if (L % 2 == 1): result = result * (-1) # Return the final result return result # Function to find the sum of all # alternative add and subtract # between ranges [L, R] def findResult(arr, n, q, m): # Declare prefix array prefixArray = [0 for i in range(n)] # Function Call to fill prefix arr[] fillPrefixArray(arr, n, prefixArray) # Iterate for each query for i in range(m): print(findResultUtil(prefixArray, q[i].L,q[i].R),end = " ") # Driver Code # Given array arr = [ 10, 13, 15, 2, 45, 31, 22, 3, 27 ] n = len(arr) # Given Queries q = [ Query(2, 5), Query(6, 8), Query(1, 7), Query(4, 8), Query(0, 5)] m = len(q) # Function Call findResult(arr, n, q, m) # This code is contributed by shinjanpatra
C#
// C# program for the above approach
using System;
class GFG{
// Structure to represent a query
class Query
{
public int L, R;
public Query(int l, int r)
{
L = l;
R = r;
}
};
// This function fills the Prefix Array
static void fillPrefixArray(int []arr, int n,
int []prefixArray)
{
// Initialise the prefix array
prefixArray[0] = arr[0];
// Iterate all the element of []arr
// and update the prefix array
for (int i = 1; i < n; i++)
{
// If n is even then, add the
// previous value of prefix array
// with the current value of arr
if (i % 2 == 0)
{
prefixArray[i] = prefixArray[i - 1] +
arr[i];
}
// if n is odd, then subtract
// the previous value of prefix
// Array from current value
else
{
prefixArray[i] = prefixArray[i - 1] -
arr[i];
}
}
}
// Function to find the result of
// alternatively adding and subtracting
// elements in the range [L< R]
static int findResultUtil(int []prefixArray,
int L, int R)
{
int result;
// Case 1 : when L is zero
if (L == 0)
{
result = prefixArray[R];
}
// Case 2 : When L is non zero
else
{
result = prefixArray[R] -
prefixArray[L - 1];
}
// If L is odd means range starts from
// odd position multiply result by -1
if (L % 2 == 1)
{
result = result * (-1);
}
// Return the readonly result
return result;
}
// Function to find the sum of all
// alternative add and subtract
// between ranges [L, R]
static void findResult(int []arr, int n,
Query []q, int m)
{
// Declare prefix array
int []prefixArray = new int[n];
// Function Call to fill prefix []arr
fillPrefixArray(arr, n, prefixArray);
// Iterate for each query
for (int i = 0; i < m; i++)
{
Console.Write(findResultUtil(
prefixArray, q[i].L,
q[i].R) + " ");
}
}
// Driver Code
public static void Main(String[] args)
{
// Given array
int []arr = { 10, 13, 15, 2, 45,
31, 22, 3, 27 };
int n = arr.Length;
// Given Queries
Query []q = {new Query( 2, 5 ), new Query( 6, 8 ),
new Query( 1, 7 ), new Query( 4, 8 ),
new Query( 0, 5 )};
int m = q.Length;
// Function Call
findResult(arr, n, q, m);
}
}
// This code is contributed by Rohit_ranjan
Javascript
<script>
// Javascript program for the above approach
// Structure to represent a query
class Query
{
constructor(l, r)
{
this.L = l;
this.R = r;
}
}
// This function fills the Prefix Array
function fillPrefixArray(arr, n, prefixArray)
{
// Initialise the prefix array
prefixArray[0] = arr[0];
// Iterate all the element of arr[]
// and update the prefix array
for(let i = 1; i < n; i++)
{
// If n is even then, add the
// previous value of prefix array
// with the current value of arr
if (i % 2 == 0)
{
prefixArray[i] = prefixArray[i - 1] +
arr[i];
}
// if n is odd, then subtract
// the previous value of prefix
// Array from current value
else
{
prefixArray[i] = prefixArray[i - 1] -
arr[i];
}
}
}
// Function to find the result of
// alternatively adding and subtracting
// elements in the range [L< R]
function findResultUtil(prefixArray, L, R)
{
let result;
// Case 1 : when L is zero
if (L == 0)
{
result = prefixArray[R];
}
// Case 2 : When L is non zero
else
{
result = prefixArray[R] -
prefixArray[L - 1];
}
// If L is odd means range starts from
// odd position multiply result by -1
if (L % 2 == 1)
{
result = result * (-1);
}
// Return the final result
return result;
}
// Function to find the sum of all
// alternative add and subtract
// between ranges [L, R]
function findResult(arr, n, q, m)
{
// Declare prefix array
let prefixArray = new Array(n);
// Function Call to fill prefix arr[]
fillPrefixArray(arr, n, prefixArray);
// Iterate for each query
for(let i = 0; i < m; i++)
{
document.write(findResultUtil(
prefixArray, q[i].L,
q[i].R) + " ");
}
}
// Driver Code
// Given array
let arr = [ 10, 13, 15, 2, 45,
31, 22, 3, 27 ];
let n = arr.length;
// Given Queries
let q = [ new Query(2, 5), new Query(6, 8),
new Query(1, 7), new Query(4, 8),
new Query(0, 5)];
let m = q.length;
// Function Call
findResult(arr, n, q, m);
// This code is contributed by unknown2108
</script>
Producción:
27 46 -33 60 24
Complejidad temporal: O(N + Q)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por rahulrai27 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA