Minimize sum of product of same | C ++ program to implement the above approach ; Function to print1 the arrays ; Function to reverse1 the subarray ; Function to calculate the minimum product of same - indexed elements of two given arrays ; Calculate initial product ; Traverse all odd length subarrays ; Remove the previous product ; Add the current product ; Check if current product is minimum or not ; Traverse all even length subarrays ; Remove the previous product ; Add to the current product ; Check if current product is minimum or not ; Update the pointers ; reverse1 the subarray ; print1 the subarray ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; void print1 ( vector < int > & a , vector < int > & b ) { int minProd = 0 ; for ( int i = 0 ; i < a . size ( ) ; ++ i ) { cout << a [ i ] << " ▁ " ; } cout << endl ; for ( int i = 0 ; i < b . size ( ) ; ++ i ) { cout << b [ i ] << " ▁ " ; minProd += a [ i ] * b [ i ] ; } cout << endl ; cout << minProd ; } void reverse1 ( int left , int right , vector < int > & arr ) { while ( left < right ) { int temp = arr [ left ] ; arr [ left ] = arr [ right ] ; arr [ right ] = temp ; ++ left ; -- right ; } } void minimumProdArray ( vector < int > & a , vector < int > & b , int l ) { int total = 0 ; for ( int i = 0 ; i < a . size ( ) ; ++ i ) { total += a [ i ] * b [ i ] ; } int min = INT_MAX ; int first = 0 ; int second = 0 ; for ( int i = 0 ; i < a . size ( ) ; ++ i ) { int left = i - 1 ; int right = i + 1 ; int total1 = total ; while ( left >= 0 && right < a . size ( ) ) { total1 -= a [ left ] * b [ left ] + a [ right ] * b [ right ] ; total1 += a [ left ] * b [ right ] + a [ right ] * b [ left ] ; if ( min >= total1 ) { min = total1 ; first = left ; second = right ; } -- left ; ++ right ; } } for ( int i = 0 ; i < a . size ( ) ; ++ i ) { int left = i ; int right = i + 1 ; int total1 = total ; while ( left >= 0 && right < a . size ( ) ) { total1 -= a [ left ] * b [ left ] + a [ right ] * b [ right ] ; total1 += a [ left ] * b [ right ] + a [ right ] * b [ left ] ; if ( min >= total1 ) { min = total1 ; first = left ; second = right ; } -- left ; ++ right ; } } if ( min < total ) { reverse1 ( first , second , a ) ; print1 ( a , b ) ; } else { print1 ( a , b ) ; } } int main ( ) { int n = 4 ; vector < int > a { 2 , 3 , 1 , 5 } ; vector < int > b { 8 , 2 , 4 , 3 } ; minimumProdArray ( a , b , n ) ; }