Given an array arr[] consisting of N integers and an array Q[] of M pairs representing a query of type {X, Y}, the task is to perform queries of the following type:
- Query(0, X): Add integer X to every array elements.
- Query(1, Y): Multiply each array element by Y.
- Query(2, i): Print the value at index i.
Examples:
Input: arr[] = {5, 1, 2, 3, 9}, Q[][] = {{0, 5}, {2, 4}, {1, 4}, {0, 2}, {2, 3}}
Output: 14 34
Explanation:
Below are the results after performing each query:
- Query(0, 5): Adding 5 to every array elements, modifies the array as arr[] = {10, 6, 7, 8, 14}.
- Query(2, 4): Print the array element at index 4, i.e., arr[4] = 14.
- Query(1, 4): Multiplying every array elements with 4, modifies the array as arr[] = {40, 24, 28, 32, 56}
- Query(0, 2): Adding 2 to every array elements, modifies the array as arr[] = {42, 26, 30, 34, 58}
- Query(2, 3): Print the element at index 4, i.e., arr[3] = 34.
Input: arr[] = {3, 1, 23, 45, 100}, Q[][] = {{1, 2}, {0, 10}, {2, 3}, {1, 5}, {2, 4}}
Output: 100 1050
Naive Approach: The simplest approach is to solve the given problem is to perform each query by traversing the given array and print the result accordingly for each query.
Time Complexity: O(N * M)
Auxiliary Space: O(1)
Efficient Approach: The above approach can be optimized based on the following observations:
- Suppose A is an element and the following operation is performed:
- Adding a1 to A, then the value of A becomes A = A + a1.
- Multiply A by b1, then the value of A becomes A = b1 * A + b1 * a1.
- Add a2 to A, then the value of A becomes A = b1 * A + b1 * a1 + a2.
- Multiply A by b2, then the value of A becomes, A = b1 * b2 * A + b1 * b2 * a1 + a2 * b2
- Suppose Mul is the multiplication of all the integers of the query of type 1 and Add stores the value of all the query of type 0, and type 1 performed in the given order starting as 0. Then it can be observed from above that any array element arr[i] modifies to (arr[i] * Mul + Add).
Follow the steps below to solve the problem:
- Initialize two variables, say Mul as 1 and Add as 0, stores the multiplication of all the integers in the query of type 2 and stores the value got after performing the query of type 1 and 2 in the given order on a number 0.
- Traverse the given array of queries Q[][2] and perform the following steps:
- If Q[i][0] is 0, then increment the value of Add by Q[i][1].
- Otherwise, if the value of Q[i][0] is 1 then multiply Mul and Add by Q[i][1].
- Otherwise, print the value (arr[Q[i][1]] * Mul + Add) as the result for the query of type 2.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to modify the array// by performing given queriesvoid Query(int arr[], int N, vector<vector<int> > Q){ // Stores the multiplication // of all integers of type 1 int mul = 1; // Stores the value obtained after // performing queries of type 1 & 2 int add = 0; // Iterate over the queries for (int i = 0; i < Q.size(); i++) { // Query of type 0 if (Q[i][0] == 0) { // Update the value of add add = add + Q[i][1]; } // Query of type 1 else if (Q[i][0] == 1) { // Update the value of mul mul = mul * Q[i][1]; // Update the value of add add = add * Q[i][1]; } // Otherwise else { // Store the element at index Q[i][1] int ans = arr[Q[i][1]] * mul + add; // Print the result for // the current query cout << ans << " "; } }}// Driver Codeint main(){ int arr[] = { 3, 1, 23, 45, 100 }; int N = sizeof(arr) / sizeof(arr[0]); vector<vector<int> > Q = { { 1, 2 }, { 0, 10 }, { 2, 3 }, { 1, 5 }, { 2, 4 } }; Query(arr, N, Q); return 0;} |
Java
// Java program for the above approachimport java.io.*;import java.lang.*;import java.util.*;public class GFG{ // Function to modify the array // by performing given queries static void Query(int arr[], int N, int Q[][]) { // Stores the multiplication // of all integers of type 1 int mul = 1; // Stores the value obtained after // performing queries of type 1 & 2 int add = 0; // Iterate over the queries for (int i = 0; i < Q.length; i++) { // Query of type 0 if (Q[i][0] == 0) { // Update the value of add add = add + Q[i][1]; } // Query of type 1 else if (Q[i][0] == 1) { // Update the value of mul mul = mul * Q[i][1]; // Update the value of add add = add * Q[i][1]; } // Otherwise else { // Store the element at index Q[i][1] int ans = arr[Q[i][1]] * mul + add; // Print the result for // the current query System.out.print(ans + " "); } } } // Driver Code public static void main(String[] args) { int arr[] = { 3, 1, 23, 45, 100 }; int N = arr.length; int Q[][] = { { 1, 2 }, { 0, 10 }, { 2, 3 }, { 1, 5 }, { 2, 4 } }; Query(arr, N, Q); }}// This code is contributed by Kingash. |
Python3
# Python3 program for the above approach# Function to modify the array# by performing given queriesdef Query(arr, N, Q): # Stores the multiplication # of all integers of type 1 mul = 1 # Stores the value obtained after # performing queries of type 1 & 2 add = 0 # Iterate over the queries for i in range(len(Q)): # Query of type 0 if (Q[i][0] == 0): # Update the value of add add = add + Q[i][1] # Query of type 1 elif (Q[i][0] == 1): # Update the value of mul mul = mul * Q[i][1] # Update the value of add add = add * Q[i][1] # Otherwise else: # Store the element at index Q[i][1] ans = arr[Q[i][1]] * mul + add # Print result for # the current query print(ans,end=" ")# Driver Codeif __name__ == '__main__': arr = [3, 1, 23, 45, 100] N = len(arr) Q = [ [ 1, 2 ], [ 0, 10 ], [ 2, 3 ], [ 1, 5 ], [ 2, 4 ] ] Query(arr, N, Q)# This code is contributed by mohit kumar 29. |
C#
// C# program for the above approachusing System;class GFG { // Function to modify the array // by performing given queries static void Query(int[] arr, int N, int[, ] Q) { // Stores the multiplication // of all integers of type 1 int mul = 1; // Stores the value obtained after // performing queries of type 1 & 2 int add = 0; // Iterate over the queries for (int i = 0; i < Q.GetLength(0); i++) { // Query of type 0 if (Q[i, 0] == 0) { // Update the value of add add = add + Q[i, 1]; } // Query of type 1 else if (Q[i, 0] == 1) { // Update the value of mul mul = mul * Q[i, 1]; // Update the value of add add = add * Q[i, 1]; } // Otherwise else { // Store the element at index Q[i][1] int ans = arr[Q[i, 1]] * mul + add; // Print the result for // the current query Console.Write(ans + " "); } } } // Driver Code public static void Main() { int[] arr = { 3, 1, 23, 45, 100 }; int N = arr.Length; int[, ] Q = { { 1, 2 }, { 0, 10 }, { 2, 3 }, { 1, 5 }, { 2, 4 } }; Query(arr, N, Q); }}// This code is contributed by ukasp. |
Javascript
<script>// Javascript implementation of the above approach // Function to modify the array // by performing given queries function Query(arr, N, Q) { // Stores the multiplication // of all integers of type 1 let mul = 1; // Stores the value obtained after // performing queries of type 1 & 2 let add = 0; // Iterate over the queries for (let i = 0; i < Q.length; i++) { // Query of type 0 if (Q[i][0] == 0) { // Update the value of add add = add + Q[i][1]; } // Query of type 1 else if (Q[i][0] == 1) { // Update the value of mul mul = mul * Q[i][1]; // Update the value of add add = add * Q[i][1]; } // Otherwise else { // Store the element at index Q[i][1] let ans = arr[Q[i][1]] * mul + add; // Print the result for // the current query document.write(ans + " "); } } } // Driver Code let arr = [ 3, 1, 23, 45, 100 ]; let N = arr.length; let Q = [[ 1, 2 ], [ 0, 10 ], [ 2, 3 ], [ 1, 5 ], [ 2, 4 ]]; Query(arr, N, Q); </script> |
Output:
100 1050
Time Complexity: O(M)
Auxiliary Space: O(1), since no extra space has been taken.
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!
