The_DarkKnight's blog

A question that I am stuck in
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?

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

»
3 years ago, # |
  Vote: I like it +9 Vote: I do not like it

Kindly add the link of the problem!

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    sorry I dont have a link. My friend asked me this question

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +2 Vote: I do not like it

      no link no help

      → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +12 Vote: I do not like it

      Usually, ppl ask for links to make sure that that problem is not from an ongoing contest or from a placement round.

      → Reply