How to solve this problem ? DP ? BIT ? TRIE ?

Правка en3, от mtewathia99, 2020-11-13 16:03:14

Question :

Given 2 arrays 'A' and 'B' both of size 'N'. Make 'N' pairs ( A[ i ], B[ j ] ) such that :

  1. First element of pair should be from array 'A' and second element from array 'B'. ( we cannot make pair ( A[1], A[3] ) )
  2. An element cannot occur in more than one pair. { i.e for every 2 pairs ( A[i], B[j] ) , ( A[k], B[l] ) (i != k and j != l) }
  3. Let the value of a pair be the XOR of first and second element of the pair, value of all the pairs formed must be equal.

Constraints : 0 <= A[i], B[i] <= 10^9 __________ ( 1 <= i <= N )

( Consider N even as the problem can be solved for odd N in O(N) easily )

How to solve it in less than O(N^2) Time Complexity ?

If not possible return -1

Теги coding interviews, #interview

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en3 Английский mtewathia99 2020-11-13 16:03:14 78 Tiny change: 'olved for Odd N in O(N) )\n\n![ ]' -> 'olved for odd N in O(N) easily )\n\n![ ]'
en2 Английский mtewathia99 2020-11-12 22:43:53 30 Tiny change: 'xity ?\n\n' -> 'xity ?\n\nIf not possible Print -1;\n\n'
en1 Английский mtewathia99 2020-11-12 20:59:48 752 Initial revision (published)