Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Binary Game

By Nasif_44th · Limits 1s, 512 MB

Alice and Bob love to play with numbers, one day they found an array with NN integers consisting of only 00 and 11. Alice wants to play a range query game with Bob. Alice will give Bob a range from LL to RR. Bob needs to tell her who wins 00 or 11. For 00 to win, the occurrence of 00 in the given range must be strictly greater than that of 11.


The first line of the input contains an integer N(1N105)N \hspace{.1cm} (1 \leq N \leq 10^5) denoting the number Integers in the array and an integer Q(1Q105)Q \hspace{.1cm} (1 \leq Q \leq 10^5) denoting the number of queries.

It is followed by a line having NN integers, Ai(0Ai1)A_i \hspace{.1cm} (0 \leq A_i \leq 1) denoting the array.

The following QQ lines will have two integers LL and R(1LRN)R \hspace{.1cm} (1 \leq L \leq R \leq N).


For each query, if 00 is the winner then output should be 00, otherwise 11.


10 3
0 1 0 1 1 0 0 0 0 0	
5 10
1 5
1 10

For the first query, from 55 to 1010, there are 55 zeros and 11 one, so the winner is zero.

For the second query, from 11 to 55, there are 22 zeros and 33 ones, so 11 is the winner.



    75% Solution Ratio

    steinumEarliest, Oct '20

    prodip_bsmrstuFastest, 0.0s

    tarek007Lightest, 524 kB

    Being_GoromShortest, 307B


    Login to submit


    At first find the cumulative sum of the given array. After that for each query find the sum of the g...

    Toph uses cookies. By continuing you agree to our Cookie Policy.