 # Scalar Question (2)

Given a string S of zeroes and ones. Given range (L,R), you have to find the 1st and last occuring 1 in the range and tell the number of zeros between the first and last ones including L and R index.
1<=L,R<=10^5.
Eg:
0010011001
L,R=1,8
Output: 2

Pls help in this question. O(n^2) not working

I solved it using prefix sums.
Store the position of 1’s and take lower bound of each.

1 Like

Contest finished or running ??

1 Like

finished.

1 Like

Is there a way to solve these problems now ?

NOPE.

I did it by maintaining a array of total 0s till a particular index(lets say temp array) .
and also a vector for all 1s to shift my L,R to required index(1s ) in (log n) time. Then I first shifted my L,R accordingly and then just saw difference of value in temp array of L and R.
Hence Creating temp and 1s vector ->O(n)
each query ->O(log n)

1 Like

I maintained 3 array one prefix-sum array for 0s, next_pos_of_1 array, prev_pos_of_1 array and answered queries in O(1).
.
Can any one help with the Game question where you have to divide the bunch in equal parts

1 Like

Hint -> Try dividing such that for that very bundle no further division is possible for him

1 Like

using stack found position of next 1 and prev 1 for every index , simple prefix sums from here

1 Like

like dividing it to a prime . . . I tried it but can’t think more. any hint?

Do you know how to solve the 3rd and the 5th problem?

How to solve that permutation problem?

Can anyone explain me what 3rd problem(permutation wala) was asking for I was unable to understand the question?

Just a observation , If B has no factor between [C,B) ==>ans=0(can’t divide equally by 1st player).
if it has a factor ->. if (A is odd){return 1;} else {return 0;}
as can be proved easily try otherwise I will tell

@anonym_chef So, u find the sum between next_pos_of_1(from L) and prev_pos_of_1(from R) and than u do (R-L-prefix_sum) ? U did prefix sum using fenwick tree? then how u can answer queries in O(1), it will take logn
@knightknight

For eg, a,b,c=5,92,10 then ever if u finding prime factor, u can’t divide becaz after dividing quotent is less to C. factors of 92 = 46,23,4,2 but how can u divide ? @knightknight

No, not fenwik tree but I used prefix count array for 0s