2 very innocent looking problems(asked in Google online round on 10/7/21)
Разница между en1 и en2, 2 символ(ов) изменены
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!

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский randomx_123 2021-07-11 12:49:45 2
en1 Английский randomx_123 2021-07-11 12:49:15 1315 Initial revision (published)