Dado un rango representado por dos enteros positivos L y R. Encuentra el número que se encuentra en el rango que tiene el producto máximo de los dígitos.
Ejemplos:
Input : L = 1, R = 10 Output : 9 Input : L = 51, R = 62 Output : 59
Enfoque: la idea clave aquí es iterar sobre los dígitos del número R a partir del dígito más significativo. Yendo de izquierda a derecha, es decir, del dígito más significativo al dígito menos significativo, reemplace el dígito actual con uno menos que el dígito actual y reemplace todos los dígitos después del dígito actual en el número con 9, ya que el número ya se ha vuelto más pequeño que R en la posición actual para que podamos poner con seguridad cualquier número en los siguientes dígitos para maximizar el producto de los dígitos. Además, verifique si el número resultante es mayor que L para permanecer en el rango y actualizar el producto máximo.
A continuación se muestra la implementación del enfoque anterior:
C++
// CPP Program to find the number in a
// range having maximum product of the
// digits
#include <bits/stdc++.h>
using namespace std;
// Returns the product of digits of number x
int product(int x)
{
int prod = 1;
while (x) {
prod *= (x % 10);
x /= 10;
}
return prod;
}
// This function returns the number having
// maximum product of the digits
int findNumber(int l, int r)
{
// Converting both integers to strings
string a = to_string(l);
string b = to_string(r);
// Let the current answer be r
int ans = r;
for (int i = 0; i < b.size(); i++) {
if (b[i] == '0')
continue;
// Stores the current number having
// current digit one less than current
// digit in b
string curr = b;
curr[i] = ((curr[i] - '0') - 1) + '0';
// Replace all following digits with 9
// to maximise the product
for (int j = i + 1; j < curr.size(); j++)
curr[j] = '9';
// Convert string to number
int num = 0;
for (auto c : curr)
num = num * 10 + (c - '0');
// Check if it lies in range and its product
// is greater than max product
if (num >= l && product(ans) < product(num))
ans = num;
}
return ans;
}
// Driver Code
int main()
{
int l = 1, r = 10;
cout << findNumber(l, r) << endl;
l = 51, r = 62;
cout << findNumber(l, r) << endl;
return 0;
}
Java
// Java Program to find the number in a
// range having maximum product of the
// digits
class GFG
{
// Returns the product of digits of number x
static int product(int x)
{
int prod = 1;
while (x > 0)
{
prod *= (x % 10);
x /= 10;
}
return prod;
}
// This function returns the number having
// maximum product of the digits
static int findNumber(int l, int r)
{
// Converting both integers to strings
//string a = l.ToString();
String b = Integer.toString(r);
// Let the current answer be r
int ans = r;
for (int i = 0; i < b.length(); i++)
{
if (b.charAt(i) == '0')
continue;
// Stores the current number having
// current digit one less than current
// digit in b
char[] curr = b.toCharArray();
curr[i] = (char)(((int)(curr[i] -
(int)'0') - 1) + (int)('0'));
// Replace all following digits with 9
// to maximise the product
for (int j = i + 1; j < curr.length; j++)
curr[j] = '9';
// Convert string to number
int num = 0;
for (int j = 0; j < curr.length; j++)
num = num * 10 + (curr[j] - '0');
// Check if it lies in range and its product
// is greater than max product
if (num >= l && product(ans) < product(num))
ans = num;
}
return ans;
}
// Driver Code
public static void main (String[] args)
{
int l = 1, r = 10;
System.out.println(findNumber(l, r));
l = 51;
r = 62;
System.out.println(findNumber(l, r));
}
}
// This code is contributed by chandan_jnu
Python3
# Python3 Program to find the number
# in a range having maximum product
# of the digits
# Returns the product of digits
# of number x
def product(x) :
prod = 1
while (x) :
prod *= (x % 10)
x //= 10;
return prod
# This function returns the number having
# maximum product of the digits
def findNumber(l, r) :
# Converting both integers to strings
a = str(l);
b = str(r);
# Let the current answer be r
ans = r
for i in range(len(b)) :
if (b[i] == '0') :
continue
# Stores the current number having
# current digit one less than current
# digit in b
curr = list(b)
curr[i] = str(((ord(curr[i]) -
ord('0')) - 1) + ord('0'))
# Replace all following digits with 9
# to maximise the product
for j in range(i + 1, len(curr)) :
curr[j] = str(ord('9'))
# Convert string to number
num = 0
for c in curr :
num = num * 10 + (int(c) - ord('0'))
# Check if it lies in range and its
# product is greater than max product
if (num >= l and product(ans) < product(num)) :
ans = num
return ans
# Driver Code
if __name__ == "__main__" :
l, r = 1, 10
print(findNumber(l, r))
l, r = 51, 62
print(findNumber(l, r))
# This code is contributed by Ryuga
C#
// C# Program to find the number in a
// range having maximum product of the
// digits
using System;
class GFG
{
// Returns the product of digits of number x
static int product(int x)
{
int prod = 1;
while (x > 0)
{
prod *= (x % 10);
x /= 10;
}
return prod;
}
// This function returns the number having
// maximum product of the digits
static int findNumber(int l, int r)
{
// Converting both integers to strings
//string a = l.ToString();
string b = r.ToString();
// Let the current answer be r
int ans = r;
for (int i = 0; i < b.Length; i++)
{
if (b[i] == '0')
continue;
// Stores the current number having
// current digit one less than current
// digit in b
char[] curr = b.ToCharArray();
curr[i] = (char)(((int)(curr[i] -
(int)'0') - 1) + (int)('0'));
// Replace all following digits with 9
// to maximise the product
for (int j = i + 1; j < curr.Length; j++)
curr[j] = '9';
// Convert string to number
int num = 0;
for (int j = 0; j < curr.Length; j++)
num = num * 10 + (curr[j] - '0');
// Check if it lies in range and its product
// is greater than max product
if (num >= l && product(ans) < product(num))
ans = num;
}
return ans;
}
// Driver Code
static void Main()
{
int l = 1, r = 10;
Console.WriteLine(findNumber(l, r));
l = 51;
r = 62;
Console.WriteLine(findNumber(l, r));
}
}
// This code is contributed by chandan_jnu
PHP
<?php
// PHP Program to find the number
// in a range having maximum product
// of the digits
// Returns the product of digits
// of number x
function product($x)
{
$prod = 1;
while ($x)
{
$prod *= ($x % 10);
$x = (int)($x / 10);
}
return $prod;
}
// This function returns the number
// having maximum product of the digits
function findNumber($l, $r)
{
// Let the current answer be r
$ans = $r;
// Converting both integers
// to strings
$a = strval($l);
$b = strval($r);
for ($i = 0; $i < strlen($b); $i++)
{
if ($b[$i] == '0')
continue;
// Stores the current number having
// current digit one less than
// current digit in b
$curr = $b;
$curr[$i] = chr(((ord($curr[$i]) -
ord('0')) - 1) +
ord('0'));
// Replace all following digits
// with 9 to maximise the product
for ($j = $i + 1; $j < strlen($curr); $j++)
$curr[$j] = '9';
// Convert string to number
$num = 0;
for ($c = 0; $c < strlen($curr); $c++)
$num = $num * 10 + (ord($curr[$c]) -
ord('0'));
// Check if it lies in range and its
// product is greater than max product
if ($num >= $l and
product($ans) < product($num))
$ans = $num;
}
return $ans;
}
// Driver Code
$l = 1;
$r = 10;
print(findNumber($l, $r) . "\n");
$l = 51;
$r = 62;
print(findNumber($l, $r));
// This code is contributed
// by chandan_jnu
?>
Javascript
<script>
// Javascript Program to find the number in a
// range having maximum product of the
// digits
// Returns the product of digits of number x
function product(x)
{
let prod = 1;
while (x > 0)
{
prod *= (x % 10);
x = parseInt(x / 10, 10);
}
return prod;
}
// This function returns the number having
// maximum product of the digits
function findNumber(l, r)
{
// Converting both integers to strings
//string a = l.ToString();
let b = r.toString();
// Let the current answer be r
let ans = r;
for (let i = 0; i < b.length; i++)
{
if (b[i] == '0')
continue;
// Stores the current number having
// current digit one less than current
// digit in b
let curr = b.split('');
curr[i] = String.fromCharCode(((curr[i].charCodeAt() - '0'.charCodeAt()) - 1) + '0'.charCodeAt());
// Replace all following digits with 9
// to maximise the product
for (let j = i + 1; j < curr.length; j++)
curr[j] = '9';
// Convert string to number
let num = 0;
for (let j = 0; j < curr.length; j++)
num = num * 10 + (curr[j].charCodeAt() - '0'.charCodeAt());
// Check if it lies in range and its product
// is greater than max product
if (num >= l && product(ans) < product(num))
ans = num;
}
return ans;
}
let l = 1, r = 10;
document.write(findNumber(l, r) + "</br>");
l = 51;
r = 62;
document.write(findNumber(l, r));
// This code is contributed by decode2207.
</script>
Producción:
9 59
Complejidad de tiempo : O((logr) 2 ), donde r es el número dado.
Espacio Auxiliar: O(logr) donde r es el número dado.
Otro enfoque: se puede resolver usando Digit Dp
Puntos clave de observación: –
1. Como sabemos, usamos tight in digit dp para verificar si el rango de este dígito está restringido o no, lo mismo aquí usaremos tight ta y tight tb ( básicamente dos condiciones ajustadas ), donde ta nos dirá
el límite inferior del dígito y tb nos dirá el límite superior del dígito y la razón para usar dos valores ajustados es que tenemos que calcular el producto máximo, puede ser el caso como: –
max(l,r) ≠ max(r) – max(l-1) y nuestro entero debe estar en un rango de l a r.
2. Supongamos que los valores del rango son l=5 y r=15, por lo que para que el tamaño sea igual, debemos agregar los ceros delante del número después de convertirlo en una string y tener cuidado con los ceros iniciales mientras calculamos la respuesta.
Los estados de DP incluyen: –
1) posición
- dirá la posición del índice desde la izquierda en el número entero
2) ta
- representa el límite inferior de un dígito, debemos asegurarnos de que el número sea mayor o igual que {l}
- Supongamos que estamos construyendo un número mayor que igual a 0055 y hemos creado una secuencia como 005, por lo que en el cuarto lugar, no podemos poner un dígito menor que 5, que solo tendrá dígitos entre 5 y 9. Entonces, para verificar este límite, necesitamos ta.
Example : Consider the value of l = 005 Index : 0 1 2 digits : 0 0 5 valid numbers like: 005,006,007,008... invalid numbers like: ...001,002,003,004
3) tuberculosis
- el límite superior de un dígito, debemos asegurarnos de que el número sea menor o igual que { r }
- Nuevamente, supongamos que estamos construyendo un número menor que igual a 526 y hemos creado una secuencia como 52, por lo que en el tercer lugar, no podemos poner un dígito mayor que 6, allí solo podemos colocar entre 0 y 6. Entonces, para comprobando este límite, necesitamos tb
Example : Consider the value of r = 150 Index : 0 1 2 digits : 1 5 0 valid numbers like: ...148,149,150 invalid numbers like: 151,152,153...
4) calle
- se usa para verificar los ceros a la izquierda (como 005 ~ 5)
3. Restricciones: l y r (1 ≤ l ≤ r ≤ 10^18)
Algoritmo:
- Atravesaremos i de principio a fin sobre la base de tight ta y tight tb como:
start = ta == 1 ? l[ pos ] - '0' : 0; end = tb ==1 ? r[ pos ] -'0' : 9;
- En primer lugar, comprobaremos si hay ceros a la izquierda como:
if ( st == 0 and i = 0) then multiply with 1,else multiply with i
- Para cada posición, calcularemos el producto de secuencia y verificaremos si es el producto máximo o no y almacenaremos el número correspondiente
int ans = 0;
for(int i = start; i <= end; i++){
int val = i;
if (st==0 and i==0) val = 1;
ans = max (ans, val * solve (pos+1, ta&(i==start),tb&(i==end) ,st|i>0);
}
Implementación en C++:
C++
// CPP program for the above approach
#include <bits/stdc++.h>
using namespace std;
#define int long long int
// pair of array to store product and number
// dp[pos][tight1][tight2][start]
pair<int, string> dp[20][2][2][2];
pair<int, string> recur(string l, string r, int pos, int ta,
int tb, int st)
{
// Base case if pos is equal
// to l or r size return
// pair{1,""}
if (pos == l.size()) {
return { 1, "" };
}
// look up condition
if (dp[pos][ta][tb][st].first != -1)
return dp[pos][ta][tb][st];
// Lower bound condition
int start = ta ? l[pos] - '0' : 0;
// Upper bound condition
int end = tb ? r[pos] - '0' : 9;
// To store the maximum product
// initially its is set to -1
int ans = -1;
// To store the corresponding
// number as number is large
// so store it as a string
string s = "";
for (int i = start; i <= end; i++) {
// Multiply with this val
int val = i;
// check for leading zeroes as 00005
if (st == 0 and i == 0) {
val = 1;
}
// Recursive call for next
// position and store it in
// a pair pair first gives
// maximum product pair
// second gives number which
// gave maximum product
pair<int, string> temp
= recur(l, r, pos + 1, ta & (i == start),
tb & (i == end), st | i > 0);
// check if calculated product is greater than
// previous calculated ans
if (temp.first * val > ans) {
ans = temp.first * val;
// update string only if no leading zeroes
// becoz no use to append the leading zeroes
if (i == 0 and st == 0) {
s = temp.second;
}
else {
s = temp.second;
s.push_back('0' + i);
}
}
}
// while returning memoize the ans
return dp[pos][ta][tb][st] = { ans, s };
}
pair<int, string> solve(int a, int b)
{
// convert int l to sting L and int r to string R ,
// as integer value should be large
string L = to_string(a);
string R = to_string(b);
// to make the size of strings
// equal append zeroes in
// front of string L
if (L.size() < R.size()) {
reverse(L.begin(), L.end());
while (L.size() < R.size()) {
L.push_back('0');
}
reverse(L.begin(), L.end());
}
// initialize dp
// as it is pair of array so memset will not work
for (int i = 0; i < 20; i++) {
for (int j = 0; j < 2; j++) {
for (int k = 0; k < 2; k++) {
for (int l = 0; l < 2; l++) {
dp[i][j][k][l].first = -1;
}
}
}
}
// as we have to return pair second value
// it's that number which gaves maximum product
// initially pos=0,ta=1,tb=1,start=0(becoz number is not
// started yet)
pair<int, string> ans = recur(L, R, 0, 1, 1, 0);
// reverse it becoz we were appending from right to left
// in recursive call
reverse(ans.second.begin(), ans.second.end());
return { ans.first, ans.second };
}
signed main()
{
// take l and r as input
int l = 52, r = 62;
cout << "l= " << l << "\n";
cout << "r= " << r << "\n";
pair<int, string> ans = solve(l, r);
cout << "Maximum Product: " << ans.first << "\n";
cout << "Number which gave maximum product: "
<< ans.second;
return 0;
}
Java
// JAVA program for the above approach
import java.util.*;
import java.io.*;
import java.math.*;
class GFG
{
// pair of array to store product and number
// dp[pos][tight1][tight2][start]
static class pair
{
int first;
String second;
pair(int first,String second)
{
this.first=first;
this.second=second;
}
}
static pair dp[][][][];
static pair recur(String l, String r, int pos, int ta,
int tb, int st)
{
// Base case if pos is equal
// to l or r size return
// pair{1,""}
if (pos == l.length()) {
return new pair(1,"");
}
// look up condition
if (dp[pos][ta][tb][st].first != -1)
return dp[pos][ta][tb][st];
// Lower bound condition
int start = ta ==1 ? l.charAt(pos) - '0' : 0;
// Upper bound condition
int end = tb ==1 ? r.charAt(pos) - '0' : 9;
// To store the maximum product
// initially its is set to -1
int ans = -1;
// To store the corresponding
// number as number is large
// so store it as a string
String s = "";
for (int i = start; i <= end; i++) {
// Multiply with this val
int val = i;
// check for leading zeroes as 00005
if (st == 0 && i == 0) {
val = 1;
}
// Recursive call for next
// position and store it in
// a pair pair first gives
// maximum product pair
// second gives number which
// gave maximum product
pair temp
= recur(l, r, pos + 1, ta==1 ? (i == start ? 1 : 0) : 0,
tb==1 ? (i == end ? 1 : 0) : 0, (st | i) > 0 ? 1 : 0);
// check if calculated product is greater than
// previous calculated ans
if (temp.first * val > ans) {
ans = temp.first * val;
// update string only if no leading zeroes
// becoz no use to append the leading zeroes
if (i == 0 && st == 0) {
s = temp.second;
}
else {
s = temp.second;
s+=(i);
}
}
}
// while returning memoize the ans
return dp[pos][ta][tb][st] = new pair(ans, s );
}
static String reverse(String x)
{
StringBuilder sb=new StringBuilder("");
sb.append(x);
sb.reverse();
return sb.toString();
}
static pair solve(int a, int b)
{
// convert int l to sting L and int r to string R ,
// as integer value should be large
String L = Integer.toString(a);
String R = Integer.toString(b);
// to make the size of strings
// equal append zeroes in
// front of string L
if (L.length() < R.length()) {
L=reverse(L);
while (L.length() < R.length()) {
L += "0";
}
L=reverse(L);
}
// initialize dp
// as it is pair of array so memset will not work
for (int i = 0; i < 20; i++) {
for (int j = 0; j < 2; j++) {
for (int k = 0; k < 2; k++) {
for (int l = 0; l < 2; l++) {
dp[i][j][k][l] = new pair(-1,"");
}
}
}
}
// as we have to return pair second value
// it's that number which gaves maximum product
// initially pos=0,ta=1,tb=1,start=0(becoz number is not
// started yet)
pair ans = recur(L, R, 0, 1, 1, 0);
// reverse it becoz we were appending from right to left
// in recursive call
ans.second = reverse(ans.second);
pair result = new pair(ans.first, ans.second);
return result;
}
public static void main(String args[])
{
// take l and r as input
int l = 52, r = 62;
System.out.println("l= "+l );
System.out.println("r= "+r );
// creation of dp table
dp = new pair[20][2][2][2];
// call function
pair ans = solve(l, r);
System.out.println("Maximum Product: "+ans.first);
System.out.println("Number which gave maximum product: "+ans.second);
}
}
// This code is contributed by Debojyoti Mandal
Python3
# Python3 program for the above approach
# pair of array to store product and number
# dp[pos][tight1][tight2][start]
dp=[[[[[0,0] for _ in range(2)] for _ in range(2)]for _ in range(2)]for _ in range(20)]
def recur(l, r, pos, ta, tb, st):
# Base case if pos is equal
# to l or r size return
# pair:1,""
if (pos == len(l)) :
return (1, "")
# look up condition
if (dp[pos][ta][tb][st][0] != -1):
return dp[pos][ta][tb][st]
# Lower bound condition
start = ord(l[pos]) - ord('0') if ta else 0
# Upper bound condition
end = ord(r[pos]) - ord('0') if tb else 9
# To store the maximum product
# initially its is set to -1
ans = -1
# To store the corresponding
# number as number is large
# so store it as a
s = []
for i in range(start,end+1) :
# Multiply with this val
val = i
# check for leading zeroes as 00005
if (st == 0 and i == 0) :
val = 1
# Recursive call for next
# position and store it in
# a pair pair first gives
# maximum product pair
# second gives number which
# gave maximum product
temp = recur(l, r, pos + 1, ta & (i == start),tb & (i == end), st | i > 0)
# check if calculated product is greater than
# previous calculated ans
if (temp[0] * val > ans) :
ans = temp[0] * val
# update only if no leading zeroes
# becoz no use to append the leading zeroes
if (i == 0 and st == 0) :
s = list(temp[1])
else :
s = list(temp[1])
s.append(chr(ord('0') + i))
s=''.join(s)
# while returning memoize the ans
dp[pos][ta][tb][st] = [ans, s]
return dp[pos][ta][tb][st]
def solve(a, b):
# convert l to sting L and r to R ,
# as eger value should be large
L = list(str(a))
R = str(b)
# to make the size of s
# equal append zeroes in
# front of L
if (len(L) < len(R)) :
L=L[::-1]
while (len(L) < len(R)) :
L.append('0')
L=L[::-1]
L=''.join(L)
# initialize dp
# as it is pair of array so memset will not work
for i in range(20) :
for j in range(2) :
for k in range(2) :
for l in range(2):
dp[i][j][k][l][0] = -1
# as we have to return pair second value
# it's that number which gaves maximum product
# initially pos=0,ta=1,tb=1,start=0(becoz number is not
# started yet)
ans = recur(L, R, 0, 1, 1, 0)
# reverse it becoz we were appending from right to left
# in recursive call
ans[1]=ans[1][::-1]
return [ans[0], ans[1]]
if __name__=='__main__':
# take l and r as input
l = 52; r = 62
print("l=",l)
print("r=",r)
ans = solve(l, r)
print("Maximum Product:",ans[0])
print("Number which gave maximum product:",ans[1])
Producción
l= 52 r= 62 Maximum Product: 45 Number which gave maximum product: 59
Complejidad Temporal: O(logN), donde N es el número máximo entre L y R.
Espacio Auxiliar: O(logN)
Publicación traducida automáticamente
Artículo escrito por Nishant Tanwar y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA