Count of odd and even parity elements in subarray using MO’s algorithm
Given an array arr consisting of N elements and Q queries represented by L and R denoting a range, the task is to print the count of odd and even parity elements in the subarray [L, R].
Examples:
Input: arr[]=[5, 2, 3, 1, 4, 8, 10] Q=2 1 3 0 4
Output: 2 1 3 2
Explanation: In query 1, odd parity elements in subarray [1:3] are 2 and 1 and the even parity element is 3. In query 2, odd parity elements in subarray [0:4] are 2, 1, and 4 and even parity elements are 5 and 3.Input: arr[] = { 13, 17, 12, 10, 18, 19, 15, 7, 9, 6 } Q=3 1 5 0 7 2 9
Output: 1 4 3 5 2 6
Explanation: In query 1, the odd parity element in subarray [1:4] is 19 and even parity elements are 17,12,10 and 18. In query 2, odd parity elements in subarray [0:7] are 13, 19, and 7 and even parity elements are 17,12,10,18 and 15. In query 3, odd parity elements in subarray [2:6] are 19 and 7 and even parity elements are 12,10,18, 15, 9, and 6.
Approach:
The idea of MO’s algorithm is to pre-process all queries so that the result of one query can be used in the next query.
- Sort all queries so that queries with L values from 0 to √n – 1 are put together, followed by queries from √n to 2×√n – 1, and so on.
- All queries within a block are sorted in increasing order of R values.
- Count the odd parity elements and then calculate the even parity elements as (R-L+1- odd parity elements)
- Process all queries one by one and increase the count of odd parity elements and store the result in the structure.
- Let count_oddP store the count of odd parity elements in previous query.
- Remove extra elements of previous query and add new elements for the current query. For example, if previous query was [0, 8] and the current query is [3, 9], then remove the elements arr[0], arr[1] and arr[2] and add arr[9].
- In order to display the results, sort the queries in the order they were provided.
Adding elements()
- If the current element has odd parity then increase the count of count_oddP.
Removing elements()
- If the current element has odd parity then decrease the count of count_oddP.
Below is the implementation of the above approach:
C++
// C++ program to count odd and // even parity elements in subarray // using MO's algorithm #include <bits/stdc++.h> using namespace std; #define MAX 100000 // Variable to represent block size. // This is made global so compare() // of sort can use it. int block; // Structure to represent a query range struct Query { // Starting index int L; // Ending index int R; // Index of query int index; // Count of odd // parity elements int odd; // Count of even // parity elements int even; }; // To store the count of // odd parity elements int count_oddP; // Function used to sort all queries so that // all queries of the same block are arranged // together and within a block, queries are // sorted in increasing order of R values. bool compare(Query x, Query y) { // Different blocks, sort by block. if (x.L / block != y.L / block) return x.L / block < y.L / block; // Same block, sort by R value return x.R < y.R; } // Function used to sort all queries in order of their // index value so that results of queries can be printed // in same order as of input bool compare1(Query x, Query y) { return x.index < y.index; } // Function to Add elements // of current range void add( int currL, int a[]) { // _builtin_parity(x)returns true(1) // if the number has odd parity else // it returns false(0) for even parity. if (__builtin_parity(a[currL])) count_oddP++; } // Function to remove elements // of previous range void remove ( int currR, int a[]) { // _builtin_parity(x)returns true(1) // if the number has odd parity else // it returns false(0) for even parity. if (__builtin_parity(a[currR])) count_oddP--; } // Function to generate the result of queries void queryResults( int a[], int n, Query q[], int m) { // Initialize number of odd parity // elements to 0 count_oddP = 0; // Find block size block = ( int ) sqrt (n); // Sort all queries so that queries of // same blocks are arranged together. sort(q, q + m, compare); // Initialize current L, current R and // current result int currL = 0, currR = 0; for ( int i = 0; i < m; i++) { // L and R values of current range int L = q[i].L, R = q[i].R; // Add Elements of current range while (currR <= R) { add(currR, a); currR++; } while (currL > L) { add(currL - 1, a); currL--; } // Remove element of previous range while (currR > R + 1) { remove (currR - 1, a); currR--; } while (currL < L) { remove (currL, a); currL++; } q[i].odd = count_oddP; q[i].even = R - L + 1 - count_oddP; } } // Function to display the results of // queries in their initial order void printResults(Query q[], int m) { sort(q, q + m, compare1); for ( int i = 0; i < m; i++) { cout << q[i].odd << " " << q[i].even << endl; } } // Driver Code int main() { int arr[] = { 5, 2, 3, 1, 4, 8, 10, 12 }; int n = sizeof (arr) / sizeof (arr[0]); Query q[] = { { 1, 3, 0, 0, 0 }, { 0, 4, 1, 0, 0 }, { 4, 7, 2, 0, 0 } }; int m = sizeof (q) / sizeof (q[0]); queryResults(arr, n, q, m); printResults(q, m); return 0; } |
Java
import java.util.Arrays; // Class to represent a query range class Query { // Starting index int L; // Ending index int R; // Index of query int index; // Count of odd parity elements int odd; // Count of even parity elements int even; Query( int L, int R, int index) { this .L = L; this .R = R; this .index = index; this .odd = 0 ; this .even = 0 ; } } public class GFG { // Variable to represent block size. // This is made global so compare() // can use it. static int block; // To store the count of odd parity elements static int count_oddP; // Function to Add elements // of the current range static void add( int currL, int [] a) { if (Integer.bitCount(a[currL]) % 2 != 0 ) count_oddP++; } // Function to remove elements // of the previous range static void remove( int currR, int [] a) { if (Integer.bitCount(a[currR]) % 2 != 0 ) count_oddP--; } // Function to generate the result of queries static void queryResults( int [] a, int n, Query[] q, int m) { // Initialize the number of odd parity elements to 0 count_oddP = 0 ; // Find the block size block = ( int )Math.sqrt(n); // Sort all queries so that queries of the same // blocks are arranged together. Arrays.sort(q, (x, y) -> { if (x.L / block != y.L / block) return x.L / block - y.L / block; return x.R - y.R; }); // Initialize current L, current R and current // result int currL = 0 , currR = 0 ; for ( int i = 0 ; i < m; i++) { // L and R values of the current range int L = q[i].L, R = q[i].R; // Add elements of the current range while (currR <= R) { add(currR, a); currR++; } while (currL > L) { add(currL - 1 , a); currL--; } // Remove element of the previous range while (currR > R + 1 ) { remove(currR - 1 , a); currR--; } while (currL < L) { remove(currL, a); currL++; } q[i].odd = count_oddP; q[i].even = R - L + 1 - count_oddP; } } // Function to display the results of queries in their // initial order static void printResults(Query[] q, int m) { Arrays.sort(q, (x, y) -> x.index - y.index); for ( int i = 0 ; i < m; i++) { System.out.println(q[i].odd + " " + q[i].even); } } // Driver Code public static void main(String[] args) { int [] arr = { 5 , 2 , 3 , 1 , 4 , 8 , 10 , 12 }; int n = arr.length; Query[] q = { new Query( 1 , 3 , 0 ), new Query( 0 , 4 , 1 ), new Query( 4 , 7 , 2 ) }; int m = q.length; queryResults(arr, n, q, m); printResults(q, m); } } |
Python
import math # Structure to represent a query range class Query: def __init__( self , L, R, index, odd, even): self .L = L self .R = R self .index = index self .odd = odd self .even = even # Function used to sort all queries so that # all queries of the same block are arranged # together and within a block, queries are # sorted in increasing order of R values. def compare(x, y): # Different blocks, sort by block. if x.L / / block ! = y.L / / block: return x.L / / block < y.L / / block # Same block, sort by R value return x.R < y.R # Function used to sort all queries in order of their # index value so that results of queries can be printed # in the same order as input def compare1(x, y): return x.index < y.index # Function to Add elements # of the current range def add(currL, a): global count_oddP # __builtin_parity(x) returns True (1) # if the number has odd parity else # it returns False (0) for even parity. if bin (a[currL]).count( '1' ) % 2 = = 1 : count_oddP + = 1 # Function to remove elements # of the previous range def remove(currR, a): global count_oddP # __builtin_parity(x) returns True (1) # if the number has odd parity else # it returns False (0) for even parity. if bin (a[currR]).count( '1' ) % 2 = = 1 : count_oddP - = 1 # Function to generate the result of queries def queryResults(a, n, q, m): global block, count_oddP # Initialize number of odd parity # elements to 0 count_oddP = 0 # Find block size block = int (math.sqrt(n)) # Sort all queries so that queries of # the same blocks are arranged together. q.sort(key = lambda x: (x.L / / block, x.R)) # Initialize current L, current R, and # current result currL, currR = 0 , 0 for i in range (m): # L and R values of the current range L, R = q[i].L, q[i].R # Add Elements of the current range while currR < = R: add(currR, a) currR + = 1 while currL > L: add(currL - 1 , a) currL - = 1 # Remove element of the previous range while currR > R + 1 : remove(currR - 1 , a) currR - = 1 while currL < L: remove(currL, a) currL + = 1 q[i].odd = count_oddP q[i].even = R - L + 1 - count_oddP # Function to display the results of # queries in their initial order def printResults(q, m): q.sort(key = lambda x: x.index) for i in range (m): print (q[i].odd, q[i].even) # Driver Code if __name__ = = "__main__" : arr = [ 5 , 2 , 3 , 1 , 4 , 8 , 10 , 12 ] n = len (arr) q = [Query( 1 , 3 , 0 , 0 , 0 ), Query( 0 , 4 , 1 , 0 , 0 ), Query( 4 , 7 , 2 , 0 , 0 )] m = len (q) queryResults(arr, n, q, m) printResults(q, m) |
C#
using System; class Query { public int L; // Starting index public int R; // Ending index public int index; // Index of query public int odd; // Count of odd parity elements public int even; // Count of even parity elements } class Program { static int block; static int count_oddP; static void Add( int currL, int [] a) { if (Convert.ToString(a[currL], 2).Replace( "0" , "" ).Length % 2 == 1) count_oddP++; } static void Remove( int currR, int [] a) { if (Convert.ToString(a[currR], 2).Replace( "0" , "" ).Length % 2 == 1) count_oddP--; } static void QueryResults( int [] a, int n, Query[] q, int m) { count_oddP = 0; block = ( int )Math.Sqrt(n); Array.Sort(q, (x, y) => { if (x.L / block != y.L / block) return x.L / block - y.L / block; return x.R - y.R; }); int currL = 0, currR = 0; for ( int i = 0; i < m; i++) { int L = q[i].L, R = q[i].R; while (currR <= R) { Add(currR, a); currR++; } while (currL > L) { Add(currL - 1, a); currL--; } while (currR > R + 1) { Remove(currR - 1, a); currR--; } while (currL < L) { Remove(currL, a); currL++; } q[i].odd = count_oddP; q[i].even = R - L + 1 - count_oddP; } } static void PrintResults(Query[] q, int m) { Array.Sort(q, (x, y) => x.index - y.index); for ( int i = 0; i < m; i++) { Console.WriteLine(q[i].odd + " " + q[i].even); } } static void Main( string [] args) { int [] arr = { 5, 2, 3, 1, 4, 8, 10, 12 }; int n = arr.Length; Query[] q = { new Query { L = 1, R = 3, index = 0 }, new Query { L = 0, R = 4, index = 1 }, new Query { L = 4, R = 7, index = 2 } }; int m = q.Length; QueryResults(arr, n, q, m); PrintResults(q, m); } } |
Javascript
class Query { constructor(L, R, index, odd, even) { this .L = L; this .R = R; this .index = index; this .odd = odd; this .even = even; } } let block; let count_oddP; function add(currL, a) { if (countSetBits(a[currL]) % 2 === 1) count_oddP++; } function remove(currR, a) { if (countSetBits(a[currR]) % 2 === 1) count_oddP--; } function countSetBits(num) { let count = 0; while (num) { count += num & 1; num >>= 1; } return count; } function queryResults(a, n, q, m) { count_oddP = 0; block = Math.sqrt(n); q.sort((x, y) => { if (x.L / block !== y.L / block) return x.L / block - y.L / block; return x.R - y.R; }); let currL = 0, currR = 0; for (let i = 0; i < m; i++) { const L = q[i].L, R = q[i].R; while (currR <= R) { add(currR, a); currR++; } while (currL > L) { add(currL - 1, a); currL--; } while (currR > R + 1) { remove(currR - 1, a); currR--; } while (currL < L) { remove(currL, a); currL++; } q[i].odd = count_oddP; q[i].even = R - L + 1 - count_oddP; } } function printResults(q) { q.sort((x, y) => x.index - y.index); for (let i = 0; i < q.length; i++) { console.log(q[i].odd + " " + q[i].even); } } const arr = [5, 2, 3, 1, 4, 8, 10, 12]; const n = arr.length; const q = [ new Query(1, 3, 0, 0, 0), new Query(0, 4, 1, 0, 0), new Query(4, 7, 2, 0, 0) ]; const m = q.length; queryResults(arr, n, q, m); printResults(q); |
2 1 3 2 2 2
Time Complexity: O(Q × √n)
Auxiliary Space: O(n + m), where n is the size of the input array, and m is the number of queries.
Contact Us