Given an array arr[] of N elements, the task is to answer Q queries each having two integers L and R. For each query, the task is to find the number of elements in the subarray arr[L…R] whose digit sum is even.
Examples:
Input:arr[] = {7, 3, 19, 13, 5, 4}
query = { {1, 5}, {0, 1} }
Output: 3
Explanation:
Query 1: Elements 19, 13 and 4 have even digit sum in the subarray: {3, 9, 13, 5, 4}.
Query 2: No elements have even sum in the subarray: {7, 3}Input:arr[] = {0, 1, 2, 3, 4, 5, 6, 7}
query = { 3, 5 }
Output:1
We have already discussed this approach: Queries for the count of even digit sum elements in the given range using Segment Tree
Approach: (Using MO’s Algorithm)
The idea is to pre-process all queries so that result of one query can be used in the next query.
- Sort all queries in a way 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.
- Process all queries one by one and increase the count of even digit sum elements and store the result in the structure.
- Let count_even store the count of even digits sum elements in the 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.
Helper functions:
Adding elements()
- If the current element has even digit sum then increase the count of count_even.
Removing elements()
- If the current element has even digit sum then decrease the count of count_even.
Below code is the implementation of the above approach:
C++
// C++ program to count of even// digit sum elements in the given// range 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 rangestruct Query { // Starting index int L; // Ending index int R; // Index of query int index; // Count of even // even digit sum int even;};// To store the count of// even digit sumint count_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.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 inputbool compare1(Query x, Query y){ return x.index < y.index;}// Function to find the digit sum// for a numberint digitSum(int num){ int sum = 0; while (num) { sum += (num % 10); num /= 10; } return sum;}// Function to Add elements// of current rangevoid add(int currL, int a[]){ // If digit sum of a[currL] // is even then increment if (digitSum(a[currL]) % 2 == 0) count_even++;}// Function to remove elements// of previous rangevoid remove(int currR, int a[]){ // If digit sum of a[currL] // is even then decrement if (digitSum(a[currR]) % 2 == 0) count_even--;}// Function to generate// the result of queriesvoid queryResults(int a[], int n, Query q[], int m){ // Initialize number of // even digit sum to 0 count_even = 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].even = count_even; }}// Function to display the results of// queries in their initial ordervoid printResults(Query q[], int m){ sort(q, q + m, compare1); for (int i = 0; i < m; i++) { cout << q[i].even << endl; }}// Driver Codeint 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, 4, 1, 0 }, { 4, 7, 2, 0 } }; int m = sizeof(q) / sizeof(q[0]); queryResults(arr, n, q, m); printResults(q, m); return 0;} |
Java
// Java program to count of even// digit sum elements in the given// range using MO's algorithmimport java.util.Arrays;import java.util.Collections;import java.util.Comparator;class GFG{static int MAX = 100000;// Variable to represent block size.// This is made global so compare()// of sort can use it.static int block;// Structure to represent a query rangestatic class Query { // Starting index int L; // Ending index int R; // Index of query int index; // Count of even // even digit sum int even; public Query(int l, int r, int index, int even) { this.L = l; this.R = r; this.index = index; this.even = even; }};// To store the count of// even digit sumstatic int count_even;// Function to find the digit sum// for a numberstatic int digitSum(int num) { int sum = 0; while (num > 0) { sum += (num % 10); num /= 10; } return sum;}// Function to Add elements// of current rangestatic void add(int currL, int a[]){ // If digit sum of a[currL] // is even then increment if (digitSum(a[currL]) % 2 == 0) count_even++;}// Function to remove elements// of previous rangestatic void remove(int currR, int a[]) { // If digit sum of a[currL] // is even then decrement if (digitSum(a[currR]) % 2 == 0) count_even--;}// Function to generate// the result of queriesstatic void queryResults(int a[], int n, Query q[], int m){ // Initialize number of // even digit sum to 0 count_even = 0; // Find block size block = (int) Math.sqrt(n); // Sort all queries so that queries of // same blocks are arranged together. Collections.sort(Arrays.asList(q), new Comparator<Query>() { // 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. public int 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; } }); // 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].even = count_even; }}// Function to display the results of// queries in their initial orderstatic void printResults(Query q[], int m) { Collections.sort(Arrays.asList(q), new Comparator<Query>() { // 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 public int compare(Query x, Query y) { return x.index - y.index; } }); for(int i = 0; i < m; i++) { System.out.println(q[i].even); }}// Driver Codepublic 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, 0), new Query(0, 4, 1, 0), new Query(4, 7, 2, 0) }; int m = q.length; queryResults(arr, n, q, m); printResults(q, m);}}// This code is contributed by sanjeev2552 |
Python3
# Python program to count of even# digit sum elements in the given# range using MO's algorithmimport mathimport functoolsMAX = 100000arr = [5, 2, 3, 1, 4, 8, 10, 12]n = len(arr)# Variable to represent block size.# This is made here so compare()# of sort can use it.block = int(math.sqrt(n))# Class to represent a query rangeclass Query: def __init__(self, l, r, index, even): self.L = l # Starting index self.R = r # Ending index self.index = index # Index of query self.even = even # Count of even digit sum# 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 else: # Same block, sort by R value return x.R < y.R# Function to find the digit sum# for a numberdef digitSum(num): sum = 0 while num > 0: sum += (num % 10) num //= 10 return sum# Function to Add elements# of current rangedef add(currL, a, count_even): # If digit sum of a[currL] # is even then increment if digitSum(a[currL]) % 2 == 0: count_even += 1 return count_even# Function to remove elements# of previous rangedef remove(currR, a, count_even): # If digit sum of a[currL] # is even then decrement if digitSum(a[currR]) % 2 == 0: count_even -= 1 return count_even# Function to generate# the result of queriesdef queryResults(a, n, q, m): # Initialize number of # even digit sum to 0 count_even = 0 # Find block size block = int(math.sqrt(n)) # Sort all queries so that queries of # same blocks are arranged together. q.sort(key=functools.cmp_to_key(compare)) # Initialize current L, current R and # current result currL = 0 currR = 0 for i in range(m): # L and R values of current range L = q[i].L R = q[i].R # Add Elements of current range while currR <= R: count_even = add(currR, a, count_even) currR += 1 while currL > L: count_even = add(currL - 1, a, count_even) currL -= 1 # Remove element of previous range while currR > R + 1: count_even = remove(currR - 1, a, count_even) currR -= 1 while currL < L: count_even = remove(currL, a, count_even) currL += 1 q[i].even = count_even# Function to display the results of# queries in their initial orderdef printResults(q, m): q.sort(key=lambda x: x.index) for i in range(m): print(q[i].even)# Driver Codeq = [Query(1, 3, 0, 0), Query(0, 4, 1, 0), Query(4, 7, 2, 0)]m = len(q)queryResults(arr, n, q, m)printResults(q, m)# This code is contributed by Tapesh (tapeshdua420) |
C#
// program to count of even// digit sum elements in the given// range using MO's algorithmusing System;using System.Linq;using System.Collections.Generic;// Class to represent a query rangepublic class Query{ public int L { get; set; } public int R { get; set; } public int Index { get; set; } public int Even { get; set; } public Query(int l, int r, int index, int even) { L = l; R = r; Index = index; Even = even; }}public class GFG{ static int MAX = 100000; static int[] arr = new int[] { 5, 2, 3, 1, 4, 8, 10, 12 }; static int n = arr.Length; // Variable to represent block size. // This is made here so compare() // of sort can use it static int block = (int)Math.Sqrt(n); // Function to find the digit sum // for a number static int DigitSum(int num) { int sum = 0; while (num > 0) { sum += (num % 10); num /= 10; } return sum; } // Function to Add elements // of current range static int Add(int currL, int[] a, int count_even) { // If digit sum of a[currL] // is even then increment if (DigitSum(a[currL]) % 2 == 0) { count_even++; } return count_even; } // Function to remove elements // of previous range static int Remove(int currR, int[] a, int count_even) { // If digit sum of a[currL] // is even then decrement if (DigitSum(a[currR]) % 2 == 0) { count_even--; } return count_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. static int Compare(Query x, Query y) { // Different blocks, sort by block. if (x.L / block != y.L / block) { return x.L / block - y.L / block; } else { // Same block, sort by R value return x.R - y.R; } } // Function to generate // the result of queries static void QueryResults(int[] a, int n, Query[] q, int m) { // Initialize number of // even digit sum to 0 int count_even = 0; // Sort all queries so that queries of // same blocks are arranged together. q = q.OrderBy(x => x, Comparer<Query>.Create(Compare)).ToArray(); // 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) { count_even = Add(currR, a, count_even); currR++; } while (currL > L) { count_even = Add(currL - 1, a, count_even); currL--; } // Remove element of previous range while (currR > R + 1) { count_even = Remove(currR - 1, a, count_even); currR--; } while (currL < L) { count_even = Remove(currL, a, count_even); currL++; } q[i].Even = count_even; } } // Function to display the results of // queries in their initial order static void PrintResults(Query[] q, int m) { q = q.OrderBy(x => x.Index).ToArray(); for (int i = 0; i < m; i++) { Console.WriteLine(q[i].Even); } } // Driver Code public static void Main() { Query[] q = new Query[] { new Query(1, 3, 0, 0), new Query(0, 4, 1, 0), new Query(4, 7, 2, 0) }; int m = q.Length; QueryResults(arr, n, q, m); PrintResults(q, m); }}// This code is contributed by shivhach999 |
Javascript
// Function to find the digit sum for a numberfunction digitSum(num) {let sum = 0;while (num) {sum += (num % 10);num = Math.floor(num / 10);}return sum;}// Function to Add elements of current rangefunction add(currL, a, count_even) {// If digit sum of a[currL] is even then incrementif (digitSum(a[currL]) % 2 === 0) {count_even++;}return count_even;}// Function to remove elements of previous rangefunction remove(currR, a, count_even) {// If digit sum of a[currR] is even then decrementif (digitSum(a[currR]) % 2 === 0) {count_even--;}return count_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.function compare(x, y) {// Different blocks, sort by block.if (Math.floor(x.L / block) !== Math.floor(y.L / block)) {return Math.floor(x.L / block) < Math.floor(y.L / block);}// Same block, sort by R valuereturn 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 inputfunction compare1(x, y) {return x.index < y.index;}// Function to generate the result of queriesfunction queryResults(a, n, q, m) {// Initialize number of even digit sum to 0let count_even = 0;// Find block sizeblock = Math.floor(Math.sqrt(n));// Sort all queries so that queries of same blocks are arranged together.q.sort(compare);// Initialize current L, current R and current resultlet currL = 0, currR = 0;for (let i = 0; i < m; i++) {// L and R values of current rangelet L = q[i].L, R = q[i].R;// Add Elements of current rangewhile (currR <= R) { count_even = add(currR, a, count_even); currR++;}while (currL > L) { count_even = add(currL - 1, a, count_even); currL--;}// Remove element of previous rangewhile (currR > R + 1) { count_even = remove(currR - 1, a, count_even); currR--;}while (currL < L) { count_even = remove(currL, a, count_even); currL++;}q[i].even = count_even;}}// Function to display the results of queries in their initial orderfunction printResults(q, m) {q.sort(compare1);for (let i = 0; i < m; i++) {document.write(q[i].even);}}// Driver Codeconst arr = [5, 2, 3, 1, 4, 8, 10, 12];const n = arr.length;const q = [{ L: 1, R: 3, index: 0, even: 0 },{ L: 0, R: 4, index: 1, even: 0 },{ L: 4, R: 7, index: 2, even: 0 }] let m = q.length; queryResults(arr, n, q, m); printResults(q, m); |
Output
1 2 2
Time Complexity: O(Q x ?N)
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!
