SMPSEQ4 - Fun with Sequences (Act 2)
You are given a sorted sequence of n integers S = s1, s2, ..., sn and a sorted sequence of m integers Q = q1, q2, ..., qm. Please, print in the ascending order all such si that belongs to Q.
Input data specification
In the first line you are given one integer 2<=n<=100,
and in the following line n integers:
-100 <= si <= 100, si <= si+1.
In the third line you are given one integer 2<=m<=100,
and in the following line m integers:
-100 <= qi <= 100, qi <= qi+1.
Output data specification
The sequence of requested integers separated by spaces.
Input: 5 -2 -1 0 1 4 6 -3 -2 -1 1 2 3 Output: -2 -1 1
using binary search gives time complexity- n(logm). Is this correct?
Take care Binary Search is best solution, but not gonna work in duplicated values
Solve SMPSEQ3 to solve this problem.
at first you need to solve the previous question..
I have used binary search. It's not working for me. Can anyone tell me what might be wrong with my code?
Compares to this http://www.spoj.com/problems/SMPSEQ3/ I added only one character in my code which is "!"... Problem would be more interesting if there were more test cases and/or numbers in sequences. For n, m <= 100 brute force is quick enough.