pH7's blog

By pH7, history, 6 weeks ago, In English

You are given two N size arrays A and B. Then you will have to answer Q queries : Given X -> If A[i] | B[j] = X for some i, j < N, print 1, else 0.

1 <= N, Q <= 100000 0 <= A[i], B[i] <= 100000

I tried to solve using trie, but i could not determine overall complexity. Can someone please help me solving this best possible way?

Note : This problem is not from any running contest.

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

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can we use modified FFT convolution?