10.
Search in a Rotated Array
Given a sorted and rotated array A of N distinct elements which is rotated at some point, and given
an element K. The task is to find the index of the given element K in the array A.
Input:
The first line of the input contains an integer T, denoting the total number of test cases. Then T test
cases follow. Each test case consists of three lines. First line of each test case contains an
integer N denoting the size of the given array. Second line of each test case contains N space
separated integers denoting the elements of the array A. Third line of each test case contains an
integer K denoting the element to be searched in the array.
Output:
Corresponding to each test case, output the index of the element found in the array. If element is
not present, then output -1.
Constraints:
1 ≤ T ≤ 100
1 ≤ N ≤ 107
0 ≤ Ai ≤ 108
1 ≤ K ≤ 108
Example:
Input:
3
9
5 6 7 8 9 10 1 2 3
10
3
312
1
4
3512
6
Output:
5
1
-1
Explanation:
Testcase 1: 10 is found at index 5.
11. Minimum Swaps to Sort
Given an array of N distinct elements A[ ]. The task is to find the minimum number of swaps required
to sort the array. Your are required to complete the function which returns an integer denoting the
minimum number of swaps, required to sort the array.
Input:
The first line of input contains an integer T denoting the no of test cases . Then T test cases follow .
Each test case contains an integer N denoting the no of element of the array A[ ]. In the next line are
N space separated values of the array A[ ] .
Output:
For each test case in a new line output will be an integer denoting minimum umber of swaps that
are required to sort the array.
Constraints:
1 <= T <= 100
1 <= N <= 103
1 <= A[] <= 104
Input:
2
4
4321
5
15432
Output:
2
2
Explanation:
Testcase 1: We need two swaps, swap 1 with 4 and 3 with 2 to make it sorted.
12. Sorting Elements of an Array by Frequency
Given an array A[] of integers, sort the array according to frequency of elements. That is elements
that have higher frequency come first. If frequencies of two elements are same, then smaller
number comes first.
Input:
The first line of input contains an integer T denoting the number of test cases. The description of T
test cases follows. The first line of each test case contains a single integer N denoting the size of
array. The second line contains N space-separated integers A 1, A2, ..., AN denoting the elements of
the array.
Output:
For each testcase, in a new line, print each sorted array in a seperate line. For each array its numbers
should be seperated by space.
Constraints:
1 ≤ T ≤ 70
30 ≤ N ≤ 130
1 ≤ Ai ≤ 60
Example:
Input:
2
5
55464
5
99925
Output:
44556
99925
Explanation:
Testcase1: The highest frequency here is 2. Both 5 and 4 have that frequency. Now since the
frequencies are same then smaller element comes first. So 4 4 comes first then comes 5 5. Finally
comes 6.
The output is 4 4 5 5 6.
Testcase2: The highest frequency here is 3. The element 9 has the highest frequency. So 9 9 9 comes
first. Now both 2 and 5 have same frequency. So we print smaller element first.
The output is 9 9 9 2 5.
