Program to find the minimum scalar product of two vectors (dot product) | faceprep

Program to find the minimum scalar product of two vectors (dot product) is discussed here. Given two arrays, find the minimum scalar product of all permutations of the two given arrays.

Sample Input 1:
3 (Number of elements of the array)
1 3 5 (Array 1 elements)
2 4 1 (Array 2 elements)

Sample Output 1:
15 

Calculation:

Minimum scalar product  = 1 * 4 + 3 * 2 + 5 * 1 
                                                         = 4 + 6 + 5
                                                         = 15

Sample Input 2: 
5
1 2 3 4 5
1 0 1 0 1

Sample Output 2:
6

Calculation:

Minimum scalar product  = 5 * 0 + 4 * 0 + 3 * 1 + 2 * 1 + 1 * 1 
                                                         = 0 + 0 + 3 + 2 + 1
                                                         = 6

Algorithm to find the minimum scalar product of two vectors

  • Input the number of elements of the arrays.
  • Input the array 1 and array 2 elements.
  • Initialize sum = 0.
  • Sort the array 1 in ascending order.
  • Sort the array 2 in descending order.
  • Repeat from i = 1 to n
  • sum = sum + (arr1[i] * arr2[i])
  • Return sum.

Program to find the minimum scalar product of two vectors (dot product) is given below.

// C Program to find the minimum scalar product of two vectors (dot product)
#include<stdio.h>

int sort(int arr[], int n)
{
int i, j;
for (i = 0; i < n-1; i++)
for (j = 0; j < n-i-1; j++)
if (arr[j] > arr[j+1])
{
int temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}

int sort_des(int arr[], int n)
{
int i,j;
for (i = 0; i < n; ++i)
{
for (j = i + 1; j < n; ++j)
{
if (arr[i] < arr[j])
{
int a = arr[i];
arr[i] = arr[j];
arr[j] = a;
}
}
}
}

int main()
{
//fill the code;
int n;
scanf(“%d”,&n);
int arr1[n], arr2[n];
int i;
for(i = 0; i < n ; i++)
{
scanf(“%d”,&arr1[i]);
}
for(i = 0; i < n ; i++)
{
scanf(“%d”,&arr2[i]);
}

sort(arr1, n);
sort_des(arr2, n);
int sum = 0;
for(i = 0; i < n ; i++)
{
sum = sum + (arr1[i] * arr2[i]);
}
printf(“%d”,sum);
return 0;
}

// C++ Program to find the minimum scalar product of two vectors (dot product)
#include<bits/stdc++.h>
using namespace std;

int main()
{
//fill the code;
int n;
cin >> n;
int arr1[n], arr2[n];
int i;
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 = sum + (arr1[i] * arr2[i]);
}
cout << sum;
return 0;
}

// Java Program to find the minimum scalar product of two vectors (dot product)

import java.util.*;
import java.util.Arrays;
import java.util.Collections;

public class Main
{
static void sort_des(int arr[], int n)
{
int i,j;
for (i = 0; i < n; ++i)
{
for (j = i + 1; j < n; ++j)
{
if (arr[i] < arr[j])
{
int a = arr[i];
arr[i] = arr[j];
arr[j] = a;
}
}
}
}

public static void main(String[] args)
{
int n;
Scanner sc = new Scanner(System.in);
System.out.print(“\nEnter the number of elements of the array : “);
n = sc.nextInt();
int[] arr1 = new int[n];
int[] arr2 = new int[n];
System.out.print(“\nInput the array 1 elements : “);
int i;

for(i = 0; i < n ; i++)
{
arr1[i] = sc.nextInt();
}

System.out.print(“\nInput the array 2 elements : “);
for(i = 0; i < n ; i++)
{
arr2[i] = sc.nextInt();
}
Arrays.sort(arr1);
sort_des(arr2,n);
int sum = 0;
for(i = 0; i < n ; i++)
{
sum = sum + (arr1[i] * arr2[i]);
}
System.out.println(“\nMinimum Scalar Product : ” + sum);
}
}

# Python program to find the minimum scalar product of two vectors

n = int(input())
arr1 = []
arr2 = []
for i in range(0,n):
temp = int(input())
arr1.append(temp)

for i in range(0,n):
temp = int(input())
arr2.append(temp)

arr1.sort()
arr2.sort(reverse=True)
sum = 0

for i in range(0, n):
sum = sum + (arr1[i] * arr2[i])

print(“Minimum Scalar Product :”,sum)

#include<stdio.h>
#include<stdlib.h>
int i,j,temp;
int* createarray(int);
int getelements(int*,int);
int ascending(int*,int);
int minscalar(int*,int*,int);
int main()
{
int n,*a,*b;
scanf(“%d”,&n);
a=createarray(n);
getelements(a,n);
b=createarray(n);
getelements(b,n);
ascending(a,n);
ascending(b,n);
minscalar(a,b,n);
return 0;
}
int* createarray(int n)
{
int *a;
a=(int*)malloc(n*sizeof(int));
return a;
}
int getelements(int *a,int n)
{
for(i=0;i<n;i++)
scanf(“%d”,a+i);
return 0;
}
int ascending(int *a,int n)
{
for(i=0;i<n;i++)
{
for(j=i+1;j<n;j++)
{
if(*(a+i)>*(a+j))
{
temp=*(a+i);
*(a+i)=*(a+j);
*(a+j)=temp;

}
}
}
return 0;
}
int minscalar(int *a,int *b,int n)
{
int sum=0,p,q;
for(i=0;i<n;i++)
{
p=*(a+i);
q=*(b+n-1-i);
sum=sum+(p*q);
}

printf(“%d”,sum);
return 0;
}

Output:

Minimum scalar product of two vectors