Question

Suppose you have two arrays: Arr1 and Arr2. Arr1 will be sorted values. For each element v in Arr2, you need to write a pseudo code that will print the number of elements in Arr1 that is less than or equal to v. For example: suppose you are given two arrays of size 5 and 3 respectively. 5 3 [size of the arrays] Arr1 = 1 3 5 7 9 Arr2 = 6 4 8 The output should be 3 2 4 Explanation: Firstly, you should search how many numbers are there in Arr1 which are less than 6. There are 1, 3, 5 which are less than 6 (total 3 numbers). Therefore, the answer for 6 will be 3. After that, you will do the same thing for 4 and 8 and output the corresponding answers which are 2 and 4. Your searching method should not take more than O (log n) time. Sample Input Sample Output 5 5 1 1 2 2 5 3 1 4 1 5 4 2 4 2 5

Answer 1

Answer:

The algorithm is as follows:

1. Declare Arr1 and Arr2

2. Get Input for Arr1 and Arr2

3. Initialize count to 0

4. For i in Arr2

4.1 For j in Arr1:

4.1.1 If i > j Then

4.1.1.1 count = count + 1

4.2 End j loop

4.3 Print count

4.4 count = 0

4.5 End i loop

5. End

Explanation:

This declares both arrays

1. Declare Arr1 and Arr2

This gets input for both arrays

2. Get Input for Arr1 and Arr2

This initializes count to 0

3. Initialize count to 0

This iterates through Arr2

4. For i in Arr2

This iterates through Arr1 (An inner loop)

4.1 For j in Arr1:

This checks if current element is greater than current element in Arr1

4.1.1 If i > j Then

If yes, count is incremented by 1

4.1.1.1 count = count + 1

This ends the inner loop

4.2 End j loop

Print count and set count to 0

4.3 Print count

4.4 count = 0

End the outer loop

4.5 End i loop

End the algorithm

5. End