Maximize sum of Averages of Pairs made utilizing components of X [] and Y []

Given two arrays X[] and Y[] of size N every. You may make a pair by deciding on precisely one component from X[] and Y[]. The duty is to seek out the utmost sum of averages by making N pairs.

Examples:

Enter: N = 3, X[] = {6, 5, 4}, Y[] = {3, 1, 2}
Output: 10
Clarification: One of many doable technique to organize pairs is: (4, 2) (5, 1) (6, 3), Which supplies common as ((4 + 2) / 2),  ((1 + 5) / 2), ((6 + 3) / 2), Which is the same as 3, 3 and 4 respectively. Complete sum of common is: 3 + 3 + 4 = 10. Which is most doable.

Enter: N = 5, X[] = {4, 8, 3, 2, 1}, Y[] = {2, 5, 1, 2, 3}
Output: 15
Clarification: It may be verified that no different association of pairs give sum of common greater than 15.

Strategy: Implement the thought beneath to resolve the issue:

The issue could be solved through counting variety of odd components current in X[] and Y[]. Components for calculating most doable common will probably be: (Complete sum of components of X[] and Y[] – Absolute distinction(rely of strange components in X[] – rely of strange components in Y[])) / 2.

The second time period is subtracted as a result of there will probably be that many pairs the place one component is odd and the opposite is even. And in case of every such pair we unfastened the worth equal to 0.5 from the sum of averages.

Illustration of strategy:

Think about an instance: N = 5, X[] = {4, 8, 3, 2, 1}, Y[] = {2, 5, 1, 2, 3}

• Complete sum of components of X[] = 4 + 8 + 3 + 2 + 1 = 18
• Complete sum of components of Y[] = 2 + 5 + 1 + 2 + 3 = 13
• Complete sum of each arrays = 18 + 13 = 31
• Depend of strange components in X[] = 2(3, 1)
• Depend of strange components in Y[] = 3(5, 1, 3) 
• Complete common of pairs will probably be: 
  (complete sum of each arrays – absolute distinction(odd rely of X[] – odd rely of Y[]))/2 = (31 – |2 – 3|) / 2 = (31 – 1) / 2 = 30 / 2 = 15.

That is the utmost doable sum of averages on this case.

Observe the steps talked about beneath to resolve the issue:

• Receive the whole sum of components of each X[] and Y[].
• Depend the variety of odd components in X[].
• Depend the variety of odd components in Y[].
• Print the output in accordance with mentioned components.

Under is the code to implement the strategy:

Time Complexity: O(N)
Auxiliary House: O(1)