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

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.

Frequently Asked Questions

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

Recommended Reads: Permutation of string

If you are an absolute beginner, interested in coding, and want to learn DSA, you can look for our guided path for DSA, which is free! 

Thank you for reading!