Data Modelling & AI Data Structure & Algorithm

Minimize sum of product of same-indexed elements of two arrays by reversing a subarray of one of the two arrays

23 June 2025

3

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 37

Explanation: 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>

Output:

1 3 2 5 
8 2 4 3 
37

Time Complexity: O(N²).
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!

Minimize sum of product of same-indexed elements of two arrays by reversing a subarray of one of the two arrays

C++

Java

Python3

C#

Javascript

From Word2Vec to LLM2Vec: How to Choose the Right Embedding Model for RAG

How to Debug Slow Search Requests in Milvus

When Context Engineering Is Done Right, Hallucinations Can Be the Spark of AI Creativity

LEAVE A REPLY Cancel reply

Most Popular

I used the Google Pixel 10 Pro Fold and Galaxy Z Fold 7, and I’ve never been more conflicted

I wasn’t looking for a new app — but this one completely changed how I see daylight

It’s not sleek, it’s not cheap — but the Pixel 10 Pro Fold won me over anyway

Uh-oh, Pixel 10 users are still getting “fuzzy display” bug after Google’s fix

EDITOR PICKS

I used the Google Pixel 10 Pro Fold and Galaxy Z Fold 7, and I’ve never been more conflicted

I wasn’t looking for a new app — but this one completely changed how I see daylight

It’s not sleek, it’s not cheap — but the Pixel 10 Pro Fold won me over anyway

POPULAR POSTS

I used the Google Pixel 10 Pro Fold and Galaxy Z Fold 7, and I’ve never been more conflicted

I wasn’t looking for a new app — but this one completely changed how I see daylight

It’s not sleek, it’s not cheap — but the Pixel 10 Pro Fold won me over anyway

POPULAR CATEGORY

ABOUT US

FOLLOW US