Given two equal-length arrays A[] and B[], consisting only of positive integers, the task is to reverse any subarray of the first array such that sum of the product of same-indexed elements of the two arrays, i.e. (A[i] * B[i]) is minimum.
Examples:
Input: N = 4, A[] = {2, 3, 1, 5}, B[] = {8, 2, 4, 3}
Output:
A[] = 1 3 2 5
B[] = 8 2 4 3
Minimum product is 37Explanation: Reverse the subarray {A[0], A[2]}. Sum of product of same-indexed elements is 37, which is minimum possible.
Input: N = 3, A[] = {3, 1, 1}, B[] = {4, 5, 6}
Output:
A[] = 3 1 1
B[] = 4 5 6
Minimum product is 23
Approach: The given problem can be solved by using Two Pointers technique. Follow the steps below to solve the problem:
- Declare a variable, say total, to store the initial product of the two arrays.
- Declare a variable, say min, to store the required answer.
- Declare two variables, say first and second, to store the start and end indices of the subarray required to be reversed to minimize the product.
- Calculate the minimum product possible for odd length subarrays by the following operations:
- Traverse the array using a variable, say i.
- Check for all odd length subarrays, by setting i – 1, say left, and i + 1, say right, as the start and end indices of the subarrays.
- Update total by subtracting a[left] * b[left] + a[right] * b[right] and adding a[left] * b[right] + a[right] * b[left].
- For every subarray, after updating total, check if it is the minimum obtained or not. Update and store minimum product accordingly.
- Similarly, check for all even length subarrays and calculate the sum.
- Finally, print the arrays and minimum sum obtained.
Below is the implementation of the above approach:
C++
// C++ program to implement the above approach #include<bits/stdc++.h> using namespace std; // Function to print1 the arrays 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; } // Function to reverse1 the subarray 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; } } // Function to calculate the // minimum product of same-indexed // elements of two given arrays void minimumProdArray(vector< int > &a, vector< int > &b, int l) { int total = 0; // Calculate initial product for ( int i = 0; i < a.size(); ++i) { total += a[i] * b[i]; } int min = INT_MAX; int first = 0; int second = 0; // Traverse all odd length subarrays 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()) { // Remove the previous product total1 -= a[left] * b[left] + a[right] * b[right]; // Add the current product total1 += a[left] * b[right] + a[right] * b[left]; // Check if current product // is minimum or not if (min >= total1) { min = total1; first = left; second = right; } --left; ++right; } } // Traverse all even length subarrays for ( int i = 0; i < a.size(); ++i) { int left = i; int right = i + 1; int total1 = total; while (left >= 0 && right < a.size()) { // Remove the previous product total1 -= a[left] * b[left] + a[right] * b[right]; // Add to the current product total1 += a[left] * b[right] + a[right] * b[left]; // Check if current product // is minimum or not if (min >= total1) { min = total1; first = left; second = right; } // Update the pointers --left; ++right; } } // reverse1 the subarray if (min < total) { reverse1(first, second, a); // print1 the subarray print1(a, b); } else { print1(a, b); } } // Driver Code int main() { int n = 4; vector< int > a{ 2, 3, 1, 5 }; vector< int > b{ 8, 2, 4, 3 }; minimumProdArray(a, b, n); } // This code is contributed by bgangwar59 |
Java
// Java Program to implement the above approach import java.io.*; import java.util.*; public class Main { // Function to calculate the // minimum product of same-indexed // elements of two given arrays static void minimumProdArray( long a[], long b[], int l) { long total = 0 ; // Calculate initial product for ( int i = 0 ; i < a.length; ++i) { total += a[i] * b[i]; } long min = Integer.MAX_VALUE; int first = 0 ; int second = 0 ; // Traverse all odd length subarrays 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) { // Remove the previous product total1 -= a[left] * b[left] + a[right] * b[right]; // Add the current product total1 += a[left] * b[right] + a[right] * b[left]; // Check if current product // is minimum or not if (min >= total1) { min = total1; first = left; second = right; } --left; ++right; } } // Traverse all even length subarrays for ( int i = 0 ; i < a.length; ++i) { int left = i; int right = i + 1 ; long total1 = total; while (left >= 0 && right < a.length) { // Remove the previous product total1 -= a[left] * b[left] + a[right] * b[right]; // Add to the current product total1 += a[left] * b[right] + a[right] * b[left]; // Check if current product // is minimum or not if (min >= total1) { min = total1; first = left; second = right; } // Update the pointers --left; ++right; } } // Reverse the subarray if (min < total) { reverse(first, second, a); // Print the subarray print(a, b); } else { print(a, b); } } // Function to reverse the subarray 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; } } // Function to print the arrays 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); } // Driver Code 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); } } |
Python3
# Python3 Program to implement the above approach # Function to calculate the # minimum product of same-indexed # elements of two given arrays def minimumProdArray(a, b, l) : total = 0 # Calculate initial product for i in range ( len (a)): total + = a[i] * b[i] Min = 2147483647 first = 0 ; second = 0 ; # Traverse all odd length subarrays for i in range ( len (a)): left = i - 1 ; right = i + 1 ; total1 = total; while (left > = 0 and right < len (a)) : # Remove the previous product total1 - = a[left] * b[left] + a[right] * b[right]; # Add the current product total1 + = a[left] * b[right] + a[right] * b[left]; # Check if current product # is minimum or not if ( Min > = total1) : Min = total1 first = left second = right left - = 1 right + = 1 # Traverse all even length subarrays for i in range ( len (a)): left = i right = i + 1 total1 = total while (left > = 0 and right < len (a)) : # Remove the previous product total1 - = a[left] * b[left] + a[right] * b[right] # Add to the current product total1 + = a[left] * b[right] + a[right] * b[left] # Check if current product # is minimum or not if ( Min > = total1) : Min = total1 first = left second = right # Update the pointers left - = 1 right + = 1 # Reverse the subarray if ( Min < total) : reverse(first, second, a) # Print the subarray Print (a, b) else : Print (a, b) # Function to reverse the subarray def reverse(left, right, arr) : while (left < right) : temp = arr[left] arr[left] = arr[right] arr[right] = temp left + = 1 right - = 1 # Function to print the arrays def Print (a, b): minProd = 0 for i in range ( len (a)): print (a[i], end = " " ) print (); for i in range ( len (b)): print (b[i], end = " " ) minProd + = a[i] * b[i] print () print (minProd) n = 4 ; a = [ 2 , 3 , 1 , 5 ] b = [ 8 , 2 , 4 , 3 ] minimumProdArray(a, b, n) # This code is contributed by divyeshrabadiya07 |
C#
// C# Program to implement the above approach using System; public class GFG { // Function to calculate the // minimum product of same-indexed // elements of two given arrays static void minimumProdArray( long [] a, long [] b, int l) { long total = 0; // Calculate initial product for ( int i = 0; i < a.Length; ++i) { total += a[i] * b[i]; } long min = Int32.MaxValue; int first = 0; int second = 0; // Traverse all odd length subarrays 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) { // Remove the previous product total1 -= a[left] * b[left] + a[right] * b[right]; // Add the current product total1 += a[left] * b[right] + a[right] * b[left]; // Check if current product // is minimum or not if (min >= total1) { min = total1; first = left; second = right; } --left; ++right; } } // Traverse all even length subarrays for ( int i = 0; i < a.Length; ++i) { int left = i; int right = i + 1; long total1 = total; while (left >= 0 && right < a.Length) { // Remove the previous product total1 -= a[left] * b[left] + a[right] * b[right]; // Add to the current product total1 += a[left] * b[right] + a[right] * b[left]; // Check if current product // is minimum or not if (min >= total1) { min = total1; first = left; second = right; } // Update the pointers --left; ++right; } } // Reverse the subarray if (min < total) { reverse(first, second, a); // Print the subarray print(a, b); } else { print(a, b); } } // Function to reverse the subarray 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; } } // Function to print the arrays static void print( long [] a, long [] b) { long minProd = 0; for ( int i = 0; i < a.Length; ++i) { Console.Write(a[i] + " " ); } Console.WriteLine(); for ( int i = 0; i < b.Length; ++i) { Console.Write(b[i] + " " ); minProd += a[i] * b[i]; } Console.WriteLine(); Console.WriteLine(minProd); } // Driver Code 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); } } // This code is contributed by ukasp. |
Javascript
<script> // JavaScript program to implement the above approach // Function to print1 the arrays function print1(a, b) { let minProd = 0; for (let i = 0; i < a.length; ++i) { document.write(a[i] + " " ); } document.write( "<br>" ); for (let i = 0; i < b.length; ++i) { document.write(b[i] + " " ); minProd += a[i] * b[i]; } document.write( "<br>" ); document.write(minProd); } // Function to reverse1 the subarray function reverse1(left, right, arr) { while (left < right) { let temp = arr[left]; arr[left] = arr[right]; arr[right] = temp; ++left; --right; } } // Function to calculate the // minimum product of same-indexed // elements of two given arrays function minimumProdArray(a, b, l) { let total = 0; // Calculate initial product for (let i = 0; i < a.length; ++i) { total += a[i] * b[i]; } let min = Number.MAX_SAFE_INTEGER; let first = 0; let second = 0; // Traverse all odd length subarrays for (let i = 0; i < a.length; ++i) { let left = i - 1; let right = i + 1; let total1 = total; while (left >= 0 && right < a.length) { // Remove the previous product total1 -= a[left] * b[left] + a[right] * b[right]; // Add the current product total1 += a[left] * b[right] + a[right] * b[left]; // Check if current product // is minimum or not if (min >= total1) { min = total1; first = left; second = right; } --left; ++right; } } // Traverse all even length subarrays for (let i = 0; i < a.length; ++i) { let left = i; let right = i + 1; let total1 = total; while (left >= 0 && right < a.length) { // Remove the previous product total1 -= a[left] * b[left] + a[right] * b[right]; // Add to the current product total1 += a[left] * b[right] + a[right] * b[left]; // Check if current product // is minimum or not if (min >= total1) { min = total1; first = left; second = right; } // Update the pointers --left; ++right; } } // reverse1 the subarray if (min < total) { reverse1(first, second, a); // print1 the subarray print1(a, b); } else { print1(a, b); } } // Driver Code let n = 4; let a = [2, 3, 1, 5]; let b = [8, 2, 4, 3]; minimumProdArray(a, b, n); // This code is contributed by _saurabh_jaiswal </script> |
1 3 2 5 8 2 4 3 37
Time Complexity: O(N2).
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!