Dado un número n, encuentre un número en el rango de 1 a n tal que su suma sea máxima. Si hay varios enteros de este tipo, determine el mayor de ellos.
Ejemplos:
Input: n = 100 Output: 99 99 is the largest number in range from 1 to 100 with maximum sum of digits. Input: n = 48 Output: 48 Explanation: There are two numbers with maximum digit sum. The numbers are 48 and 39 Since 48 > 39, it is our answer.
Un enfoque ingenuo es iterar todos los números del 1 al n y averiguar qué número tiene la suma máxima de dígitos. La complejidad temporal de esta solución es O(n).
Un enfoque eficiente es iterar de n a 1. Haga lo siguiente para cada dígito del número actual, si el dígito no es cero, redúzcalo en uno y cambie todos los demás dígitos a nueve a la derecha. Si la suma de los dígitos del entero resultante es estrictamente mayor que la suma de los dígitos de la respuesta actual, actualice la respuesta con el entero resultante. Si la suma del entero resultante es igual a la respuesta actual, entonces si el entero resultante es mayor que la respuesta actual, actualice la respuesta actual con el entero resultante.
¿Cómo reducir un dígito y cambiar todos los demás dígitos a su derecha a 9?
Sea x nuestro número actual. Podemos encontrar el siguiente número para el dígito actual usando la siguiente fórmula. En la siguiente fórmula, b es una potencia de 10 para representar la posición del dígito actual. Después de cada iteración, reducimos x a x/10 y cambiamos b a b * 10.
Usamos (x – 1) * b + (b – 1);
Esta línea se puede explicar además como, si el número es x = 521 y b = 1, entonces
- (521 – 1) * 1 + (1-1) lo que da 520, que es lo que debemos hacer, reducir el número de posición en 1 y reemplazar todos los demás números a la derecha por 9.
- Después de que x /= 10 te da x como 52 y b*=10 te da b como 10, que nuevamente se ejecuta como (52-1)*(10) + 9 lo que te da 519, que es lo que tenemos que hacer, reducir el índice actual en 1 y aumentar todos los demás derechos en 9.
C++
// CPP program to find the
// number with maximum digit
// sum.
#include <bits/stdc++.h>
using namespace std;
// function to calculate the
// sum of digits of a number.
int sumOfDigits(int a)
{
int sum = 0;
while (a)
{
sum += a % 10;
a /= 10;
}
return sum;
}
// Returns the maximum number
// with maximum sum of digits.
int findMax(int x)
{
// initializing b as 1 and
// initial max sum to be of n
int b = 1, ans = x;
// iterates from right to
// left in a digit
while (x)
{
// while iterating this
// is the number from
// from right to left
int cur = (x - 1) * b + (b - 1);
// calls the function to
// check if sum of cur is
// more than of ans
if (sumOfDigits(cur) > sumOfDigits(ans) ||
(sumOfDigits(cur) == sumOfDigits(ans) &&
cur > ans))
ans = cur;
// reduces the number to one unit less
x /= 10;
b *= 10;
}
return ans;
}
// driver program
int main()
{
int n = 521;
cout << findMax(n);
return 0;
}
Java
// Java program to find the
// number with maximum digit
// sum.
import java.io.*;
class GFG {
// function to calculate the
// sum of digits of a number.
static int sumOfDigits(int a)
{
int sum = 0;
while (a!=0)
{
sum += a % 10;
a /= 10;
}
return sum;
}
// Returns the maximum number
// with maximum sum of digits.
static int findMax(int x)
{
// initializing b as 1 and
// initial max sum to be of n
int b = 1, ans = x;
// iterates from right to
// left in a digit
while (x!=0)
{
// while iterating this
// is the number from
// from right to left
int cur = (x - 1) * b + (b - 1);
// calls the function to
// check if sum of cur is
// more then of ans
if (sumOfDigits(cur) > sumOfDigits(ans) ||
(sumOfDigits(cur) == sumOfDigits(ans) &&
cur > ans))
ans = cur;
// reduces the number to one unit less
x /= 10;
b *= 10;
}
return ans;
}
// driver program
public static void main (String[] args)
{
int n = 521;
System.out.println(findMax(n));
}
}
/*This article is contributed by Nikita Tiwari.*/
Python3
# Python 3 program to # find the number # with maximum digit # sum. # function to calculate # the sum of digits of # a number. def sumOfDigits(a) : sm = 0 while (a!=0) : sm = sm + a % 10 a = a // 10 return sm # Returns the maximum number # with maximum sum of digits. def findMax(x) : # initializing b as 1 # and initial max sum # to be of n b = 1 ans = x # iterates from right # to left in a digit while (x!=0) : # while iterating this # is the number from # right to left cur = (x - 1) * b + (b - 1) # calls the function to # check if sum of cur is # more then of ans if (sumOfDigits(cur) > sumOfDigits(ans) or (sumOfDigits(cur) == sumOfDigits(ans) and cur > ans)) : ans = cur # reduces the number # to one unit less x =x // 10 b = b * 10 return ans # driver program to test the above function n = 521 print(findMax(n)) # This article is contributed by Nikita Tiwari.
C#
// C# program to find the number
// with maximum digit sum.
using System;
class GFG {
// function to calculate the
// sum of digits of a number.
static int sumOfDigits(int a)
{
int sum = 0;
while (a!=0)
{
sum += a % 10;
a /= 10;
}
return sum;
}
// Returns the maximum number
// with maximum sum of digits.
static int findMax(int x)
{
// initializing b as 1 and
// initial max sum to be of n
int b = 1, ans = x;
// iterates from right to
// left in a digit
while (x!=0)
{
// while iterating this
// is the number from
// from right to left
int cur = (x - 1) * b + (b - 1);
// calls the function to
// check if sum of cur is
// more then of ans
if (sumOfDigits(cur) > sumOfDigits(ans) ||
(sumOfDigits(cur) == sumOfDigits(ans) &&
cur > ans))
ans = cur;
// reduces the number to one unit less
x /= 10;
b *= 10;
}
return ans;
}
// driver program
public static void Main()
{
int n = 521;
Console.WriteLine(findMax(n));
}
}
// This article is contributed by Anant Agarwal.
PHP
<?php
// PHP program to find the
// number with maximum digit
// sum.
// function to calculate the
// sum of digits of a number.
function sumOfDigits($a)
{
$sum = 0;
while ($a)
{
$sum += $a % 10;
$a = (int)$a / 10;
}
return $sum;
}
// Returns the maximum number
// with maximum sum of digits.
function findMax( $x)
{
// initializing b as 1 and
// initial max sum to be of n
$b = 1; $ans = $x;
// iterates from right to
// left in a digit
while ($x)
{
// while iterating this
// is the number from
// from right to left
$cur = ($x - 1) * $b +
($b - 1);
// calls the function to
// check if sum of cur is
// more then of ans
if (sumOfDigits($cur) > sumOfDigits($ans) ||
(sumOfDigits($cur) == sumOfDigits($ans) &&
$cur > $ans))
$ans = $cur;
// reduces the number
// to one unit less
$x = (int)$x / 10;
$b *= 10;
}
return $ans;
}
// Driver Code
$n = 521;
echo findMax($n);
// This code is contributed by ajit
?>
Javascript
<script>
// Javascript program to find the
// number with maximum digit
// sum.
// Function to calculate the
// sum of digits of a number.
function sumOfDigits(a)
{
var sum = 0;
while (a != 0)
{
sum += a % 10;
a = parseInt(a / 10);
}
return sum;
}
// Returns the maximum number
// with maximum sum of digits.
function findMax(x)
{
// Initializing b as 1 and
// initial max sum to be of n
var b = 1, ans = x;
// Iterates from right to
// left in a digit
while (x != 0)
{
// While iterating this
// is the number from
// from right to left
var cur = (x - 1) * b + (b - 1);
// Calls the function to
// check if sum of cur is
// more then of ans
if (sumOfDigits(cur) >
sumOfDigits(ans) ||
(sumOfDigits(cur) ==
sumOfDigits(ans) &&
cur > ans))
ans = cur;
// Reduces the number to one unit less
x = parseInt(x / 10);
b *= 10;
}
return ans;
}
// Driver Code
var n = 521;
document.write(findMax(n));
// This code is contributed by todaysgaurav
</script>
Producción :
499
Complejidad del tiempo: O(m) donde m es el número de dígitos en n.
Este artículo es una contribución de Striver . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA