Question

Phonepe | OA Coding Questions and Solutions | 2022 | Set-6

Answer 1

Smallest element of array B should be greater than or equal to Largest of array A. This can be done by reducing any element of A by 1 or increasing any element of B by 1, can be done multiple times. Output the minimum cost of operations. cost of each operation is 1.

 

A: 1 3 5
B: 4 7

 

Output : 1

 

A: 5 8 9 11
B: 1 3 4

 

Output : 20

Answer 2

I think you can think along this direction:-



Obtain the max element of A and min element of B.
Binary Search [The inputs are sorted in the example] or Simple search to get two bounds.
2.1 Find all the elements in B that are smaller than the largest element in A.
2.2 Find all the elements in A that are larger than smallest element of B.
After getting the bounds from above just calculate the cost for both the cases take the minimum one. The cost would basically be the total number of operations required for a bound to reach a particular element i.e. either max element of A or min element of B.


Time_Complexity:- O(N)

Answer 3

Consider all elements in A that are larger than the smallest element in B. Call this X. Consider all elements in B that are smaller than the largest element in A. Call this Y. We want a "middle point" m so that the cost of decreasing elements of X to m and increasing elements of Y to m is minimum. In other words, this m should minimize the sum of linear distance. It is well known that the median does this. So find the median of X union Y and compute the cost.