Given an array arr[] which is the resultant array when a number of queries are performed on the original array. The queries are of the form [l, r, x] where l is the starting index in the array, r is the ending index in the array and x is the integer elements that have to be added to all the elements in the index range [l, r]. The task is to find the original array.
Examples:
Input: arr[] = {5, 7, 8}, l[] = {0}, r[] = {1}, x[] = {2}
Output: 3 5 8
If query [0, 1, 2] is performed on the array {3, 5, 8}
The resultant array will be {5, 7, 8}Input: arr[] = {20, 30, 20, 70, 100},
l[] = {0, 1, 3},
r[] = {2, 4, 4},
x[] = {10, 20, 30}
Output: 10 0 -10 20 50
Naive Approach: For each range starting from l to r subtract the corresponding x to get the initial array.
Algorithm
1)Define the initial array arr and its size n.
2)Define the ranges l, r, and the values x for decrementing the elements in those ranges.
3)Define the number of queries q.
4)For each query j from 0 to q-1:
For each index i from l[j] to r[j], decrement the corresponding element in the array arr by the value x[j].
5)Print the elements of the final array arr.
Below is the implementation of the approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;// Utility function to print the contents of an arrayvoid printArr(int arr[], int n){ for (int i = 0; i < n; i++) { cout << arr[i] << " "; }}// Function to find the original arrayvoid 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 codeint 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 approachimport java.util.*;class GFG{// Utility function to print the contents of an arraystatic void printArr(int arr[], int n){ for (int i = 0; i < n; i++) { System.out.print(arr[i]+" "); }}// Function to find the original arraystatic 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 codepublic 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 approachimport math as mt# Utility function to print the # contents of an arraydef printArr(arr, n): for i in range(n): print(arr[i], end = " ")# Function to find the original arraydef 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 arrayarr = [20, 30, 20, 70, 100] # Size of the arrayn = len(arr)# Queriesl = [0, 1, 3] r = [ 2, 4, 4] x = [ 10, 20, 30 ]# Number of queriesq = len(l)findOrgArr(arr, l, r, x, n, q)# This code is contributed by # mohit kumar 29 |
C#
// C# implementation of the approachusing System;class GFG{// Utility function to print the // contents of an arraystatic void printArr(int[] arr, int n){ for (int i = 0; i < n; i++) { Console.Write(arr[i] + " "); }}// Function to find the original arraystatic 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 codepublic 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 arrayfunction printArr(&$arr, $n){ for ($i = 0; $i < $n; $i++) { echo($arr[$i]); echo(" "); }}// Function to find the original arrayfunction 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 arrayfunction printArr(arr,n){ for (let i = 0; i < n; i++) { document.write(arr[i]+" "); }}// Function to find the original arrayfunction 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 arraylet arr = [ 20, 30, 20, 70, 100 ];// Size of the arraylet n = arr.length;// Querieslet l = [ 0, 1, 3 ];let r = [ 2, 4, 4 ];let x = [ 10, 20, 30 ];// Number of querieslet q = l.length;findOrgArr(arr, l, r, x, n, q); // This code is contributed by patel2127</script> |
Output
10 0 -10 20 50
Complexity Analysis:
- Time Complexity: O(n2)
- Auxiliary Space: O(1)
Efficient Approach:
Follow the following steps to reach the initial array:
- Take an array b[] of the size of the given array and initialize all of its elements with 0.
- In array b[], for every query update b[l] = b[l] – x and b[r + 1] = b[r + 1] + x if r + 1 < n. This is because x will cancel out the effect of -x when performed the prefix sum.
- Take the prefix sum of array b[], and add it to the given array which will produce the initial array.
Implementation:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;// Utility function to print the contents of an arrayvoid printArr(int arr[], int n){ for (int i = 0; i < n; i++) { cout << arr[i] << " "; }}// Function to find the original arrayvoid 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 codeint 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 arraydef printArr(arr, n): for i in range(n): print(arr[i], end = " ")# Function to find the original arraydef 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 codearr = [20, 30, 20, 70, 100]# Size of the arrayn = len(arr)# Queriesl = [0, 1, 3 ]r = [2, 4, 4 ]x = [10, 20, 30 ]# Number of queriesq = 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 |
Javascript
<script> // Javascript implementation of above approach // Utility function to print the contents of an array function printArr(arr, n) { console.log(arr.join(' ')) ; } // Function to find the original array function findOrgArr(arr,l,r,x,n,q) { let b = new Array(n) ; for (let i = 0; i < n; i++) b[i] = 0 ; for (let 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 (let i = 1; i < n; i++) // Prefix sum of array b b[i] = b[i - 1] + b[i]; // Update the original array for (let i = 0; i < n; i++) arr[i] = arr[i] + b[i]; 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 ; // Function call findOrgArr(arr, l, r, x, n, q); // This code is contributed by aarohirai2616. </script> |
Output
10 0 -10 20 50
Complexity Analysis:
- Time Complexity: O(n)
- Auxiliary Space: O(n)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
