Minimize the sum of product

PROBLEM :
Given two arrays, A and B, of equal size n, the task is to find the minimum value  of A[0] * B[0] + A[1] * B[1] +…+ A[n-1] * B[n-1], where shuffling of elements of arrays A and B is allowed.

Examples:
Input : A[] = {3, 1, 1} and B[] = {6, 5, 4}.
Output : 23 Minimum value of S = 1*6 + 1*5 + 3*4 = 23.

Input : A[] = { 6, 1, 9, 5, 4 } and B[] = { 3, 4, 8, 2, 4 }
Output : 80. Minimum value of S = 1*8 + 4*4 + 5*4 + 6*3 + 9*2 = 80.


Input:
The first line of input contains an integer denoting the no of test cases. Then T test cases follow. Each test case contains three lines. The first line of input contains an integer N denoting the size of the arrays. In the second line are N space separated values of the array A[], and in the last line are N space separated values of the array B[].

Output:
For each test case in a new line print the required result.

Constraints:
1<=T<=100
1<=N<=50
1<=A[]<=20

Example:
Input:
2
3
3 1 1
6 5 4
5
6 1 9 5 4
3 4 8 2 4

Output:
23
80

--------------------------------------------------------------------------------
SIMPLE c++ IMPLEMENTATION :
--------------------------------------------------------------------------------

#include<iostream>
using namespace std;
#include<algorithm>
#define max 200
int main()
{
int arr1[max],arr2[max] ;
int n,t,i ;
cin>>t  ;
while(t--)
{
   cin>>n ;
   for(i=0;i<n;i++)
       cin>>arr1[i] ;
   for(i=0;i<n;i++)
       cin>>arr2[i] ;
     
   sort(arr1,arr1+n) ;
   sort(arr2,arr2+n,greater<int>()) ;
 
   int sum=0 ;
   for(i=0;i<n;i++)
       sum+=arr1[i]*arr2[i] ;

 
   cout<<sum<<endl ;
}
return 0;
}

---------------------------------------------------------------------------------

Comments

Popular posts from this blog

Count ways to N'th Stair(Order does not matter)

Replace all ‘0’ with ‘5’ in an input Integer

Chocolate Distribution Problem

Remove characters from the first string which are present in the second string

Primality Test ( CodeChef Problem code: PRB01 )