# Split the Array in two parts such that maximum product is minimized

Given an array of integers, **arr[]** of size **N (<=16),** the task is to partition the array into 2 parts such that the maximum product of the 2 halves is minimized. Find the minimized maximum product of the half. If the array is empty, print **-1.**

**Examples:**

Attention reader! Don’t stop learning now. Get hold of all the important DSA concepts with the **DSA Self Paced Course** at a student-friendly price and become industry ready. To complete your preparation from learning a language to DS Algo and many more, please refer **Complete Interview Preparation Course****.**

In case you wish to attend **live classes **with experts, please refer **DSA Live Classes for Working Professionals **and **Competitive Programming Live for Students**.

Input:arr[] = {3, 5, 7}Output:15Explanation:The possible partitions are –

-> {5, 7} , {3} – here the products are 35 and 3 andmaximum product is 35

-> {3, 7} , {5} – here the products are 21 and 5 andmaximum product is 21

-> {5, 3} , {7} – here the products are 15 and 7 andmaximum product is 15

-> {5, 7, 3} , {} – here the products are 105 and 0 andmaximum product is 105Out of the maximum product obtained i.e. from 105, 35, 21 and 15, the minimum value is 15 and therefore our required answer is 15.

Input:arr[] = { 10 }Output:10Explanation:Since the array contains single element, the array cannot be further divided. Hence the first half contains 10 and the other half contains no element. Therefore, the answer is 10.

**Approach:** Since the value of **N** is less than **16** the problem can be solved using bit masking as multiply all the numbers which are at set bits position and put it into one side similarly multiply all the unset bits position and store it in another half find the maximum of those and store it in a set and at last return first element of the set.

Follow the steps below to solve the problem:

- Initialize a set
**st[]**to store the possible answers in order. - Iterate over the range
**[0, 2**using the variable^{N})**i**and perform the following tasks:- Initialize the variables
**product1**and**product2**as**1**. - Iterate over the range
**[0, N)**using the variable**j**and perform the following tasks:- If
**i & (1 << j)**is**true,**then multiply the value**arr[j]**to the variable**product1**else to the variable**product2.**

- If
- Insert the maximum of
**product1**or**product2**in the set**st[].**

- Initialize the variables
- After performing the above steps, print the first value of the set as the answer.

Below is the implementation of the above approach.

## C++

`// C++ program for the above approach` `#include <bits/stdc++.h>` `using` `namespace` `std;` `// Function to find the minimum of the` `// maximum product of the 2 halves` `void` `findMinimum(vector<` `int` `>& arr, ` `int` `N)` `{` ` ` `// Set to store the possible answers` ` ` `// in ascending order.` ` ` `set<` `int` `> st;` ` ` `// Traverse over the all possible` ` ` `for` `(` `int` `i = 0; i < (1 << N); i++) {` ` ` `// Variables to find the product` ` ` `// of set bits at set positions` ` ` `// and unset bits at unset positions` ` ` `int` `product1 = 1, product2 = 1;` ` ` `// Traverse over the array` ` ` `for` `(` `int` `j = 0; j < N; j++) {` ` ` `// Check the condition` ` ` `if` `(i & (1 << j)) {` ` ` `product1 = product1 * arr[j];` ` ` `}` ` ` `else` `{` ` ` `product2 = product2 * arr[j];` ` ` `}` ` ` `}` ` ` `// Insert the maximum one` ` ` `st.insert(max(product1, product2));` ` ` `}` ` ` `cout << *st.begin() << ` `"\n"` `;` `}` `// Driver Code` `int` `main()` `{` ` ` `vector<` `int` `> arr = { 3, 5, 7 };` ` ` `int` `N = arr.size();` ` ` `findMinimum(arr, N);` ` ` `return` `0;` `}` |

## Java

