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 updatevoid update(int l, int r, int x, int mul[], int div[]){ mul[l] *= x; div[r + 1] *= x;}// Prints updated Arrayvoid 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 approachclass 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 updatestatic void update(int l, int r, int x, int mul[], int div[]){ mul[l] *= x; div[r + 1] *= x;}// Prints updated Arraystatic 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 updatedef update(l, r, x, mul, div): mul[l] *= x; div[r + 1] *= x;# Prints updated Arraydef 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 approachusing 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 updatestatic void update(int l, int r, int x, int []mul, int []div){ mul[l] *= x; div[r + 1] *= x;}// Prints updated Arraystatic 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> |
Output:
100 1000 800 800
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!
… [Trackback]
[…] Here you will find 83805 additional Information on that Topic: geeksforgeeks.org/multiplication-on-array-range-update-query-in-o-1/ […]
… [Trackback]
[…] Find More to that Topic: geeksforgeeks.org/multiplication-on-array-range-update-query-in-o-1/ […]
… [Trackback]
[…] Read More on that Topic: geeksforgeeks.org/multiplication-on-array-range-update-query-in-o-1/ […]