So I gave the on-campus Google hiring test yesterday and when I saw the 2 problems I had to solve in an hour, I was really excited since they looked doable. However, things took a turn when I actually started to think about optimizations. Anyways, here goes :

Problem -1

We have an array A of N elements. We will be asked Q queries. each query is in the form of a single integer, X, and we have to tell whether there exists an index i in the array such that the bitwise AND of A[i] and X equals 0. If such an index exists print YES, otherwise print NO.

Constraints : 1<=N<=1e5, 1<=Q<=1e5, 1<=A[i]<=1e5

Problem 2

We have a binary string S of length N, and we have to find the number of substrings(that is, a contiguous range i to j) in which the frequency of 1 is strictly greater than the frequency of 0.

Constraints : 1<=N<=1e6;

I have spent a lot of time on them but could not come up with an optimal approach for either. I realize that the 2nd problem can be solved in O(NlogN) in a similar fashion in which we solve LIS in NlogN time, But other than that, I am clueless about both problems. Any help will be appreciated, Thanks!