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 arraysvoid 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 subarrayvoid 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 arraysvoid 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 Codeint 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 approachimport 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 arraysdef 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 subarraydef 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 arraysdef 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 approachusing 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 arraysfunction 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 subarrayfunction 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 arraysfunction 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 Codelet 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> |
Output:
1 3 2 5 8 2 4 3 37
Time Complexity: O(N2).
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
