Given an array arr[ ] consisting of N positive integers and a 2D array Q[][] consisting of queries of the form {i, val}, the task for each query is to replace arr[i] by val and calculate the Bitwise OR of the modified array.
Examples:
Input: arr[ ]= {1, 2, 3}, Q[ ][] = {{1, 4}, {3, 0}}
Output: 7 6
Explanation:
Replacing arr[1] by 4 modifies arr[ ] to {4, 2, 3}. Bitwise OR = 7.
Replacing arr[2] by 0 modifies arr[] to {4, 2, 0}. Bitwise OR = 6.Input: arr[ ]= {1, 2, 3, 4}, Q[][ ] = {{4, 0}, {2, 8}}
Output: 3 11
Explanation:
Replacing arr[3] by 0 modifies arr[ ] to {1, 2, 3, 0}. Bitwise OR = 3.
Replacing arr[2] by 8 modifies arr[] to {1, 8, 3, 0}. Bitwise OR = 11.
Naive Approach: The simplest approach to solve the problem is to traverse the array arr[ ] for every ith query after updating arr[Q[i][0]] by Q[i][1] to calculate Bitwise OR of the array.
Time Complexity: O(N * sizeof(Q))
Auxiliary Space: O(1)
Efficient Approach: Follow the steps below to solve the problem:
- Initialize an array result[] of size 32. Set all its elements to 0.
- Traverse the array arr[].
- Iterate over the bits of each array element.
- Increment result[j] for every jth unset bit found in the current array element.
- Now, traverse the array Q[][] and perform the following:
- Modify result[] by removing the set bits of Q[i][0] from their respective positions.
- Update result[] by adding the set bits of Q[i][0] from their respective positions.
- Convert the result[] array to its equivalent decimal value and print it.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;#define bitsSize 32// Function to convert a binary array// to equivalent decimal representationint toDecimal(int result[], int size){ // Stores the decimal result int ans = 0; // Traverse the array for (int i = 0; i < size; i++) { // If non-zero element // is encountered if (result[i] != 0) ans += pow(2, i); } return ans;}// Function to replace an array// element old_value by new_valuevoid findOrUtil(int result[], int old_value, int new_value){ int i = 0; // Removing old value from result while (old_value != 0) { result[i] -= old_value % 2; old_value = old_value / 2; i++; } i = 0; // Adding new value to result while (new_value != 0) { result[i] += new_value % 2; new_value = new_value / 2; i++; }}// Function to calculate and print// Bitwise OR of array for each queryvoid findOR(vector<int> arr, vector<pair<int, int> > queries){ int result[bitsSize]; // Initialize all bits to zero memset(result, 0, sizeof(result)); // Precompute and fill result[] for (int i = 0; i < arr.size(); i++) { int val = arr[i]; int j = 0; // Add all set bits to result[] while (val != 0) { result[j] += val % 2; val = val / 2; j++; } } // Traverse the queries for (int q = 0; q < queries.size(); q++) { int index = queries[q].first; int new_value = queries[q].second; // Update result[] by replacing // arr[index] by new_value findOrUtil(result, arr[index], new_value); // Modify arr[] arr[index] = new_value; // Calculate Bitwise OR int ans = toDecimal(result, bitsSize); // Print the value of Bitwise OR cout << ans << endl; }}// Driver Codeint main(){ // Given array vector<int> arr = { 1, 2, 3, 4 }; // Queries of the form {i, value} vector<pair<int, int> > queries; // 0-indexed queries queries.push_back({ 3, 0 }); queries.push_back({ 1, 8 }); findOR(arr, queries); return 0;} |
Java
// Java implementation of the approachimport java.util.ArrayList;class GFG{ static int bitsSize = 32;static class Pair{ int first; int second; Pair(int first, int second) { this.first = first; this.second = second; }}// Function to convert a binary array// to equivalent decimal representationstatic int toDecimal(int result[], int size){ // Stores the decimal result int ans = 0; // Traverse the array for(int i = 0; i < size; i++) { // If non-zero element // is encountered if (result[i] != 0) ans += Math.pow(2, i); } return ans;}// Function to replace an array// element old_value by new_valuestatic void findOrUtil(int result[], int old_value, int new_value){ int i = 0; // Removing old value from result while (old_value != 0) { result[i] -= old_value % 2; old_value = old_value / 2; i++; } i = 0; // Adding new value to result while (new_value != 0) { result[i] += new_value % 2; new_value = new_value / 2; i++; }}// Function to calculate and print// Bitwise OR of array for each querystatic void findOR(int[] arr, ArrayList<Pair> queries){ int result[] = new int[bitsSize]; // Precompute and fill result[] for(int i = 0; i < arr.length; i++) { int val = arr[i]; int j = 0; // Add all set bits to result[] while (val != 0) { result[j] += val % 2; val = val / 2; j++; } } // Traverse the queries for(int q = 0; q < queries.size(); q++) { int index = queries.get(q).first; int new_value = queries.get(q).second; // Update result[] by replacing // arr[index] by new_value findOrUtil(result, arr[index], new_value); // Modify arr[] arr[index] = new_value; // Calculate Bitwise OR int ans = toDecimal(result, bitsSize); // Print the value of Bitwise OR System.out.println(ans); }}// Driver codepublic static void main(String[] args){ // Given array int arr[] = { 1, 2, 3, 4 }; // Queries of the form {i, value} ArrayList<Pair> queries = new ArrayList<>(); // 0-indexed queries queries.add(new Pair(3, 0)); queries.add(new Pair(1, 8)); findOR(arr, queries);}}// This code is contributed by abhinavjain194 |
Python3
# Python3 implementation of the approach# Function to convert a binary array# to equivalent decimal representationdef toDecimal(result, size): # Stores the decimal result ans = 0 # Traverse the array for i in range(size): # If non-zero element # is encountered if (result[i] != 0): ans += pow(2, i) return ans# Function to replace an array# element old_value by new_valuedef findOrUtil(result, old_value, new_value): i = 0 # Removing old value from result while (old_value != 0): result[i] -= old_value % 2 old_value = old_value // 2 i += 1 i = 0 # Adding new value to result while (new_value != 0): result[i] += new_value % 2 new_value = new_value // 2 i += 1# Function to calculate and print# Bitwise OR of array for each querydef findOR(arr, queries): result = [0] * 32 # Initialize all bits to zero # memset(result, 0, sizeof(result)) # Precompute and fill result[] for i in range(len(arr)): val = arr[i] j = 0 # Add all set bits to result[] while (val != 0): result[j] += val % 2 val = val // 2 j += 1 # Traverse the queries for q in range(len(queries)): index = queries[q][0] new_value = queries[q][1] # Update result[] by replacing # arr[index] by new_value findOrUtil(result, arr[index], new_value) # Modify arr[] arr[index] = new_value # Calculate Bitwise OR ans = toDecimal(result, 32) # Print the value of Bitwise OR print (ans)# Driver Codeif __name__ == '__main__': # Given array arr = [ 1, 2, 3, 4 ] # Queries of the form {i, value} queries = [] # 0-indexed queries queries.append([3, 0]) queries.append([1, 8]) findOR(arr, queries)# This code is contributed by mohit kumar 29 |
C#
// C# implementation of the approachusing System;using System.Collections.Generic;class GFG{ static int bitsSize = 32;class Pair{ public int first; public int second; public Pair(int first, int second) { this.first = first; this.second = second; }}// Function to convert a binary array// to equivalent decimal representationstatic int toDecimal(int []result, int size){ // Stores the decimal result int ans = 0; // Traverse the array for(int i = 0; i < size; i++) { // If non-zero element // is encountered if (result[i] != 0) ans += (int)Math.Pow(2, i); } return ans;}// Function to replace an array// element old_value by new_valuestatic void findOrUtil(int []result, int old_value, int new_value){ int i = 0; // Removing old value from result while (old_value != 0) { result[i] -= old_value % 2; old_value = old_value / 2; i++; } i = 0; // Adding new value to result while (new_value != 0) { result[i] += new_value % 2; new_value = new_value / 2; i++; }}// Function to calculate and print// Bitwise OR of array for each querystatic void findOR(int[] arr, List<Pair> queries){ int []result = new int[bitsSize]; // Precompute and fill result[] for(int i = 0; i < arr.Length; i++) { int val = arr[i]; int j = 0; // Add all set bits to result[] while (val != 0) { result[j] += val % 2; val = val / 2; j++; } } // Traverse the queries for(int q = 0; q < queries.Count; q++) { int index = queries[q].first; int new_value = queries[q].second; // Update result[] by replacing // arr[index] by new_value findOrUtil(result, arr[index], new_value); // Modify []arr arr[index] = new_value; // Calculate Bitwise OR int ans = toDecimal(result, bitsSize); // Print the value of Bitwise OR Console.WriteLine(ans); }}// Driver codepublic static void Main(String[] args){ // Given array int []arr = { 1, 2, 3, 4 }; // Queries of the form {i, value} List<Pair> queries = new List<Pair>(); // 0-indexed queries queries.Add(new Pair(3, 0)); queries.Add(new Pair(1, 8)); findOR(arr, queries);}}// This code is contributed by 29AjayKumar |
Javascript
<script>// JavaScript implementation of the approachvar bitsSize = 32;// Function to convert a binary array// to equivalent decimal representationfunction toDecimal(result, size){ // Stores the decimal result var ans = 0; var i; // Traverse the array for (i = 0; i < size; i++) { // If non-zero element // is encountered if (result[i] != 0) ans += Math.pow(2, i); } return ans;}// Function to replace an array// element old_value by new_valuefunction findOrUtil(result, old_value, new_value){ var i = 0; // Removing old value from result while (old_value != 0) { result[i] -= old_value % 2; old_value = parseInt(old_value / 2); i++; } i = 0; // Adding new value to result while(new_value != 0) { result[i] += new_value % 2; new_value = parseInt(new_value / 2); i++; }}// Function to calculate and print// Bitwise OR of array for each queryfunction findOR(arr, queries){ var result = Array(bitsSize).fill(0); var i; // Precompute and fill result[] for (i = 0; i < arr.length; i++) { var val = arr[i]; var j = 0; // Add all set bits to result[] while (val != 0) { result[j] += val % 2; val = parseInt(val / 2); j++; } } var q; // Traverse the queries for (q = 0; q < queries.length; q++) { var index = queries[q][0]; var new_value = queries[q][1]; // Update result[] by replacing // arr[index] by new_value findOrUtil(result, arr[index], new_value); // Modify arr[] arr[index] = new_value; // Calculate Bitwise OR var ans = toDecimal(result, bitsSize); // Print the value of Bitwise OR document.write(ans+"<br>"); }}// Driver Code // Given array var arr = [1, 2, 3, 4]; // Queries of the form {i, value} var queries = [[3, 0],[1, 8]] findOR(arr, queries);</script> |
Output:
3 11
Time Complexity: O(N)
Auxiliary Space: O(1)
