Dada una array arr[] , que es la array resultante cuando se realizan varias consultas en la array original. Las consultas son de la forma [l, r, x] donde l es el índice inicial en la array, r es el índice final en la array y x son los elementos enteros que deben agregarse a todos los elementos en el rango del índice [l, r] . La tarea es encontrar la array original.
Ejemplos:
Entrada: arr[] = {5, 7, 8}, l[] = {0}, r[] = {1}, x[] = {2} Salida: 3 5 8 Si consulta [
0 ,
1, 2 ] se realiza en la array {3, 5, 8}
La array resultante será {5, 7, 8}
Entrada: arr[] = {20, 30, 20, 70, 100},
l[] = {0, 1, 3},
r[] = {2, 4, 4},
x[] = {10, 20, 30}
Salida: 10 0 -10 20 50
Enfoque ingenuo: para cada rango que comienza de l a r, reste la x correspondiente para obtener la array inicial.
A continuación se muestra la implementación del enfoque:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Utility function to print the contents of an array
void printArr(int arr[], int n)
{
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
}
// Function to find the original array
void findOrgArr(int arr[], int l[], int r[], int x[],
int n, int q)
{
for (int j = 0; j < q; j++) {
for (int i = l[j]; i <= r[j]; i++) {
// Decrement elements between
// l[j] and r[j] by x[j]
arr[i] = arr[i] - x[j];
}
}
printArr(arr, n);
}
// Driver code
int main()
{
// Final array
int arr[] = { 20, 30, 20, 70, 100 };
// Size of the array
int n = sizeof(arr) / sizeof(arr[0]);
// Queries
int l[] = { 0, 1, 3 };
int r[] = { 2, 4, 4 };
int x[] = { 10, 20, 30 };
// Number of queries
int q = sizeof(l) / sizeof(l[0]);
findOrgArr(arr, l, r, x, n, q);
return 0;
}
Java
// Java implementation of the approach
import java.util.*;
class GFG
{
// Utility function to print the contents of an array
static void printArr(int arr[], int n)
{
for (int i = 0; i < n; i++) {
System.out.print(arr[i]+" ");
}
}
// Function to find the original array
static void findOrgArr(int arr[], int l[], int r[], int x[],
int n, int q)
{
for (int j = 0; j < q; j++) {
for (int i = l[j]; i <= r[j]; i++) {
// Decrement elements between
// l[j] and r[j] by x[j]
arr[i] = arr[i] - x[j];
}
}
printArr(arr, n);
}
// Driver code
public static void main(String args[])
{
// Final array
int arr[] = { 20, 30, 20, 70, 100 };
// Size of the array
int n = arr.length;
// Queries
int l[] = { 0, 1, 3 };
int r[] = { 2, 4, 4 };
int x[] = { 10, 20, 30 };
// Number of queries
int q = l.length;
findOrgArr(arr, l, r, x, n, q);
}
}
// This code is contributed by
// Shashank_Sharma
Python3
# Python3 implementation of the approach import math as mt # Utility function to print the # contents of an array def printArr(arr, n): for i in range(n): print(arr[i], end = " ") # Function to find the original array def findOrgArr(arr, l, r, x, n, q): for j in range(q): for i in range(l[j], r[j] + 1): # Decrement elements between # l[j] and r[j] by x[j] arr[i] = arr[i] - x[j] printArr(arr, n) # Driver code # Final array arr = [20, 30, 20, 70, 100] # Size of the array n = len(arr) # Queries l = [0, 1, 3] r = [ 2, 4, 4] x = [ 10, 20, 30 ] # Number of queries q = len(l) findOrgArr(arr, l, r, x, n, q) # This code is contributed by # mohit kumar 29
C#
// C# implementation of the approach
using System;
class GFG
{
// Utility function to print the
// contents of an array
static void printArr(int[] arr, int n)
{
for (int i = 0; i < n; i++)
{
Console.Write(arr[i] + " ");
}
}
// Function to find the original array
static void findOrgArr(int[] arr, int[] l,
int[] r, int[] x,
int n, int q)
{
for (int j = 0; j < q; j++)
{
for (int i = l[j]; i <= r[j]; i++)
{
// Decrement elements between
// l[j] and r[j] by x[j]
arr[i] = arr[i] - x[j];
}
}
printArr(arr, n);
}
// Driver code
public static void Main()
{
// Final array
int[] arr = { 20, 30, 20, 70, 100 };
// Size of the array
int n = arr.Length;
// Queries
int[] l = { 0, 1, 3 };
int[] r = { 2, 4, 4 };
int[] x = { 10, 20, 30 };
// Number of queries
int q = l.Length;
findOrgArr(arr, l, r, x, n, q);
}
}
// This code is contributed by
// Akanksha Rai
PHP
<?php
// PHP implementation of the approach
// Utility function to print the contents
// of an array
function printArr(&$arr, $n)
{
for ($i = 0; $i < $n; $i++)
{
echo($arr[$i]);
echo(" ");
}
}
// Function to find the original array
function findOrgArr(&$arr, &$l, &$r,
&$x, $n, $q)
{
for ($j = 0; $j < $q; $j++)
{
for ($i = $l[$j]; $i <= $r[$j]; $i++)
{
// Decrement elements between
// l[j] and r[j] by x[j]
$arr[$i] = $arr[$i] - $x[$j];
}
}
printArr($arr, $n);
}
// Driver code
// Final array
$arr = array(20, 30, 20, 70, 100);
// Size of the array
$n = sizeof($arr);
// Queries
$l = array(0, 1, 3 );
$r = array( 2, 4, 4 );
$x = array(10, 20, 30 );
// Number of queries
$q = sizeof($l);
findOrgArr($arr, $l, $r, $x, $n, $q);
// This code is contributed by Shivi_Aggarwal
?>
Javascript
<script>
// Javascript implementation of the approach
// Utility function to print the contents of an array
function printArr(arr,n)
{
for (let i = 0; i < n; i++) {
document.write(arr[i]+" ");
}
}
// Function to find the original array
function findOrgArr(arr,l,r,x,n,q)
{
for (let j = 0; j < q; j++) {
for (let i = l[j]; i <= r[j]; i++) {
// Decrement elements between
// l[j] and r[j] by x[j]
arr[i] = arr[i] - x[j];
}
}
printArr(arr, n);
}
// Driver code
// Final array
let arr = [ 20, 30, 20, 70, 100 ];
// Size of the array
let n = arr.length;
// Queries
let l = [ 0, 1, 3 ];
let r = [ 2, 4, 4 ];
let x = [ 10, 20, 30 ];
// Number of queries
let q = l.length;
findOrgArr(arr, l, r, x, n, q);
// This code is contributed by patel2127
</script>
Producción:
10 0 -10 20 50
Complejidad de tiempo: O(n 2 )
Enfoque eficiente: siga los siguientes pasos para llegar a la array inicial:
- Tome una array b[] del tamaño de la array dada e inicialice todos sus elementos con 0 .
- En la array b[] , para cada consulta actualice b[l] = b[l] – x y b[r + 1] = b[r + 1] + x si r + 1 < n . Esto se debe a que x cancelará el efecto de -x cuando se realice la suma del prefijo.
- Tome la suma del prefijo de la array b[] y agréguela a la array dada que producirá la array inicial.
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Utility function to print the contents of an array
void printArr(int arr[], int n)
{
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
}
// Function to find the original array
void findOrgArr(int arr[], int l[], int r[], int x[],
int n, int q)
{
int b[n] = { 0 };
for (int i = 0; i < q; i++) {
// Decrement the element at l[i]th index by -x
b[l[i]] += -x[i];
// Increment the element at (r[i] + 1)th index
// by x if (r[i] + 1) is a valid index
if (r[i] + 1 < n)
b[r[i] + 1] += x[i];
}
for (int i = 1; i < n; i++)
// Prefix sum of array b
b[i] = b[i - 1] + b[i];
// Update the original array
for (int i = 0; i < n; i++)
arr[i] = arr[i] + b[i];
printArr(arr, n);
}
// Driver code
int main()
{
// Final array
int arr[] = { 20, 30, 20, 70, 100 };
// Size of the array
int n = sizeof(arr) / sizeof(arr[0]);
// Queries
int l[] = { 0, 1, 3 };
int r[] = { 2, 4, 4 };
int x[] = { 10, 20, 30 };
// Number of queries
int q = sizeof(l) / sizeof(l[0]);
findOrgArr(arr, l, r, x, n, q);
return 0;
}
Java
// Java implementation of above approach
class GFG{
// Utility function to print the contents of an array
static void printArr(int arr[], int n)
{
for (int i = 0; i < n; i++)
{
System.out.print(arr[i] + " ") ;
}
}
// Function to find the original array
static void findOrgArr(int arr[], int l[], int r[], int x[],
int n, int q)
{
int b[] = new int[n] ;
for (int i = 0; i < q; i++)
b[i] = 0 ;
for (int i = 0; i < q; i++)
{
// Decrement the element at l[i]th index by -x
b[l[i]] += -x[i];
// Increment the element at (r[i] + 1)th index
// by x if (r[i] + 1) is a valid index
if (r[i] + 1 < n)
b[r[i] + 1] += x[i];
}
for (int i = 1; i < n; i++)
// Prefix sum of array b
b[i] = b[i - 1] + b[i];
// Update the original array
for (int i = 0; i < n; i++)
arr[i] = arr[i] + b[i];
printArr(arr, n);
}
// Driver code
public static void main(String []args)
{
// Final array
int arr[] = { 20, 30, 20, 70, 100 };
// Size of the array
int n = arr.length ;
// Queries
int l[] = { 0, 1, 3 };
int r[] = { 2, 4, 4 };
int x[] = { 10, 20, 30 };
// Number of queries
int q = l.length ;
findOrgArr(arr, l, r, x, n, q);
}
}
// This code is contributed by aishwarya.27
Python3
# Python3 implementation of the approach # Utility function to print the contents # of an array def printArr(arr, n): for i in range(n): print(arr[i], end = " ") # Function to find the original array def findOrgArr(arr, l, r, x, n, q): b = [0 for i in range(n)] for i in range(q): # Decrement the element at l[i]th # index by -x b[l[i]] += -x[i] # Increment the element at (r[i] + 1)th # index by x if (r[i] + 1) is a valid index if (r[i] + 1 < n): b[r[i] + 1] += x[i] for i in range(n): # Prefix sum of array b b[i] = b[i - 1] + b[i] # Update the original array for i in range(n): arr[i] = arr[i] + b[i] printArr(arr, n) # Driver code arr = [20, 30, 20, 70, 100] # Size of the array n = len(arr) # Queries l = [0, 1, 3 ] r = [2, 4, 4 ] x = [10, 20, 30 ] # Number of queries q = len(l) findOrgArr(arr, l, r, x, n, q) # This code Is contributed by # Mohit kumar 29
C#
// C# implementation of above approach
using System;
class GFG
{
// Utility function to print the
// contents of an array
static void printArr(int[] arr, int n)
{
for (int i = 0; i < n; i++)
{
Console.Write(arr[i] + " ");
}
}
// Function to find the original array
static void findOrgArr(int[] arr, int[] l,
int[] r, int[] x,
int n, int q)
{
int[] b = new int[n];
for (int i = 0; i < q; i++)
b[i] = 0 ;
for (int i = 0; i < q; i++)
{
// Decrement the element at l[i]th
// index by -x
b[l[i]] += -x[i];
// Increment the element at (r[i] + 1)th
// index by x if (r[i] + 1) is a valid index
if (r[i] + 1 < n)
b[r[i] + 1] += x[i];
}
for (int i = 1; i < n; i++)
// Prefix sum of array b
b[i] = b[i - 1] + b[i];
// Update the original array
for (int i = 0; i < n; i++)
arr[i] = arr[i] + b[i];
printArr(arr, n);
}
// Driver code
public static void Main()
{
// Final array
int[] arr = { 20, 30, 20, 70, 100 };
// Size of the array
int n = arr.Length;
// Queries
int[] l = { 0, 1, 3 };
int[] r = { 2, 4, 4 };
int[] x = { 10, 20, 30 };
// Number of queries
int q = l.Length;
findOrgArr(arr, l, r, x, n, q);
}
}
// This code is contributed
// by Akanksha Rai
Producción:
10 0 -10 20 50
Complejidad de tiempo: O(n)
Publicación traducida automáticamente
Artículo escrito por ranjanmonisha233 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA