# Maximum Scalar Product

18 July 2022

Given 2 integer arrays X and Y of same size. Consider both arrays as vectors and print the maximum scalar product ( Dot product ) of 2 vectors.

If you are from 2023 batch student, Join our Telegram group for placement preparation and coming placement drive updates : https://t.me/talentbattle2023

# Discription

Sample input 1:

4

1 2 3 4

5 6 7 8

Sample output 1:

70

Explanation :

(8*4 + 7*3 + 6*2 + 1*5)  = 70

Sample input 2:

4

-1 -2 -3 -4

5 6 -7 -8

Sample output 2:

37

Explanation :

(-4*-8 + -3*-7 + -2*5 + -1*6) = 37

Solution:

C Program

#include <stdio.h>

#include <limits.h>

// SpecialSort function sorts negetive numbers in array1 in ascending order

// and positive numbers and zero in descending order

void swap(int *x, int *y)

{

int temp = *x;

*x = *y;

*y = temp;

}

void SpecialSort(int *vec1,int n)

{

for(int i = 0 ; i < n-1 ; i++)

{

for(int k = 0 ; k<n-1-i ; k++)

{

if(vec1[k] < vec1[k+1])

{

swap(&vec1[k],&vec1[k+1]);

}

}

}

for(int i = 0 ; i<n ; i++)

{

printf("%d ",vec1[i]);

}

printf("\n");

int idx=0;

while(vec1[idx] >=0)

{

idx++;

}

int start = idx,end = n-1;

while(start<end)

{

swap(&vec1[start],&vec1[end]);

start++;end--;

}

for(int i = 0 ; i<n ; i++)

{

printf("%d ",vec1[i]);

}

printf("\n\n");

}

// Find min product and move the elements to left side of both arrays

int MaximumScalarProduct(int *vec1,int *vec2,int n)

{

int max,sop=0,id1,id2;

for(int i = 0 ; i<n ; i++)

{

max = INT_MIN;

for(int j = i ; j<n ; j++)

{

if((vec1[i]*vec2[j]) > max)

{

max = vec1[i]*vec2[j];

id1 = i; id2 = j;

}

}

sop = sop + max;

swap(&vec1[i],&vec1[id1]);

swap(&vec2[i],&vec2[id2]);

for(int i = 0 ; i<n ; i++)

{

printf("%d ",vec1[i]);

}

printf("\n");

for(int i = 0 ; i<n ; i++)

{

printf("%d ",vec2[i]);

}

printf("\n\n");

}

return sop;

}

int main()

{

int n;            scanf("%d",&n);

int vec1[n];

for(int i = 0 ; i<n ; i++)

{

scanf("%d",&vec1[i]);

}

int vec2[n];

for(int i = 0 ; i<n ; i++)

{

scanf("%d",&vec2[i]);

}

SpecialSort(vec1,n);

printf("%d",MaximumScalarProduct(vec1,vec2,n));

return 0;

}

C++ Program

#include <bits/stdc++.h>

using namespace std;

// SpecialSort function sorts negetive numbers in array1 in ascending order

// and positive numbers and zero in descending order

void SpecialSort(int vec1[],int n)

{

int idx=0;

sort(vec1,vec1+n, greater<int>());

while(vec1[idx] >= 0)

{

idx++;

}

int start = idx,end = n-1;

while(start<end)

{

swap(vec1[start],vec1[end]);

start++;end--;

}

}

// Find min product and move the elements to left side of both arrays

int MaximumScalarProduct(int vec1[],int vec2[],int n)

{

int min,sop=0,id1,id2;

for(int i = 0 ; i<n ; i++)

{

max = INT_MIN;

for(int j = i ; j<n ; j++)

{

if((vec1[i]*vec2[j]) > max)

{

max = vec1[i]*vec2[j];

id1 = i; id2 = j;

}

}

sop = sop + max;

swap(vec1[i],vec1[id1]);

swap(vec2[i],vec2[id2]);

}

return sop;

}

int main()

{

int n;            cin>>n;

int vec1[n];

for(int i = 0 ; i<n ; i++)

{

cin>>vec1[i];

}

int vec2[n];

for(int i = 0 ; i<n ; i++)

{

cin>>vec2[i];

}

SpecialSort(vec1,n);

cout<<MaximumScalarProduct(vec1,vec2,n);

return 0;

}

JAVA Program

import java.util.*;

import java.lang.*;

import java.io.*;

class Main

{

static void swap(int arr[],int start, int end)

{

int temp = arr[start];

arr[start] = arr[end];

arr[end] = temp;

}

// SpecialSort function sorts negetive numbers in array1 in ascending order

// and positive numbers and zero in descending order

static void SpecialSort(int vec1[],int n)

{

Arrays.sort(vec1, Collections.reverseOrder());

int idx=0;

while((idx<n) && (vec1[idx] >= 0))

{

idx++;

}

int start = idx,end = n-1;

while(start<end)

{

swap(vec1,start,end);;

start++;end--;

}

}

// Find min product and move the elements to left side of both arrays

static int MaximumScalarProduct(int vec1[], int vec2[], int n)

{

int max,sop=0;

int id1=0,id2=0;

for(int i = 0 ; i<n ; i++)

{

max = Integer.MIN_VALUE;

for(int j = i ; j<n ; j++)

{

if((vec1[i]*vec2[j]) > max)

{

max = vec1[i]*vec2[j];

id1 = i; id2 = j;

}

}

sop = sop + max;

swap(vec1,i,id1);

swap(vec2,i,id2);

}

return sop;

}

public static void main(String[] args) throws java.lang.Exception

{

Scanner sc = new Scanner(System.in);

int n = sc.nextInt();

int vec1[] = new int[n];

for(int i = 0 ; i<n ; i++)

{

vec1[i] = sc.nextInt();

}

int vec2[] = new int[n];

for(int i = 0 ; i<n ; i++)

{

vec2[i] = sc.nextInt();

}

SpecialSort(vec1,n);

System.out.print(MaximumScalarProduct(vec1,vec2,n));

}

}

Python

def swap(vec1, pos1, pos2):

vec1[pos1], vec1[pos2] = vec1[pos2], vec1[pos1]

def SpeecialSort(vec1,n):

vec1.sort(reverse=True)

idx=0

while idx<n and vec1[idx] >= 0 :

idx=idx+1

start = idx

end = n-1

while(start<end):

swap(vec1, start, end)

start = start + 1

end = end + 1

def MaximumScalarProduct(vec1,vec2,n):

sop=0

for i in range(0,n):

max = 2147483647

for j in range(i,n):

if(vec1[i]*vec2[j]) > max :

max = vec1[i]*vec2[j]

id1 = i

id2 = j

sop = sop + max

swap(vec1,i,id1)

swap(vec2,i,id2)

return sop

n = int(input())

vec1 = list(map(int,input().split(' ')))

vec2 = list(map(int,input().split(' ')))

SpeecialSort(vec1,n)

print(MaximumScalarProduct(vec1,vec2,n))

If you are from 2023 batch student, Join our Telegram group for placement preparation and coming placement drive updates : https://t.me/talentbattle2023