Minimize sum of product of same | Java Program to implement the above approach ; Function to print the arrays ; Function to reverse 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 ; Reverse the subarray ; Print the subarray ; Driver Code
import java . io . * ; import java . util . * ; public class Main { static void print ( long a [ ] , long b [ ] ) { int minProd = 0 ; for ( int i = 0 ; i < a . length ; ++ i ) { System . out . print ( a [ i ] + " ▁ " ) ; } System . out . println ( ) ; for ( int i = 0 ; i < b . length ; ++ i ) { System . out . print ( b [ i ] + " ▁ " ) ; minProd += a [ i ] * b [ i ] ; } System . out . println ( ) ; System . out . println ( minProd ) ; } static void reverse ( int left , int right , long arr [ ] ) { while ( left < right ) { long temp = arr [ left ] ; arr [ left ] = arr [ right ] ; arr [ right ] = temp ; ++ left ; -- right ; } } static void minimumProdArray ( long a [ ] , long b [ ] , int l ) { long total = 0 ; for ( int i = 0 ; i < a . length ; ++ i ) { total += a [ i ] * b [ i ] ; } long min = Integer . MAX_VALUE ; int first = 0 ; int second = 0 ; for ( int i = 0 ; i < a . length ; ++ i ) { int left = i - 1 ; int right = i + 1 ; long total1 = total ; while ( left >= 0 && right < a . length ) { 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 . length ; ++ i ) { int left = i ; int right = i + 1 ; long total1 = total ; while ( left >= 0 && right < a . length ) { 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 ) { reverse ( first , second , a ) ; print ( a , b ) ; } else { print ( a , b ) ; } } public static void main ( String [ ] args ) { int n = 4 ; long a [ ] = { 2 , 3 , 1 , 5 } ; long b [ ] = { 8 , 2 , 4 , 3 } ; minimumProdArray ( a , b , n ) ; } }