1.
Introduction
1.1.
Problem statement
1.2.
Sample Examples
2.
Approach
2.1.
Steps of algorithm
3.
Implementation in C++
3.1.
Complexity Analysis
4.
5.
Key Takeaways
Last Updated: Mar 27, 2024

# Maximum product of integers formed by splitting digits of N into two parts in any permutation

## 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.

### 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.

## Implementation in C++

``````#include <bits/stdc++.h>
using namespace std;

int max_product(string num)
{

int maxm_prod = 0; // stores the maximum product

sort(num.begin(), num.end()); // sorting the digits

// Iterating through all permutations
do {

for (int i = 1; i < num.size(); i++) {
int l = 0, r = 0;

for (int j = 0; j < i; j++) // left partition
l = l * 10 + num[j] - '0';

for (int j = i; j < num.size(); j++) // right partition
r = r * 10 + num[j] - '0';

maxm_prod = max(maxm_prod, l * r); // current maximum
}
} while (next_permutation(num.begin(), num.end()));

return maxm_prod;
}

int main()
{
int N = 234;
cout << "Maximum product: " << max_product(to_string(N));

return 0;
}``````

Output:

``Maximum product: 128``

Also see, Euclid GCD Algorithm

### Complexity Analysis

Time complexity: (logN)! *logN

We are using the next permutation function having a time complexity of d!*d where d is the maximum number of digits in N.

Here, the number of maximum digits is 9 as the maximum value of N in the above question is 10^9.

So, the time complexity = 9! * 9 = (9*log10)! * (9*log10) = (log 10^9) * (log 10^9) = (logN)! *logN

Space complexity: O(1) as we are using constant extra space.

Q1. How do you calculate a permutation?

Answer: Calculating the number of permutations of a word is as easy as evaluating n! where n is the number of letters in the word. There are 6! =6*5*4*3*2*1=720 permutations in a six-letter word.

Q2. What is the purpose of the next permutation function?

Answer: The next permutation() function in the C++ is used to reorder the elements in the range [first, last) into a lexicographically greater permutation. Each of several possible ways to order or arrange a set or number of things is defined as a permutation.

Q3. What is a greater permutation?

Answer: The greater permutation is the permutation that is lexicographically next. "ACB" will be followed by "BAC" as an example. In some cases, such as "BBB" or "DCBA," the lexicographically next permutation may be missing. We can accomplish this in C++ by calling the next permutation library function ().

Q4. What's the Difference Between Combination and Permutation?

Answer: The permutation is the number of different arrangements that can be created by selecting r number of items from a set of n items.

The number of different groups of r objects that can be formed from the available n objects is the combination.

Q5. Why do we use multiplication in permutations?

Answer: By multiplying the number of ways to complete each task, we can count the number of ways to complete a sequence of tasks using the multiplication principle. A permutation is a particular arrangement of objects.

## Key Takeaways

This article discussed the next_permutation function and the approach to find the maximum product of integers formed by splitting the digits of N into two parts in any permutation with examples for a better understanding and its implementation in C++.