Queries to calculate Bitwise AND of an array with updates | C ++ program for the above approach ; Store the number of set bits at each position ; Function to precompute the prefix count array ; Iterate over the range [ 0 , 31 ] ; Set the bit at position i if arr [ 0 ] is set at position i ; Traverse the array and take prefix sum ; Update prefixCount [ i ] [ j ] ; Function to find the Bitwise AND of all array elements ; Stores the required result ; Iterate over the range [ 0 , 31 ] ; Stores the number of set bits at position i ; If temp is N , then set ith position in the result ; Print the result ; Function to update the prefix count array in each query ; Iterate through all the bits of the current number ; Store the bit at position i in the current value and the new value ; If bit2 is set and bit1 is unset , then increase the set bits at position i by 1 ; If bit1 is set and bit2 is unset , then decrease the set bits at position i by 1 ; Function to find the bitwise AND of the array after each query ; Fill the prefix count array ; Traverse the queries ; Store the index and the new value ; Store the current element at the index ; Update the array element ; Apply the changes to the prefix count array ; Print the bitwise AND of the modified array ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; int prefixCount [ 32 ] [ 10000 ] ; void findPrefixCount ( vector < int > arr , int size ) { for ( int i = 0 ; i < 32 ; i ++ ) { prefixCount [ i ] [ 0 ] = ( ( arr [ 0 ] >> i ) & 1 ) ; for ( int j = 1 ; j < size ; j ++ ) { prefixCount [ i ] [ j ] = ( ( arr [ j ] >> i ) & 1 ) ; prefixCount [ i ] [ j ] += prefixCount [ i ] [ j - 1 ] ; } } } void arrayBitwiseAND ( int size ) { int result = 0 ; for ( int i = 0 ; i < 32 ; i ++ ) { int temp = prefixCount [ i ] [ size - 1 ] ; if ( temp == size ) result = ( result | ( 1 << i ) ) ; } cout << result << " ▁ " ; } void applyQuery ( int currentVal , int newVal , int size ) { for ( int i = 0 ; i < 32 ; i ++ ) { int bit1 = ( ( currentVal >> i ) & 1 ) ; int bit2 = ( ( newVal >> i ) & 1 ) ; if ( bit2 > 0 && bit1 == 0 ) prefixCount [ i ] [ size - 1 ] ++ ; else if ( bit1 > 0 && bit2 == 0 ) prefixCount [ i ] [ size - 1 ] -- ; } } void findbitwiseAND ( vector < vector < int > > queries , vector < int > arr , int N , int M ) { findPrefixCount ( arr , N ) ; for ( int i = 0 ; i < M ; i ++ ) { int id = queries [ i ] [ 0 ] ; int newVal = queries [ i ] [ 1 ] ; int currentVal = arr [ id ] ; arr [ id ] = newVal ; applyQuery ( currentVal , newVal , N ) ; arrayBitwiseAND ( N ) ; } } int main ( ) { vector < int > arr { 1 , 2 , 3 , 4 , 5 } ; vector < vector < int > > queries { { 0 , 2 } , { 3 , 3 } , { 4 , 2 } } ; int N = arr . size ( ) ; int M = queries . size ( ) ; findbitwiseAND ( queries , arr , N , M ) ; return 0 ; }