Given an array, arr[] of size N and a positive integer M, the task is to find the maximum subarray product modulo M and the minimum length of the maximum product subarray.
Examples:
Input: arr[] = {2, 3, 4, 2}, N = 4, M = 5
Output:
Maximum subarray product is 4
Minimum length of the maximum product subarray is 1
Explanation:
Subarrays of length 1 are {{2}, {3}, {4}, {2}} and their product modulo M(= 5) are {2, 3, 4, 2} respectively.
Subarrays of length 2 are {{2, 3}, {3, 4}, {4, 2}} and the product modulo M(= 5) are {1, 2, 3} respectively.
Subarrays of length 3 are {{2, 3, 4}, {3, 4, 2}} and the product modulo M(= 5) are {4, 4, } respectively.
Subarrays of length 4 is {2, 3, 4, 2} and the product modulo M(= 5) is 3.
Therefore, the maximum subarray product mod M(= 5) is 4 and smallest possible length is 1.Input: arr[] = {5, 5, 5}, N = 3, M = 7
Output:
Maximum subarray product is 6
Minimum length of the maximum product subarray is 3
Naive Approach: The simplest approach is to generate all possible subarrays and for each subarray, calculate its product modulo M and print the maximum subarray product and the minimum length of such subarray.
Time Complexity: O(N3)
Auxiliary Space: O(1)
Efficient Approach: The above approach can be optimized by calculating the product of subarray in the range [i, j] by multiplying arr[j] with the precalculated product of subarray in the range [i, j – 1]. Follow the steps below to solve the problem:
- Initialize two variables, say ans and length, to store the maximum subarray product and the minimum length of maximum product subarray.
- Iterate over the range [0, N – 1] and perform the following steps:
- Initialize a variable, say product, to store the product of subarray {arr[i], …, arr[j]}.
- Iterate over the range [i, N-1] and update the product by multiplying it by arr[j], i.e. (product * arr[j]) % M.
- In every iteration, update ans if ans < product and then update length, if length > (j – i + 1).
- Finally, print the maximum subarray product obtained in ans and minimum length of subarray having the maximum product, length.
Below is the implementation of the above approach:
C++
// C++ program for above approach#include <bits/stdc++.h>using namespace std;// Function to find maximum subarray product// modulo M and minimum length of the subarrayvoid maxModProdSubarr(int arr[], int n, int M){ // Stores maximum subarray product modulo // M and minimum length of the subarray int ans = 0; // Stores the minimum length of // subarray having maximum product int length = n; // Traverse the array for (int i = 0; i < n; i++) { // Stores the product of a subarray int product = 1; // Calculate Subarray whose start // index is i for (int j = i; j < n; j++) { // Multiply product by arr[i] product = (product * arr[i]) % M; // If product greater than ans if (product > ans) { // Update ans ans = product; if (length > j - i + 1) { // Update length length = j - i + 1; } } } } // Print maximum subarray product mod M cout << "Maximum subarray product is " << ans << endl; // Print minimum length of subarray // having maximum product cout << "Minimum length of the maximum product " << "subarray is " << length << endl;}// Drivers Codeint main(){ int arr[] = { 2, 3, 4, 2 }; int N = sizeof(arr) / sizeof(arr[0]); int M = 5; maxModProdSubarr(arr, N, M); return 0;} |
Java
// Java program for the above approachimport java.io.*;import java.util.*;class GFG{// Function to find maximum subarray product// modulo M and minimum length of the subarraystatic void maxModProdSubarr(int arr[], int n, int M){ // Stores maximum subarray product modulo // M and minimum length of the subarray int ans = 0; // Stores the minimum length of // subarray having maximum product int length = n; // Traverse the array for(int i = 0; i < n; i++) { // Stores the product of a subarray int product = 1; // Calculate Subarray whose start // index is i for(int j = i; j < n; j++) { // Multiply product by arr[i] product = (product * arr[i]) % M; // If product greater than ans if (product > ans) { // Update ans ans = product; if (length > j - i + 1) { // Update length length = j - i + 1; } } } } // Print maximum subarray product mod M System.out.println( "Maximum subarray product is " + ans); // Print minimum length of subarray // having maximum product System.out.println( "Minimum length of the maximum " + "product subarray is " + length);}// Driver Codepublic static void main(String[] args){ int arr[] = { 2, 3, 4, 2 }; int N = arr.length; int M = 5; maxModProdSubarr(arr, N, M);}}// This code is contributed by Kingash |
Python3
# Python3 program for above approach# Function to find maximum subarray product# modulo M and minimum length of the subarraydef maxModProdSubarr(arr, n, M): # Stores maximum subarray product modulo # M and minimum length of the subarray ans = 0 # Stores the minimum length of # subarray having maximum product length = n # Traverse the array for i in range(n): # Stores the product of a subarray product = 1 # Calculate Subarray whose start # index is i for j in range(i, n, 1): # Multiply product by arr[i] product = (product * arr[i]) % M # If product greater than ans if (product > ans): # Update ans ans = product if (length > j - i + 1): # Update length length = j - i + 1 # Print maximum subarray product mod M print("Maximum subarray product is", ans) # Print minimum length of subarray # having maximum product print("Minimum length of the maximum product subarray is",length)# Drivers Codeif __name__ == '__main__': arr = [2, 3, 4, 2] N = len(arr) M = 5 maxModProdSubarr(arr, N, M) # This code is contributed by ipg2016107. |
C#
// C# program for above approachusing System;class GFG{// Function to find maximum subarray product// modulo M and minimum length of the subarraystatic void maxModProdSubarr(int[] arr, int n, int M){ // Stores maximum subarray product modulo // M and minimum length of the subarray int ans = 0; // Stores the minimum length of // subarray having maximum product int length = n; // Traverse the array for(int i = 0; i < n; i++) { // Stores the product of a subarray int product = 1; // Calculate Subarray whose start // index is i for(int j = i; j < n; j++) { // Multiply product by arr[i] product = (product * arr[i]) % M; // If product greater than ans if (product > ans) { // Update ans ans = product; if (length > j - i + 1) { // Update length length = j - i + 1; } } } } // Print maximum subarray product mod M Console.WriteLine( "Maximum subarray product is " + ans); // Print minimum length of subarray // having maximum product Console.WriteLine( "Minimum length of the maximum " + "product subarray is " + length);}// Driver codestatic void Main() { int[] arr = { 2, 3, 4, 2 }; int N = arr.Length; int M = 5; maxModProdSubarr(arr, N, M); }}// This code is contributed by code_hunt |
Javascript
<script>// javascript program for the above approach // Function to find maximum subarray product // modulo M and minimum length of the subarray function maxModProdSubarr(arr , n , M) { // Stores maximum subarray product modulo // M and minimum length of the subarray var ans = 0; // Stores the minimum length of // subarray having maximum product var length = n; // Traverse the array for (i = 0; i < n; i++) { // Stores the product of a subarray var product = 1; // Calculate Subarray whose start // index is i for (j = i; j < n; j++) { // Multiply product by arr[i] product = (product * arr[i]) % M; // If product greater than ans if (product > ans) { // Update ans ans = product; if (length > j - i + 1) { // Update length length = j - i + 1; } } } } // Print maximum subarray product mod M document.write("Maximum subarray product is " + ans+"<br/>"); // Print minimum length of subarray // having maximum product document.write("Minimum length of the maximum " + "product subarray is " + length); } // Driver Code var arr = [ 2, 3, 4, 2 ]; var N = arr.length; var M = 5; maxModProdSubarr(arr, N, M);// This code is contributed by umadevi9616. </script> |
Output:
Maximum subarray product is 4 Minimum length of the maximum product subarray is 1
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!
