Question

Given two integer arrays, A and B of length n each, write an efficient algotihm to find an integer that occurs the same number of times in both A and B.

extra:

solve this recurrence: T(1) = 1; T(n) = T(n/4) + n

Answer 1

Hi, I have answered Q1.

Please repost others in separate post.

Given two integer arrays, A and B of length n each, write an efficient algotihm to find an integer that occurs the same number of times in both A and B.

Algorithm:

Step 1:
   prepare HashMap of elements of A
   mapA = createHashMap
   for i=1 to n do:
       if A[i] is in mapA then do:
           increase count of A[i]
       else:
           add A[i] in mapA with count 1

Step2:
   prepare HashMap of elements of B
   mapB = createHashMap
   for i=1 to n do:
       if B[i] is in mapB then do:
           increase count of B[i]
       else:
           add B[i] in mapB with count 1

Step 3:
  
   traverse any one of the array , A or B
   Lets traverse A
   for i =1 to n do:
       if count of A[i] is in mapA and mapB is same then:
           return A[i]

Time complexity: O(N)
Space complexity: O(N)