Minimize sum of product of same | 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
def Print ( a , b ) : NEW_LINE INDENT minProd = 0 NEW_LINE for i in range ( len ( a ) ) : NEW_LINE INDENT print ( a [ i ] , end = " ▁ " ) NEW_LINE DEDENT print ( ) ; NEW_LINE for i in range ( len ( b ) ) : NEW_LINE INDENT print ( b [ i ] , end = " ▁ " ) NEW_LINE minProd += a [ i ] * b [ i ] NEW_LINE DEDENT print ( ) NEW_LINE print ( minProd ) NEW_LINE DEDENT def reverse ( left , right , arr ) : NEW_LINE INDENT while ( left < right ) : NEW_LINE INDENT temp = arr [ left ] NEW_LINE arr [ left ] = arr [ right ] NEW_LINE arr [ right ] = temp NEW_LINE left += 1 NEW_LINE right -= 1 NEW_LINE DEDENT DEDENT def minimumProdArray ( a , b , l ) : NEW_LINE INDENT total = 0 NEW_LINE for i in range ( len ( a ) ) : NEW_LINE INDENT total += a [ i ] * b [ i ] NEW_LINE DEDENT Min = 2147483647 NEW_LINE first = 0 ; NEW_LINE second = 0 ; NEW_LINE for i in range ( len ( a ) ) : NEW_LINE INDENT left = i - 1 ; NEW_LINE right = i + 1 ; NEW_LINE total1 = total ; NEW_LINE while ( left >= 0 and right < len ( a ) ) : NEW_LINE INDENT total1 -= a [ left ] * b [ left ] + a [ right ] * b [ right ] ; NEW_LINE total1 += a [ left ] * b [ right ] + a [ right ] * b [ left ] ; NEW_LINE if ( Min >= total1 ) : NEW_LINE INDENT Min = total1 NEW_LINE first = left NEW_LINE second = right NEW_LINE DEDENT left -= 1 NEW_LINE right += 1 NEW_LINE DEDENT DEDENT for i in range ( len ( a ) ) : NEW_LINE INDENT left = i NEW_LINE right = i + 1 NEW_LINE total1 = total NEW_LINE while ( left >= 0 and right < len ( a ) ) : NEW_LINE INDENT total1 -= a [ left ] * b [ left ] + a [ right ] * b [ right ] NEW_LINE total1 += a [ left ] * b [ right ] + a [ right ] * b [ left ] NEW_LINE if ( Min >= total1 ) : NEW_LINE INDENT Min = total1 NEW_LINE first = left NEW_LINE second = right NEW_LINE DEDENT left -= 1 NEW_LINE right += 1 NEW_LINE DEDENT DEDENT if ( Min < total ) : NEW_LINE INDENT reverse ( first , second , a ) NEW_LINE Print ( a , b ) NEW_LINE DEDENT else : NEW_LINE INDENT Print ( a , b ) NEW_LINE DEDENT DEDENT n = 4 ; NEW_LINE a = [ 2 , 3 , 1 , 5 ] NEW_LINE b = [ 8 , 2 , 4 , 3 ] NEW_LINE minimumProdArray ( a , b , n ) NEW_LINE