You are given as input two arrays of integers, A[1 · · · n] and B[1 · · · n]; fo

ID: 3795049 • Letter: Y

Question

You are given as input two arrays of integers, A[1 · · · n] and B[1 · · · n]; for simplicity, let’s assume that each array consists of distinct integers. Give an O(n log n) time algorithm that tests if the two arrays consist of an equal set of integers, i.e., {A[1], A[2], · · · , A[n]}
= {B[1], B[2], · · · , B[n]}. For example, if A[1] = 1, A[2] = 2, B[1] = 2, B[2] = 1 (n = 2) then you should return ‘true’ since {A[1], A[2]} = {B[1], B[2]}, but if B[1] = 1, B[2] = 3, your answer should be ‘false.’

Explanation / Answer

Algorithm CheckEqual(A,B)
   Start
   if length(A) != length(B)
   return false;

     Temp = Array.Copy(A) //Create Copy of First Array as we dont want to disturb our array
     Sort The Temp Array //As it is the copy of First Array
      For each element in B
if(!BinarySearch( Element, Temp))
return false;
   return true;
End

1. Basically we are SORTING THE FIRST Array that Takes O(n log n) time.
2. Then we are checking for Each element in B (Total N elements ) and searching in sorted array(Temp) takes log N time, So here also NLog N

So Overall Time complexity is O(NlogN)

Thanks, let me know if there is anything.

Navigate

You are given as input a maze in the following format: • two integers h and w sp

You are given as set of n time intervals {(s_1, _1), (s_2, _2), .., (s_n, _n}).

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.

You are given as input two arrays of integers, A[1 · · · n] and B[1 · · · n]; fo

Question

Explanation / Answer

Related Questions

Navigate