Number of indexes with equal elements in given range | CPP program to count the number of indexes in range L R such that Ai = Ai + 1 ; array to store count of index from 0 to i that obey condition ; precomputing prefixans [ ] array ; traverse to compute the prefixans [ ] array ; function that answers every query in O ( 1 ) ; Driver Code ; pre - computation ; 1 - st query ; 2 nd query
#include <bits/stdc++.h> NEW_LINE using namespace std ; const int N = 1000 ; int prefixans [ N ] ; int countIndex ( int a [ ] , int n ) { for ( int i = 0 ; i < n ; i ++ ) { if ( a [ i ] == a [ i + 1 ] ) prefixans [ i ] = 1 ; if ( i != 0 ) prefixans [ i ] += prefixans [ i - 1 ] ; } } int answer_query ( int l , int r ) { if ( l == 0 ) return prefixans [ r - 1 ] ; else return prefixans [ r - 1 ] - prefixans [ l - 1 ] ; } int main ( ) { int a [ ] = { 1 , 2 , 2 , 2 , 3 , 3 , 4 , 4 , 4 } ; int n = sizeof ( a ) / sizeof ( a [ 0 ] ) ; countIndex ( a , n ) ; int L , R ; L = 1 ; R = 8 ; cout << answer_query ( L , R ) << endl ; L = 0 ; R = 4 ; cout << answer_query ( L , R ) << endl ; return 0 ; }