`// Java program for the above approach` `import` `java.util.*;` `public` `class` `GFG` `{` `// Function to find the minimum of the` `// maximum product of the 2 halves` `static` `void` `findMinimum(` `int` `[]arr, ` `int` `N)` `{` ` ` `// Set to store the possible answers` ` ` `// in ascending order.` ` ` `HashSet<Integer> st = ` `new` `HashSet<Integer>();` ` ` `// Traverse over the all possible` ` ` `for` `(` `int` `i = ` `0` `; i < (` `1` `<< N); i++) {` ` ` `// Variables to find the product` ` ` `// of set bits at set positions` ` ` `// and unset bits at unset positions` ` ` `int` `product1 = ` `1` `, product2 = ` `1` `;` ` ` `// Traverse over the array` ` ` `for` `(` `int` `j = ` `0` `; j < N; j++) {` ` ` `// Check the condition` ` ` `if` `((i & (` `1` `<< j)) == ` `0` `) {` ` ` `product1 = product1 * arr[j];` ` ` `}` ` ` `else` `{` ` ` `product2 = product2 * arr[j];` ` ` `}` ` ` `}` ` ` `// Insert the maximum one` ` ` `st.add(Math.max(product1, product2));` ` ` `}` ` ` `int` `ans = ` `0` `;` ` ` `for` `(` `int` `x : st) {` ` ` `ans = x;` ` ` `}` ` ` `System.out.print(ans);` `}` `// Driver Code` `public` `static` `void` `main(String args[])` `{` ` ` `int` `[]arr = { ` `3` `, ` `5` `, ` `7` `};` ` ` `int` `N = arr.length;` ` ` `findMinimum(arr, N);` ` ` `}` `}` `// This code is contributed by Samim Hossain Mondal.` |

## C#

`// C# program for the above approach` `using` `System;` `using` `System.Collections;` `using` `System.Collections.Generic;` `class` `GFG` `{` ` ` `// Function to find the minimum of the` `// maximum product of the 2 halves` `static` `void` `findMinimum(` `int` `[]arr, ` `int` `N)` `{` ` ` `// Set to store the possible answers` ` ` `// in ascending order.` ` ` `HashSet<` `int` `> st = ` `new` `HashSet<` `int` `>();` ` ` `// Traverse over the all possible` ` ` `for` `(` `int` `i = 0; i < (1 << N); i++) {` ` ` `// Variables to find the product` ` ` `// of set bits at set positions` ` ` `// and unset bits at unset positions` ` ` `int` `product1 = 1, product2 = 1;` ` ` `// Traverse over the array` ` ` `for` `(` `int` `j = 0; j < N; j++) {` ` ` `// Check the condition` ` ` `if` `((i & (1 << j)) == 0) {` ` ` `product1 = product1 * arr[j];` ` ` `}` ` ` `else` `{` ` ` `product2 = product2 * arr[j];` ` ` `}` ` ` `}` ` ` `// Insert the maximum one` ` ` `st.Add(Math.Max(product1, product2));` ` ` `}` ` ` `int` `ans = 0;` ` ` `foreach` `(` `int` `x ` `in` `st) {` ` ` `ans = x;` ` ` `}` ` ` `Console.Write(ans);` `}` `// Driver Code` `public` `static` `void` `Main()` `{` ` ` `int` `[]arr = { 3, 5, 7 };` ` ` `int` `N = arr.Length;` ` ` `findMinimum(arr, N);` ` ` `}` `}` `// This code is contributed by Samim Hossain Mondal.` |

## Javascript

`<script>` ` ` `// JavaScript Program to implement` ` ` `// the above approach` ` ` `// Function to find the minimum of the` ` ` `// maximum product of the 2 halves` ` ` `function` `findMinimum(arr, N) {` ` ` `// Set to store the possible answers` ` ` `// in ascending order.` ` ` `let st = ` `new` `Set();` ` ` `// Traverse over the all possible` ` ` `for` `(let i = 0; i < (1 << N); i++) {` ` ` `// Variables to find the product` ` ` `// of set bits at set positions` ` ` `// and unset bits at unset positions` ` ` `let product1 = 1;` ` ` `let product2 = 1;` ` ` `// Traverse over the array` ` ` `for` `(let j = 0; j < N; j++) {` ` ` `// Check the condition` ` ` `if` `(i & (1 << j)) {` ` ` `product1 = product1 * arr[j];` ` ` `}` ` ` `else` `{` ` ` `product2 = product2 * arr[j];` ` ` `}` ` ` `}` ` ` `// Insert the maximum one` ` ` `st.add(Math.max(product1, product2));` ` ` `}` ` ` `const last = [...st][st.size - 1];` ` ` `document.write(last);` ` ` `}` ` ` `// Driver Code` ` ` `let arr = [3, 5, 7];` ` ` `let N = arr.length;` ` ` `findMinimum(arr, N);` ` ` ` ` `// This code is contributed by Potta Lokesh` ` ` `</script>` |

**Output**

15

**Time complexity:** O((2^N)*(N*log(N)))**Auxiliary Space:** O(N)