Encuentre la array inicial de la array dada después de las consultas de suma de rango

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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *