4
Problem # 4
You are given two arrays A and B which contain integer in the range of 1 to M.(array may contain
duplicate elements). You need to print how many elements of A are not in B.
Constraint : M
2
4.1
Input Specification
Integer N followed by N test cases. Each test case will be of five lines, first line will be an integer M
(maximum range of the arrays), second line will be an integer NA (size of the array A), next line
will contain the array A in space separated format. Next line will be an integer NB (size of array
B), the line after that will contain the Array B in space separated format.
4.2
Output Specification
For each test case, print the number of elements of A, which are not present in B.
4.3
Sample Input
1
10
4
2 10 1 9
5
39547
4.4
Sample Output
3
5
Problem # 5
You are given an array A of size N such that one particular element occurs more than N/2 times
in this array. Find this element.
Constraint : Your solution should be O(N ).
5.1
Input Specification
Integer N followed by N test cases. Each test case consists of two lines, first line contains the integer
NA (size of the array A) and second line contains the array A in space separated format.
5.2
Output Specification
For each test case output a single line containing the desired element.
5.3
Sample Input
3
4
3233
7
12 12 9 8 12 12 11
10
1234544444
3
5.4
Sample Output
3
12
4
6
Problem # 6
You are given two strings s1 and s2 , each consisting of distinct characters. Also s2 contains a subset
of characters of s1 . Find all permutations of characters of string s1 such that s2 is not a substring
of any of these permutations.
Note : You are supposed to output the permutations in lexicographic order.
6.1
Input Specification
Integer N followed by N test cases. Each test case consists of two lines, the first line contains the
string s1 and second line contains the string s2 .
6.2
Output Specification
For each test case output the permutations one after the other in lexicographic order. Output each
permutation on a separate line.
6.3
Sample Input
1
abcd
bcd
6.4
Sample Output
abdc
acbd
acdb
adbc
adcb
bacd
badc
bcad
bdac
bdca
cabd
cadb
cbad
cbda
cdab
cdba
dabc
dacb
dbac
dbca
4
dcab
dcba