## Introduction

Before directly jumping to the question, let’s understand the next_permutation function.

**next_permutation:**

It is used to rearrange the elements into the next lexicographically greater permutation in the range [first, last]. A permutation is each one of the possible arrangements the elements can take.

It returns a true if the function can rearrange the object as a lexicographically greater permutation, else it returns a false.

Also read, __permutation of string__

### Problem statement

A number N in the range [0, 10^9) is given to us. Our goal is to find the maximum product of two integers that are formed when any permutation of N is divided into two parts.

### Sample Examples

**Example 1:**

```
Input: N = 234
Output:
Maximum product : 128
Explanation
Possible pairs after dividing N = {2, 34}, {23, 4}, {2, 43}, {24, 3}, {3, 42}, {32, 4}
Maximum product = 32 * 4 = 128
```

**Example 2:**

```
Input: N = 101
Output: 10
Explanation
Possible pairs after dividing N = {1, 01}, {10, 1}, {0, 11}
Maximum product = 10 * 1 = 10
```

## Approach

The idea is straightforward, generate all the possible permutations of the given number N. Divide the permutation into two possible parts and calculate the product of the two parts. Find the maximum value from all the products and return the maximum product among them.

To generate all the possible permutations, we will use the next_permutation function.

### Steps of algorithm

**Initialisation:**

- Pass the given number as a string in the max_product function.
- Create a maxm_prod variable to store the maximum product and initialise it with 0, maxm_prod = 0.

**Generating all permutations:**

- Sort the digits in the string using the sort function, sort(num.begin(), num.end()).
- Iterate through all permutations using next_permutation in a do-while loop.

**Generating all possible partitions:**

- Inside the do-while loop, iterate over all the possible partitions using a for-loop.
- Create a variable l = 0 and r = 0, store the left partition of the number into l and the right partition into r.
- Find the product, calculate the current maximum, and store it in maxm_prod.
- After calculating all the products of the numbers by dividing them into two parts of a permutation, move to the next greater permutation of the given number.
- Finally, return the value of the maxm_prod.