Given an array of N elements, initially all a[i] = 0. Q queries need to be performed. Each query contains three integers l, r, and x and you need to change all a[i] to (a[i] | x) for all l ≤ i ≤ r and return the array after executing Q queries.
Examples:
Input: N = 3, Q = 2, U = {{1, 3, 1}, {1, 3, 2}}
Output: a[] = {3, 3, 3}
Explanation: Initially, all elements of the array are 0. After execution of the first query, all elements become 1 and after execution of the second query all elements become 3.Input: N = 3, Q = 2, U = {{1, 2, 1}, {3, 3, 2}}
Output: a[] = {1, 1, 2}
Explanation: {0, 0, 0] => {1, 1, 0} => {1, 1, 2}
Naive Approach:
- Initialize the array a of the size N with all elements set to 0.
- For each query in U:
– Iterate over the range from the l to r (inclusive).
– For each index i, perform the bitwise OR operation between the current value at a[i] and x, and update a[i] with the result. - Return the final array a after executing all queries.
Below is the implementation of the above approach:
C++
#include <bits/stdc++.h>using namespace std;// Function to perform operations on an array based on given// queriesvector<int> GFG(int N, int Q, vector<vector<int> >& U){ vector<int> a(N, 0); // Process each query in U for (const auto& query : U) { // Start index of range int l = query[0]; // End index of range int r = query[1]; // Value to be ORed int x = query[2]; // Perform OR operation on elements within the range // [l, r] for (int i = l - 1; i < r; ++i) { a[i] |= x; } } return a;}int main(){ // Number of elements in the array int N = 3; // Number of queries int Q = 2; vector<vector<int> > U = { { 1, 2, 1 }, { 3, 3, 2 } }; // Queries: [l, r, x] // Call the function to perform operations on the array vector<int> result = GFG(N, Q, U); // Print the resulting array for (const auto& num : result) { cout << num << " "; } cout << endl; return 0;} |
Java
// Java code for the above approach:import java.util.ArrayList;import java.util.List;public class Main { // Function to perform operations on an array based on given // queries public static List<Integer> GFG(int N, int Q, List<List<Integer>> U) { List<Integer> a = new ArrayList<>(N); for (int i = 0; i < N; i++) { a.add(0); } // Process each query in U for (List<Integer> query : U) { // Start index of range int l = query.get(0); // End index of range int r = query.get(1); // Value to be ORed int x = query.get(2); // Perform OR operation on elements within the range // [l, r] for (int i = l - 1; i < r; i++) { a.set(i, a.get(i) | x); } } return a; } public static void main(String[] args) { // Number of elements in the array int N = 3; // Number of queries int Q = 2; List<List<Integer>> U = new ArrayList<>(); U.add(List.of(1, 2, 1)); U.add(List.of(3, 3, 2)); // Queries: [l, r, x] // Call the function to perform operations on the array List<Integer> result = GFG(N, Q, U); // Print the resulting array for (int num : result) { System.out.print(num + " "); } System.out.println(); }}// This code is contributed by Utkarsh Kumar |
C#
using System;using System.Collections.Generic;class Program{ // Function to perform operations on an // array based on given queries static List<int> Geek(int N, int Q, List<List<int>> U) { List<int> a = new List<int>(new int[N]); // Process each query in U foreach (var query in U) { // Start index of range int l = query[0]; // End index of range int r = query[1]; // Value to be ORed int x = query[2]; // Perform OR operation on elements within // the range [l, r] for (int i = l - 1; i < r; ++i) { a[i] |= x; } } return a; } static void Main(string[] args) { // Number of elements in the array int N = 3; // Number of queries int Q = 2; List<List<int>> U = new List<List<int>> { new List<int> { 1, 2, 1 }, new List<int> { 3, 3, 2 }, }; // Queries: [l, r, x] List<int> result = Geek(N, Q, U); // Print the resulting array foreach (var num in result) { Console.Write(num + " "); } Console.WriteLine(); }} |
Output
1 1 2
Time complexity: O(N * Q), where N is the number of elements in the array and Q is the number of queries.
Auxiliary space: O(N) because it uses an additional vector a to store the resulting array of size N.
Efficient Approach:
To solve this problem efficiently, we have to use the concept of difference arrays for each bit.
Below are the steps for the above approach:
- Create a 2D difference array say, dp[][] of size N*20. For every index, keep an array of size 20 to store the bits and initialize every index as 0.
- For each query of l, r, and x, increment those indices of the dp[l] array where the bit position of x is set and decrement those indexes of the dp[r+1] array where the bit position of x is set.
- For each bit, we will run a loop from i=1 to N. And add the value of the previous index to the value of the current index, dp[i][j] += dp[i-1][j].
- Declare an array, say a[] which will be the answer array.
- Every inner array of dp[][] array represents a number. That means every index of the inner array represents the bit of a number. So put the numbers in their appropriate positions and return them.
Below is the implementation of the above approach:
C++
// C++ code for the above approach:#include <bits/stdc++.h>using namespace std;vector<int> updateQuery(int N, int Q, vector<vector<int> >& U){ // Code here vector<int> a(N); fill(a.begin(), a.end(), 0); int dp[N][20]; for (int i = 0; i < N; i++) { for (int j = 0; j < 20; j++) dp[i][j] = 0; } for (int j = 0; j < U.size(); j++) { for (int i = 0; i < 20; i++) { if (U[j][2] & (1 << i)) { dp[U[j][0] - 1][i]++; if (U[j][1] < N) dp[U[j][1]][i]--; } } } for (int j = 0; j < 20; j++) { for (int i = 1; i < N; i++) { dp[i][j] += dp[i - 1][j]; } } for (int i = 0; i < N; i++) { int ans = 0; for (int j = 0; j < 20; j++) { if (dp[i][j]) ans += (1 << j); } a[i] = ans; } return a;}// Drivers codeint main(){ int N = 3, Q = 2; vector<vector<int> > u = { { 1, 2, 1 }, { 3, 3, 2 } }; // Function Call vector<int> ans = updateQuery(N, Q, u); for (auto it : ans) cout << it << " "; return 0;} |
Java
// Java code for the above approach:import java.util.*;class GFG { public static void main(String[] args) { int N = 3, Q = 2; List<List<Integer>> U = new ArrayList<>(); U.add(Arrays.asList(1, 2, 1)); U.add(Arrays.asList(3, 3, 2)); List<Integer> ans = updateQuery(N, Q, U); for (int it : ans) System.out.print(it + " "); } static List<Integer> updateQuery(int N, int Q, List<List<Integer>> U) { List<Integer> a = new ArrayList<>(); for (int i = 0; i < N; i++) a.add(0); int[][] dp = new int[N][20]; for (int i = 0; i < N; i++) { for (int j = 0; j < 20; j++) dp[i][j] = 0; } for (int j = 0; j < U.size(); j++) { for (int i = 0; i < 20; i++) { if ((U.get(j).get(2) & (1 << i)) != 0) { dp[U.get(j).get(0) - 1][i]++; if (U.get(j).get(1) < N) dp[U.get(j).get(1)][i]--; } } } for (int j = 0; j < 20; j++) { for (int i = 1; i < N; i++) { dp[i][j] += dp[i - 1][j]; } } for (int i = 0; i < N; i++) { int ansVal = 0; for (int j = 0; j < 20; j++) { if (dp[i][j] != 0) ansVal += (1 << j); } a.set(i, ansVal); } return a; }} |
Python3
# Python3 code for the above approach:def updateQuery(N, Q, U): # Code here a = [0]*N dp = [[0]*20 for i in range(N)] for j in range(len(U)): for i in range(20): if (U[j][2] & (1 << i)): dp[U[j][0] - 1][i] += 1 if (U[j][1] < N): dp[U[j][1]][i] -= 1 for j in range(20): for i in range(1, N): dp[i][j] += dp[i - 1][j] for i in range(N): ans = 0 for j in range(20): if (dp[i][j]): ans += (1 << j) a[i] = ans return a# Drivers codeN = 3Q = 2U = [ [ 1, 2, 1 ], [ 3, 3, 2 ] ]# Function Callans = updateQuery(N, Q, U)for it in ans: print(it, end=" ") |
C#
// C# code for the above approach:using System;using System.Collections.Generic;class GFG { static List<int> UpdateQuery(int N, int Q, List<List<int> > U) { List<int> a = new List<int>(new int[N]); int[, ] dp = new int[N, 20]; for (int i = 0; i < N; i++) { for (int j = 0; j < 20; j++) { dp[i, j] = 0; } } for (int j = 0; j < U.Count; j++) { for (int i = 0; i < 20; i++) { if ((U[j][2] & (1 << i)) != 0) { dp[U[j][0] - 1, i]++; if (U[j][1] < N) { dp[U[j][1], i]--; } } } } for (int j = 0; j < 20; j++) { for (int i = 1; i < N; i++) { dp[i, j] += dp[i - 1, j]; } } for (int i = 0; i < N; i++) { int ans = 0; for (int j = 0; j < 20; j++) { if (dp[i, j] != 0) { ans += (1 << j); } } a[i] = ans; } return a; } static void Main(string[] args) { int N = 3, Q = 2; List<List<int> > U = new List<List<int> >(); U.Add(new List<int>{ 1, 2, 1 }); U.Add(new List<int>{ 3, 3, 2 }); // Function Call List<int> ans = UpdateQuery(N, Q, U); foreach(var item in ans) { Console.Write(item + " "); } }} |
Javascript
// JavaScript code for the above approach:function updateQuery(N, Q, U) { let a = new Array(N).fill(0); let dp = new Array(N); for (let i = 0; i < N; i++) { dp[i] = new Array(20).fill(0); } for (let j = 0; j < U.length; j++) { for (let i = 0; i < 20; i++) { if (U[j][2] & (1 << i)) { dp[U[j][0] - 1][i]++; if (U[j][1] < N) { dp[U[j][1]][i]--; } } } } for (let j = 0; j < 20; j++) { for (let i = 1; i < N; i++) { dp[i][j] += dp[i - 1][j]; } } for (let i = 0; i < N; i++) { let ans = 0; for (let j = 0; j < 20; j++) { if (dp[i][j]) { ans += 1 << j; } } a[i] = ans; } return a;}// Example usagelet N = 3;let Q = 2;let U = [[1, 2, 1], [3, 3, 2]];let ans = updateQuery(N, Q, U);console.log(ans.join(" ")); // Outputs: 1 1 2 |
Output
1 1 2
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!
