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
Related Articles

Ask Us Anything !