The_DarkKnight's blog

By The_DarkKnight, history, 3 years ago, In English

I recently came across a question that reads as follows:

We are given n pairs of number: (a1,b1), (a2,b2)....(an,bn).

We need to find if there exists n numbers : x1,x2...xn such that a_i <= x_i <= b_i and (x1 & x2 & ....xn = 0) where & denotes bitwise and.

Constraints:

1<=n<=10^5

1<=a_i,b_i<=10^9

I thought of check for each bit if it becomes zero in each interval. But that is wrong as two bits can become zero in an interval but not necessarily at the same number.

How to proceed with this?

Full text and comments »

  • Vote: I like it
  • +9
  • Vote: I do not like it