Queries to answer the number of ones and zero to the left of given index | C ++ implementation of the approach ; Function to pre - calculate the left [ ] array ; Iterate in the binary array ; Initialize the number of 1 and 0 ; Increase the count ; Driver code ; Queries ; Solve queries
#include <bits/stdc++.h> NEW_LINE using namespace std ; void preCalculate ( int binary [ ] , int n , pair < int , int > left [ ] ) { int count1 = 0 , count0 = 0 ; for ( int i = 0 ; i < n ; i ++ ) { left [ i ] . first = count1 ; left [ i ] . second = count0 ; if ( binary [ i ] ) count1 ++ ; else count0 ++ ; } } int main ( ) { int binary [ ] = { 1 , 1 , 1 , 0 , 0 , 1 , 0 , 1 , 1 } ; int n = sizeof ( binary ) / sizeof ( binary [ 0 ] ) ; pair < int , int > left [ n ] ; preCalculate ( binary , n , left ) ; int queries [ ] = { 0 , 1 , 2 , 4 } ; int q = sizeof ( queries ) / sizeof ( queries [ 0 ] ) ; for ( int i = 0 ; i < q ; i ++ ) cout << left [ queries [ i ] ] . first << " ▁ ones ▁ " << left [ queries [ i ] ] . second << " ▁ zeros STRNEWLINE " ; return 0 ; }