Range Queries for count of Armstrong numbers in subarray using MO 's algorithm | C ++ implementation to count the number of Armstrong numbers in subarray using MOaTMs algorithm ; Variable to represent block size . This is made global so compare ( ) of sort can use it . ; Structure to represent a query range ; Count of Armstrong numbers ; To store the count of Armstrong numbers ; 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 . ; Different blocks , sort by block . ; Same block , sort by R value ; 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 ; Function that return true if num is armstrong else return false ; Function to Add elements of current range ; If a [ currL ] is a Armstrong number then increment count_Armstrong ; Function to remove elements of previous range ; If a [ currL ] is a Armstrong number then decrement count_Armstrong ; Function to generate the result of queries ; Initialize count_Armstrong to 0 ; Find block size ; Sort all queries so that queries of same blocks are arranged together . ; Initialize current L , current R and current result ; L and R values of current range ; Add Elements of current range ; Remove element of previous range ; Function to display the results of queries in their initial order ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; int block ; struct Query { int L , R , index ; int armstrong ; } ; int count_Armstrong ; bool compare ( Query x , Query y ) { if ( x . L / block != y . L / block ) return x . L / block < y . L / block ; return x . R < y . R ; } bool compare1 ( Query x , Query y ) { return x . index < y . index ; } bool isArmstrong ( int x ) { int n = to_string ( x ) . size ( ) ; int sum1 = 0 ; int temp = x ; while ( temp > 0 ) { int digit = temp % 10 ; sum1 += pow ( digit , n ) ; temp /= 10 ; } if ( sum1 == x ) return true ; return false ; } void add ( int currL , int a [ ] ) { if ( isArmstrong ( a [ currL ] ) ) count_Armstrong ++ ; } void remove ( int currR , int a [ ] ) { if ( isArmstrong ( a [ currR ] ) ) count_Armstrong -- ; } void queryResults ( int a [ ] , int n , Query q [ ] , int m ) { count_Armstrong = 0 ; block = ( int ) sqrt ( n ) ; sort ( q , q + m , compare ) ; 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 ] . armstrong = count_Armstrong ; } } void printResults ( Query q [ ] , int m ) { sort ( q , q + m , compare1 ) ; for ( int i = 0 ; i < m ; i ++ ) { cout << q [ i ] . armstrong << endl ; } } int main ( ) { int arr [ ] = { 18 , 153 , 8 , 9 , 14 , 5 } ; int n = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; Query q [ ] = { { 0 , 5 , 0 , 0 } , { 3 , 5 , 1 , 0 } } ; int m = sizeof ( q ) / sizeof ( q [ 0 ] ) ; queryResults ( arr , n , q , m ) ; printResults ( q , m ) ; return 0 ; }