Dado un número entero N en el rango [0, 10 9 ] , la tarea es encontrar el producto máximo de dos números enteros que se forman al dividir cualquier permutación de dígitos del número entero N en dos partes.
Ejemplo:
Entrada: N = 123
Salida: 63
Explicación: El número de formas de dividir N = 123 en 2 enteros son {12, 3}, {21, 3}, {13, 2}, {31, 2}, {23, 1} y {32, 1}. El producto de {21, 3} es 63 que es el máximo sobre todas las posibilidades.Entrada: N = 101
Salida: 10
Enfoque: El problema dado se puede resolver usando permutaciones y combinaciones básicas con la ayuda de las siguientes observaciones:
- El número total de formas de dividir el entero dado en dos partes se puede calcular como (Número de permutaciones posibles) * (Formas de dividir una permutación) => 9! * 8 => 2903040 . Por lo tanto, todas las separaciones posibles se pueden iterar.
- Los ceros iniciales en cualquier permutación tampoco afectan la respuesta.
Por lo tanto, todas las permutaciones de los dígitos del entero actual se pueden iterar utilizando la siguiente función de permutación y, para cada permutación, mantener el producto máximo de todas las formas posibles de dividir la permutación en una variable, que es la respuesta requerida.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find maximum product
// of integers formed by dividing any
// permutation of N into two parts.
int maxProduct(string N)
{
// Stores the maximum product
int ans = 0;
// Sort the digits in the string
sort(N.begin(), N.end());
// Iterating over all permutations
do {
// Loop to iterate over all
// possible partitions
for (int i = 1; i < N.size(); i++) {
int l = 0, r = 0;
// Calculate the left partition
for (int j = 0; j < i; j++)
l = l * 10 + N[j] - '0';
// Calculate the right partition
for (int j = i; j < N.size(); j++)
r = r * 10 + N[j] - '0';
// Update answer
ans = max(ans, l * r);
}
} while (next_permutation(N.begin(), N.end()));
// Return answer
return ans;
}
// Driver code
int main()
{
int N = 101;
cout << maxProduct(to_string(N));
return 0;
}
Java
// Java implementation of the above approach
import java.util.*;
class GFG{
static boolean next_permutation(char[] p) {
for (int a = p.length - 2; a >= 0; --a)
if (p[a] < p[a + 1])
for (int b = p.length - 1;; --b)
if (p[b] > p[a]) {
char t = p[a];
p[a] = p[b];
p[b] = t;
for (++a, b = p.length - 1; a < b; ++a, --b) {
t = p[a];
p[a] = p[b];
p[b] = t;
}
return true;
}
return false;
}
// Function to find maximum product
// of integers formed by dividing any
// permutation of N into two parts.
static int maxProduct(String a)
{
// Stores the maximum product
int ans = 0;
// Sort the digits in the String
char []N = a.toCharArray();
Arrays.sort(N);
// Iterating over all permutations
do {
// Loop to iterate over all
// possible partitions
for (int i = 1; i < N.length; i++) {
int l = 0, r = 0;
// Calculate the left partition
for (int j = 0; j < i; j++)
l = l * 10 + N[j] - '0';
// Calculate the right partition
for (int j = i; j < N.length; j++)
r = r * 10 + N[j] - '0';
// Update answer
ans = Math.max(ans, l * r);
}
} while (next_permutation(N));
// Return answer
return ans;
}
// Driver code
public static void main(String[] args)
{
int N = 101;
System.out.print(maxProduct(String.valueOf(N)));
}
}
// This code is contributed by umadevi9616
Python3
# Python3 implementation of the above approach
# Function for next permutation
def next_permutation(arr):
# Find the length of the array
n = len(arr)
# Start from the right most digit and
# find the first digit that is smaller
# than the digit next to it.
k = n - 2
while k >= 0:
if arr[k] < arr[k + 1]:
break
k -= 1
# Reverse the list if the digit that
# is smaller than the digit next to
# it is not found.
if k < 0:
arr = arr[::-1]
else:
# Find the first greatest element
# than arr[k] from the end of the list
for l in range(n - 1, k, -1):
if arr[l] > arr[k]:
break
# Swap the elements at arr[k] and arr[l
arr[l], arr[k] = arr[k], arr[l]
# Reverse the list from k + 1 to the end
# to find the most nearest greater number
# to the given input number
arr[k + 1:] = reversed(arr[k + 1:])
return arr
# Function to find maximum product
# of integers formed by dividing any
# permutation of N into two parts.
def maxProduct(N):
# Stores the maximum product
ans = 0
# Sort the digits in the string
Nstr = sorted(N)
Instr = sorted(N)
# Iterating over all permutations
while next_permutation(Nstr) != Instr:
# Loop to iterate over all
# possible partitions
for i in range(len(Nstr)):
l = 0
r = 0
# Calculate the left partition
for j in range(0, i):
l = l * 10 + ord(N[j]) - ord('0')
# Calculate the right partition
for j in range(i, len(Nstr)):
r = r * 10 + ord(N[j]) - ord('0')
# Update answer
ans = max(ans, l * r)
# Return answe
return ans
# Driver code
N = 101
print(maxProduct(str(N)))
# This code is contributed by Potta Lokesh
C#
// C# implementation of the above approach
using System;
class GFG {
static bool next_permutation(char[] p)
{
for (int a = p.Length - 2; a >= 0; --a)
if (p[a] < p[a + 1])
for (int b = p.Length - 1;; --b)
if (p[b] > p[a]) {
char t = p[a];
p[a] = p[b];
p[b] = t;
for (++a, b = p.Length - 1; a < b;
++a, --b) {
t = p[a];
p[a] = p[b];
p[b] = t;
}
return true;
}
return false;
}
// Function to find maximum product
// of integers formed by dividing any
// permutation of N into two parts.
static int maxProduct(string a)
{
// Stores the maximum product
int ans = 0;
// Sort the digits in the String
char[] N = a.ToCharArray();
Array.Sort(N);
// Iterating over all permutations
do {
// Loop to iterate over all
// possible partitions
for (int i = 1; i < N.Length; i++) {
int l = 0, r = 0;
// Calculate the left partition
for (int j = 0; j < i; j++)
l = l * 10 + N[j] - '0';
// Calculate the right partition
for (int j = i; j < N.Length; j++)
r = r * 10 + N[j] - '0';
// Update answer
ans = Math.Max(ans, l * r);
}
} while (next_permutation(N));
// Return answer
return ans;
}
// Driver code
public static void Main(string[] args)
{
int N = 101;
Console.Write(maxProduct(N.ToString()));
}
}
// This code is contributed by ukasp.
Javascript
<script>
// javascript implementation of the above approach
function next_permutation( p) {
for (var a = p.length - 2; a >= 0; --a)
if (p[a] < p[a + 1])
for (b = p.length - 1;; --b)
if (p[b] > p[a]) {
var t = p[a];
p[a] = p[b];
p[b] = t;
for (++a, b = p.length - 1; a < b; ++a, --b) {
t = p[a];
p[a] = p[b];
p[b] = t;
}
return true;
}
return false;
}
// Function to find maximum product
// of integers formed by dividing any
// permutation of N into two parts.
function maxProduct( a) {
// Stores the maximum product
var ans = 0;
// Sort the digits in the String
N = a.split("");
N.sort();
// Iterating over all permutations
do {
// Loop to iterate over all
// possible partitions
for (var i = 1; i < N.length; i++) {
var l = 0, r = 0;
// Calculate the left partition
for (var j = 0; j < i; j++)
l = l * 10 + parseInt(N[j])-'0';
// Calculate the right partition
for (var j = i; j < N.length; j++)
r = r * 10 + parseInt(N[j])-'0';
// Update answer
ans = Math.max(ans, l * r);
}
} while (next_permutation(N));
// Return answer
return ans;
}
// Driver code
var N = "101";
document.write(maxProduct(N));
// This code is contributed by Rajput-Ji
</script>
Producción
10
Complejidad de tiempo: O((log N)! * log N)
Espacio auxiliar: O(1)