Multiplication on Array : Range update query in O(1)

0 0 5 minutes read

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>

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 zambiatek!