Queries to count characters having odd frequency in a range [ L , R ] | C ++ Program to implement the above problem ; Function to print the number of characters having odd frequencies for each query ; A function to construct the arr [ ] and prefix [ ] ; Stores array length ; Stores the unique powers of 2 associated to each character ; Prefix array to store the XOR values from array elements ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; void queryResult ( int prefix [ ] , pair < int , int > Q ) { int l = Q . first ; int r = Q . second ; if ( l == 0 ) { int xorval = prefix [ r ] ; cout << __builtin_popcount ( xorval ) << endl ; } else { int xorval = prefix [ r ] ^ prefix [ l - 1 ] ; cout << __builtin_popcount ( xorval ) << endl ; } } void calculateCount ( string S , pair < int , int > Q [ ] , int m ) { int n = S . length ( ) ; int arr [ n ] ; for ( int i = 0 ; i < n ; i ++ ) { arr [ i ] = ( 1 << ( S [ i ] - ' a ' ) ) ; } int prefix [ n ] ; int x = 0 ; for ( int i = 0 ; i < n ; i ++ ) { x ^= arr [ i ] ; prefix [ i ] = x ; } for ( int i = 0 ; i < m ; i ++ ) { queryResult ( prefix , Q [ i ] ) ; } } int main ( ) { string S = " geeksforgeeks " ; pair < int , int > Q [ ] = { { 2 , 4 } , { 0 , 3 } , { 0 , 12 } } ; calculateCount ( S , Q , 3 ) ; }