Given two arrays arr[] of size N and queries[] of size Q, the task is to find the OR of AND of subsets of the array. In each query, you are given an index and a value, you have to replace the value at the given index of the arrays with a given value and print the OR of AND of all subsets of the array after each query.
Examples:
Input: arr[] = {3, 5, 7}, N = 3, queries[] = {{1, 2}, {2, 1}}, Q = 2
Output: 7
3
Explanation:
For the first query replace the value at index 1 with value 2, updated array arr[] is {3, 2, 7}.
Then take AND of all subsets i.e. AND(3) = 3, AND(2) = 2, AND(7) = 7, AND(3, 2) = 2, AND(3, 7) = 3, AND(3, 2, 7) = 2.
OR of the AND of all subsets are OR(3, 2, 7, 2, 3, 2) = 7.
Now, for the second query replace the value at index 2 with value 1, updated array arr[] is {3, 2, 1}.
Then take AND of all subsets i.e. AND(3) = 3, AND(2) = 2, AND(1) = 1, AND(3, 2) = 2, AND(3, 1) = 1, AND(3, 2, 1) = 0.
OR of the AND of all subsets OR(3, 2, 1, 2, 1, 0) = 3.Input: arr[] = {1, 2, 3}, N = 3, queries[] = {{2, 4}, {1, 8}}, Q = 2
Output: 7
13
Approach: This problem can be solved using greedy algorithm. Follow the steps below to solve the problem:
- Initialize an array bits[] of size 32 and store the count of set bits of all the elements.
- Iterate in the range [0, Q-1] using the variable p:
- First subtract the bits of previous value and then add the bits of new value.
- Iterate in the range [0, 31] using the variable i:
- If the current bit is set for the previous value, then subtract one bit to the bits[] array at ith index.
- If the current bit is set for the new value, then add one bit to the bits[] array at ith index.
- Replace the new value from the previous value in given array arr[].
- Initialize a variable ans to store the OR of the bits array.
- Iterate in the range [0, 31] using the variable i:
- If the current bit is not equal to 0, then add the OR of the current bit into ans.
- After completing the above steps, print the ans as the required answer for each query.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to find the OR of AND of all// subsets of the array for each queryvoid Or_of_Ands_for_each_query(int arr[], int n, int queries[][2], int q){ // An array to store the bits int bits[32] = { 0 }; // Iterate for all the bits for (int i = 0; i < 32; i++) { // Iterate over all the numbers and // store the bits in bits[] array for (int j = 0; j < n; j++) { if ((1 << i) & arr[j]) { bits[i]++; } } } // Iterate over all the queries for (int p = 0; p < q; p++) { // Replace the bits of the value // at arr[queries[p][0]] with the bits // of queries[p][1] for (int i = 0; i < 32; i++) { if ((1 << i) & arr[queries[p][0]]) { bits[i]--; } if (queries[p][1] & (1 << i)) { bits[i]++; } } // Substitute the value in the array arr[queries[p][0]] = queries[p][1]; int ans = 0; // Find OR of the bits[] array for (int i = 0; i < 32; i++) { if (bits[i] != 0) { ans |= (1 << i); } } // Print the answer cout << ans << endl; }}// Driver Codeint main(){ // Given Input int n = 3, q = 2; int arr[] = { 3, 5, 7 }; int queries[2][2] = { { 1, 2 }, { 2, 1 } }; // Function Call Or_of_Ands_for_each_query(arr, n, queries, q); return 0;} |
Java
// java program for the above approachimport java.util.*;class GFG { // Function to find the OR of AND of all // subsets of the array for each query static void Or_of_Ands_for_each_query(int arr[], int n, int queries[][], int q) { // An array to store the bits int bits[] = new int[32]; Arrays.fill(bits, 0); // Iterate for all the bits for (int i = 0; i < 32; i++) { // Iterate over all the numbers and // store the bits in bits[] array for (int j = 0; j < n; j++) { if (((1 << i) & arr[j]) != 0) { bits[i]++; } } } // Iterate over all the queries for (int p = 0; p < q; p++) { // Replace the bits of the value // at arr[queries[p][0]] with the bits // of queries[p][1] for (int i = 0; i < 32; i++) { if (((1 << i) & arr[queries[p][0]]) != 0) { bits[i]--; } if ((queries[p][1] & (1 << i)) != 0) { bits[i]++; } } // Substitute the value in the array arr[queries[p][0]] = queries[p][1]; int ans = 0; // Find OR of the bits[] array for (int i = 0; i < 32; i++) { if (bits[i] != 0) { ans |= (1 << i); } } // Print the answer System.out.println(ans); } } // Driver Code public static void main(String[] args) { // Given Input int n = 3, q = 2; int arr[] = { 3, 5, 7 }; int queries[][] = { { 1, 2 }, { 2, 1 } }; // Function Call Or_of_Ands_for_each_query(arr, n, queries, q); }}// This code is contributed by subhammahato348. |
Python3
# Python3 program for the above approach# Function to find the OR of AND of all# subsets of the array for each querydef Or_of_Ands_for_each_query(arr, n, queries, q): # An array to store the bits bits = [0 for x in range(32)] # Iterate for all the bits for i in range(0, 32): # Iterate over all the numbers and # store the bits in bits[] array for j in range(0, n): if ((1 << i) & arr[j]): bits[i] += 1 # Iterate over all the queries for p in range(0, q): # Replace the bits of the value # at arr[queries[p][0]] with the bits # of queries[p][1] for i in range(0, 32): if ((1 << i) & arr[queries[p][0]]): bits[i] -= 1 if (queries[p][1] & (1 << i)): bits[i] += 1 # Substitute the value in the array arr[queries[p][0]] = queries[p][1] ans = 0 # Find OR of the bits[] array for i in range(0, 32): if (bits[i] != 0): ans |= (1 << i) # Print the answer print(ans)# Driver Code# Given Inputn = 3q = 2arr = [3, 5, 7]queries = [[1, 2], [2, 1]]# Function CallOr_of_Ands_for_each_query(arr, n, queries, q)# This code is contributed by amreshkumar3 |
C#
// C# program for the above approachusing System;class GFG{// Function to find the OR of AND of all// subsets of the array for each querystatic void Or_of_Ands_for_each_query(int[] arr, int n, int[,] queries, int q){ // An array to store the bits int[] bits = new int[32]; for(int i = 0; i < 32; i++) { bits[i] = 0; } // Iterate for all the bits for(int i = 0; i < 32; i++) { // Iterate over all the numbers and // store the bits in bits[] array for(int j = 0; j < n; j++) { if (((1 << i) & arr[j]) != 0) { bits[i]++; } } } // Iterate over all the queries for(int p = 0; p < q; p++) { // Replace the bits of the value // at arr[queries[p][0]] with the bits // of queries[p][1] for(int i = 0; i < 32; i++) { if (((1 << i) & arr[queries[p, 0]]) != 0) { bits[i]--; } if ((queries[p, 1] & (1 << i)) != 0) { bits[i]++; } } // Substitute the value in the array arr[queries[p, 0]] = queries[p, 1]; int ans = 0; // Find OR of the bits[] array for(int i = 0; i < 32; i++) { if (bits[i] != 0) { ans |= (1 << i); } } // Print the answer Console.WriteLine(ans); }}// Driver Codepublic static void Main(String[] args){ // Given Input int n = 3, q = 2; int[] arr = { 3, 5, 7 }; int[,] queries = { { 1, 2 }, { 2, 1 } }; // Function Call Or_of_Ands_for_each_query(arr, n, queries, q);}}// This code is contributed by target_2 |
Javascript
<script> // JavaScript program for the above approach // Function to find the OR of AND of all // subsets of the array for each query function Or_of_Ands_for_each_query(arr, n, queries, q) { // An array to store the bits let bits = new Array(32).fill(0); // Iterate for all the bits for (let i = 0; i < 32; i++) { // Iterate over all the numbers and // store the bits in bits[] array for (let j = 0; j < n; j++) { if ((1 << i) & arr[j]) { bits[i]++; } } } // Iterate over all the queries for (let p = 0; p < q; p++) { // Replace the bits of the value // at arr[queries[p][0]] with the bits // of queries[p][1] for (let i = 0; i < 32; i++) { if ((1 << i) & arr[queries[p][0]]) { bits[i]--; } if (queries[p][1] & (1 << i)) { bits[i]++; } } // Substitute the value in the array arr[queries[p][0]] = queries[p][1]; let ans = 0; // Find OR of the bits[] array for (let i = 0; i < 32; i++) { if (bits[i] != 0) { ans |= (1 << i); } } // Print the answer document.write(ans + "<br>"); } } // Driver Code // Given Input let n = 3, q = 2; let arr = [3, 5, 7]; let queries = [[1, 2], [2, 1]]; // Function Call Or_of_Ands_for_each_query(arr, n, queries, q); // This code is contributed by Potta Lokesh</script> |
Output
7 3
Time Complexity: O(max(N, Q))
Auxiliary Space: O(1)
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!
