Consider an array A[] of integers and the following two types of queries.
- update(l, r, x): multiply x to all values from A[l] to A[r] (both inclusive).
- printArray(): Prints the current modified array.
Examples:
Input: A[] = {1, 1, 1, 1, 1, 1, 1, 1, 1, 1} update(0, 2, 2) update(1, 4, 3) print() update(4, 8, 5) print() Output: 2 6 6 3 15 5 5 5 5 1 Explanation: The query update(0, 2, 2) multiply 2 to A[0], A[1] and A[2]. After update, A[] becomes {2, 2, 2, 1, 1, 1, 1, 1, 1, 1} Query update(1, 4, 3) multiply 3 to A[1], A[2], A[3] and A[4]. After update, A[] becomes {2, 6, 6, 3, 3, 1, 1, 1, 1, 1}. Query update(4, 8, 5) multiply 5, A[4] to A[8]. After update, A[] becomes {2, 6, 6, 3, 15, 5, 5, 5, 5, 1}. Input: A[] = {10, 5, 20, 40} update(0, 1, 10) update(1, 3, 20) update(2, 2, 2) print() Output: 100 1000 800 800
Approach:
A simple solution is to do the following:
- update(l, r, x): Run a loop from l to r and multiply x to all elements from A[l] to A[r].
- print(): Simply print A[].
Time complexities of both the above operations is O(n).
Efficient Approach:
An efficient solution is to use two arrays, one for multiplication and another for the division. mul[] and div[] respectively.
- Multiply x to mul[l] and Multiply x to div[r+1]
- Take prefix multiplication of mul array mul[i] = (mul[i] * mul[i-1] ) / div[i]
- printArray(): Do A[0] = mul[0] and print it. For rest of the elements do A[i] = (A[i]*mul[i])
Below is the implementation of above approach:
C++
// C++ program for // the above approach #include <bits/stdc++.h> using namespace std; // Creates a mul[] array for A[] and returns // it after filling initial values. void initialize( int mul[], int div [], int size) { for ( int i = 1; i < size; i++) { mul[i] = (mul[i] * mul[i - 1]) / div [i]; } } // Does range update void update( int l, int r, int x, int mul[], int div []) { mul[l] *= x; div [r + 1] *= x; } // Prints updated Array void printArray( int ar[], int mul[], int div [], int n) { for ( int i = 0; i < n; i++) { ar[i] = ar[i] * mul[i]; cout << ar[i] << " " ; } } // Driver code; int main() { // Array to be updated int ar[] = { 10, 5, 20, 40 }; int n = sizeof (ar) / sizeof (ar[0]); // Create and fill mul and div Array int mul[n + 1], div [n + 1]; for ( int i = 0; i < n + 1; i++) { mul[i] = div [i] = 1; } update(0, 1, 10, mul, div ); update(1, 3, 20, mul, div ); update(2, 2, 2, mul, div ); initialize(mul, div , n + 1); printArray(ar, mul, div , n); return 0; } |
Java
// Java implementation of the approach class GFG { // Creates a mul[] array for A[] and returns // it after filling initial values. static void initialize( int mul[], int div[], int size) { for ( int i = 1 ; i < size; i++) { mul[i] = (mul[i] * mul[i - 1 ]) / div[i]; } } // Does range update static void update( int l, int r, int x, int mul[], int div[]) { mul[l] *= x; div[r + 1 ] *= x; } // Prints updated Array static void printArray( int ar[], int mul[], int div[], int n) { for ( int i = 0 ; i < n; i++) { ar[i] = ar[i] * mul[i]; System.out.print(ar[i] + " " ); } } // Driver code; public static void main(String[] args) { // Array to be updated int ar[] = { 10 , 5 , 20 , 40 }; int n = ar.length; // Create and fill mul and div Array int []mul = new int [n + 1 ]; int []div = new int [n + 1 ]; for ( int i = 0 ; i < n + 1 ; i++) { mul[i] = div[i] = 1 ; } update( 0 , 1 , 10 , mul, div); update( 1 , 3 , 20 , mul, div); update( 2 , 2 , 2 , mul, div); initialize(mul, div, n + 1 ); printArray(ar, mul, div, n); } } // This code is contributed by Rajput-Ji |
Python3
# Python3 program for the above approach # Creates a mul[] array for A[] and returns # it after filling initial values. def initialize(mul, div, size): for i in range ( 1 , size): mul[i] = (mul[i] * mul[i - 1 ]) / div[i]; # Does range update def update(l, r, x, mul, div): mul[l] * = x; div[r + 1 ] * = x; # Prints updated Array def printArray(ar, mul, div, n): for i in range (n): ar[i] = ar[i] * mul[i]; print ( int (ar[i]), end = " " ); # Driver code; if __name__ = = '__main__' : # Array to be updated ar = [ 10 , 5 , 20 , 40 ]; n = len (ar); # Create and fill mul and div Array mul = [ 0 ] * (n + 1 ); div = [ 0 ] * (n + 1 ); for i in range (n + 1 ): mul[i] = div[i] = 1 ; update( 0 , 1 , 10 , mul, div); update( 1 , 3 , 20 , mul, div); update( 2 , 2 , 2 , mul, div); initialize(mul, div, n + 1 ); printArray(ar, mul, div, n); # This code is contributed by Rajput-Ji |
C#
// C# implementation of the approach using System; class GFG { // Creates a mul[] array for A[] and returns // it after filling initial values. static void initialize( int []mul, int []div, int size) { for ( int i = 1; i < size; i++) { mul[i] = (mul[i] * mul[i - 1]) / div[i]; } } // Does range update static void update( int l, int r, int x, int []mul, int []div) { mul[l] *= x; div[r + 1] *= x; } // Prints updated Array static void printArray( int []ar, int []mul, int []div, int n) { for ( int i = 0; i < n; i++) { ar[i] = ar[i] * mul[i]; Console.Write(ar[i] + " " ); } } // Driver code; public static void Main(String[] args) { // Array to be updated int []ar = { 10, 5, 20, 40 }; int n = ar.Length; // Create and fill mul and div Array int []mul = new int [n + 1]; int []div = new int [n + 1]; for ( int i = 0; i < n + 1; i++) { mul[i] = div[i] = 1; } update(0, 1, 10, mul, div); update(1, 3, 20, mul, div); update(2, 2, 2, mul, div); initialize(mul, div, n + 1); printArray(ar, mul, div, n); } } // This code is contributed by Rajput-Ji |
Javascript
<script> // Javascript implementation of the approach // Creates a mul array for A and returns // it after filling initial values. function initialize(mul , div , size) { for (i = 1; i < size; i++) { mul[i] = (mul[i] * mul[i - 1]) / div[i]; } } // Does range update function update(l , r , x , mul , div) { mul[l] *= x; div[r + 1] *= x; } // Prints updated Array function printArray(ar , mul , div , n) { for (i = 0; i < n; i++) { ar[i] = ar[i] * mul[i]; document.write(ar[i] + " " ); } } // Driver code; // Array to be updated var ar = [ 10, 5, 20, 40 ]; var n = ar.length; // Create and fill mul and div Array var mul = Array(n + 1).fill(0); var div = Array(n + 1).fill(0); for (i = 0; i < n + 1; i++) { mul[i] = div[i] = 1; } update(0, 1, 10, mul, div); update(1, 3, 20, mul, div); update(2, 2, 2, mul, div); initialize(mul, div, n + 1); printArray(ar, mul, div, n); // This code contributed by Rajput-Ji </script> |
100 1000 800 800
Time Complexity: O(n)
Auxiliary Space: O(n)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!