Dado un número n, encuentre el número más grande menor o igual que n y los dígitos en orden no decreciente.
Ejemplos:
Input : n = 200 Output : 199 If the given number is 200, the largest number which is smaller or equal to it having digits in non decreasing order is 199. Input : n = 139 Output : 139
Método 1 (Fuerza bruta)
Comience desde n, para cada número verifique si sus dígitos están en orden no decreciente. Si es así, entonces regresa. De lo contrario, busque el siguiente número hasta que encontremos el resultado.
C++
/* C++ program for brute force approach to find
largest number having digits in non-decreasing
order. */
#include<bits/stdc++.h>
using namespace std;
// Returns the required number
long long nondecdigits(long long n)
{
/* loop to recursively check the numbers less
than or equal to given number*/
long long int x = 0;
for (x=n; x>=1; x--)
{
int no = x;
int prev_dig = 11;
// Keep traversing digits from
// right to left. For every digit
// check if it is smaller than prev_dig
bool flag = true;
while (no != 0)
{
if (prev_dig < no%10)
{
flag = false;
break;
}
prev_dig = no % 10;
no /= 10;
}
// We found the required number
if (flag == true)
break;
}
return x;
}
// Driver program
int main()
{
long long n = 200;
cout << nondecdigits(n);
return 0;
}
Java
// Java program for brute force
// approach to find largest number
// having digits in non-decreasing
// order.
import java.io.*;
class GFG
{
// Returns the required number
static int nondecdigits(int n)
{
// loop to recursively check
// the numbers less than or
// equal to given number
int x = 0;
for (x = n; x >= 1; x--)
{
int no = x;
int prev_dig = 11;
// Keep traversing digits
// from right to left. For
// every digit check if it
// is smaller than prev_dig
boolean flag = true;
while (no != 0)
{
if (prev_dig < no % 10)
{
flag = false;
break;
}
prev_dig = no % 10;
no /= 10;
}
// We found the
// required number
if (flag == true)
break;
}
return x;
}
// Driver Code
public static void main (String[] args)
{
int n = 200;
System.out.println (nondecdigits(n));
}
}
// This code is contributed by ajit
Python3
# Python 3 program for brute force approach # to find largest number having digits in # non-decreasing order. # Returns the required number def nondecdigits( n): ''' loop to recursively check the numbers less than or equal to given number''' x = 0 for x in range(n, 0, -1): no = x prev_dig = 11 # Keep traversing digits from # right to left. For every digit # check if it is smaller than prev_dig flag = True while (no != 0): if (prev_dig < no % 10): flag = False break prev_dig = no % 10 no //= 10 # We found the required number if (flag == True): break return x # Driver Code if __name__=="__main__": n = 200 print(nondecdigits(n)) # This code is contributed by ita_c
C#
// C# program for brute
// force approach to find
// largest number having
// digits in non-decreasing
// order.
using System;
class GFG
{
// Returns the required number
static int nondecdigits(int n)
{
// loop to recursively
// check the numbers less
// than or equal to given
// number
int x = 0;
for (x = n; x >= 1; x--)
{
int no = x;
int prev_dig = 11;
// Keep traversing digits
// from right to left. For
// every digit check if it
// is smaller than prev_dig
bool flag = true;
while (no != 0)
{
if (prev_dig < no % 10)
{
flag = false;
break;
}
prev_dig = no % 10;
no /= 10;
}
// We found the
// required number
if (flag == true)
break;
}
return x;
}
// Driver Code
static public void Main ()
{
int n = 200;
Console.WriteLine(nondecdigits(n));
}
}
// This code is contributed
// by akt_mit
PHP
<?php
// PHP program for brute
// force approach to find
// largest number having
// digits in non-decreasing
// order.
// Returns the required number
function nondecdigits($n)
{
/* loop to recursively
check the numbers less
than or equal to
given number*/
$x = 0;
for ($x = $n; $x >= 1; $x--)
{
$no = $x;
$prev_dig = 11;
// Keep traversing
// digits from
// right to left.
// For every digit
// check if it is
// smaller than prev_dig
$flag = true;
while ($no != 0)
{
if ($prev_dig < $no%10)
{
$flag = false;
break;
}
$prev_dig = $no % 10;
$no /= 10;
}
// We found the
// required number
if ($flag == true)
break;
}
return $x;
}
// Driver Code
$n = 200;
echo nondecdigits($n);
// This code is contributed by ajt
?>
Javascript
<script>
// Javascript program for brute force
// approach to find largest number
// having digits in non-decreasing
// order.
// Returns the required number
function nondecdigits(n)
{
// Loop to recursively check
// the numbers less than or
// equal to given number
let x = 0;
for(x = n; x >= 1; x--)
{
let no = x;
let prev_dig = 11;
// Keep traversing digits
// from right to left. For
// every digit check if it
// is smaller than prev_dig
let flag = true;
while (no != 0)
{
if (prev_dig < no % 10)
{
flag = false;
break;
}
prev_dig = no % 10;
no = Math.floor(no / 10);
}
// We found the
// required number
if (flag == true)
break;
}
return x;
}
// Driver code
let n = 200;
document.write(nondecdigits(n));
// This code is contributed by avanitrachhadiya2155
</script>
Producción:
199
Enfoque eficiente
El método discutido anteriormente no es muy eficiente ya que solo daría resultados para números hasta 10 ^ 5, pero si el número es muy grande, contiene 10 ^ 5 dígitos.
Entonces, discutiremos otro método para números tan grandes.
Paso 1: almacena los dígitos del número en una array o un vector.
Paso 2: comience a recorrer la array desde el dígito desde la posición más a la derecha hasta la más a la izquierda en el número dado.
Paso 3: Si un dígito es mayor que el dígito a su derecha, observe el índice de ese dígito en esa array y disminuya ese dígito en uno.
Paso 4: Continúe actualizando ese índice hasta que atraviese completamente la array como se explicó en el paso 3.
Paso 4: Establezca todos los dígitos a la derecha de ese índice como 9.
Paso 5: imprima la array ya que este es el número requerido.
Supongamos que el número es 200, los dígitos serán 2, 0, 0. El índice en el que el dígito más a la izquierda es mayor que el dígito de la derecha es el índice 1 (después del índice 1), por lo que el número en el índice 1 será 2 – 1 = 1 y todos los dígitos a la derecha serán 9. Entonces, la array final será 1, 9, 9. Y el número requerido será 199.
C++
/* C++ program for efficient approach to find
largest number having digits in non-decreasing
order. */
#include<bits/stdc++.h>
using namespace std;
// Prints the largest number smaller than s and
// digits in non-decreasing order.
void nondecdigits(string s)
{
long long m = s.size();
/* array to store digits of number */
long long a[m];
/* conversion of characters of string int number */
for (long long i=0; i<m; i++)
a[i] = s[i] - '0';
/* variable holds the value of index after which
all digits are set 9 */
long long level = m-1;
for (long long i=m-1; i>0; i--)
{
/* Checking the condition if the digit is
less than its left digit */
if (a[i] < a[i-1])
{
a[i-1]--;
level=i-1;
}
}
/* If first digit is 0 no need to print it */
if (a[0] != 0)
{
for (long long i=0; i<=level; i++)
cout << a[i];
for (long long i=level+1; i<m; i++)
cout << "9";
}
else
{
for (long long i=1; i<level; i++)
cout << a[i];
for (long long i=level+1; i<m; i++)
cout << "9";
}
}
// Driver function
int main()
{
string n = "200";
nondecdigits(n);
return 0;
}
Java
/* Java program for efficient approach to find
largest number having digits in non-decreasing
order. */
import java.util.*;
class GFG
{
// Prints the largest number smaller than s and
// digits in non-decreasing order.
static void nondecdigits(String s)
{
int m = s.length();
/* array to store digits of number */
int[] a = new int[m + 1];
/* conversion of characters of string int number */
for (int i = 0; i < m; i++)
a[i] = (int)s.charAt(i) - (int)'0';
/* variable holds the value of index after which
all digits are set 9 */
int level = m - 1;
for (int i = m - 1; i > 0; i--)
{
/* Checking the condition if the digit is
less than its left digit */
if (a[i] < a[i - 1])
{
a[i - 1]--;
level = i - 1;
}
}
/* If first digit is 0 no need to print it */
if (a[0] != 0)
{
for (int i = 0; i <= level; i++)
System.out.print(a[i]);
for (int i = level + 1; i < m; i++)
System.out.print("9");
}
else
{
for (int i = 1; i < level; i++)
System.out.print(a[i]);
for (int i = level + 1; i < m; i++)
System.out.print("9");
}
}
// Driver code
public static void main(String[] args)
{
String n = "200";
nondecdigits(n);
}
}
// This code is contributed by chandan_jnu
Python3
# Python3 program for efficient approach to
# find largest number having digits in
# non-decreasing order.
# Prints the largest number smaller than s
# and digits in non-decreasing order.
def nondecdigits(s):
m = len(s);
# array to store digits of number
a = [0] * m;
# conversion of characters of string
# int number
for i in range(m):
a[i] = ord(s[i]) - ord('0');
# variable holds the value of index
# after which all digits are set 9
level = m - 1;
for i in range(m - 1, 0, -1):
# Checking the condition if the digit
# is less than its left digit
if (a[i] < a[i - 1]):
a[i - 1] -= 1;
level = i - 1;
# If first digit is 0 no need to print it */
if (a[0] != 0):
for i in range(level + 1):
print(a[i], end = "");
for i in range(level + 1, m):
print("9", end = "");
else:
for i in range(1, level):
print(a[i], end = "");
for i in range(level + 1, m):
print("9", end = "");
# Driver Code
n = "200";
nondecdigits(n);
# This code is contributed by mits
C#
/* C# program for efficient approach to find
largest number having digits in non-decreasing
order. */
using System;
class GFG
{
// Prints the largest number smaller than s and
// digits in non-decreasing order.
static void nondecdigits(string s)
{
int m = s.Length;
/* array to store digits of number */
int[] a = new int[m + 1];
/* conversion of characters of string int number */
for (int i = 0; i < m; i++)
a[i] = (int)s[i] - (int)'0';
/* variable holds the value of index after which
all digits are set 9 */
int level = m - 1;
for (int i = m - 1; i > 0; i--)
{
/* Checking the condition if the digit is
less than its left digit */
if (a[i] < a[i - 1])
{
a[i - 1]--;
level = i - 1;
}
}
/* If first digit is 0 no need to print it */
if (a[0] != 0)
{
for (int i = 0; i <= level; i++)
Console.Write(a[i]);
for (int i = level + 1; i < m; i++)
Console.Write("9");
}
else
{
for (int i = 1; i < level; i++)
Console.Write(a[i]);
for (int i = level + 1; i < m; i++)
Console.Write("9");
}
}
// Driver code
static void Main()
{
string n = "200";
nondecdigits(n);
}
}
// This code is contributed by chandan_jnu
PHP
<?php
/* PHP program for efficient
approach to find largest number
having digits in non-decreasing
order. */
// Prints the largest number
// smaller than s and digits
// in non-decreasing order.
function nondecdigits($s)
{
$m = strlen($s);
/* array to store
digits of number */
$a[$m] = 0;
/* conversion of characters
of string int number */
for ($i = 0; $i < $m; $i++)
$a[$i] = $s[$i] - '0';
/* variable holds the
value of index after
which all digits are set 9 */
$level = $m - 1;
for ($i = $m - 1; $i > 0; $i--)
{
/* Checking the condition
if the digit is less than
its left digit */
if ($a[$i] < $a[$i - 1])
{
$a[$i - 1]--;
$level = $i - 1;
}
}
/* If first digit is 0
no need to print it */
if ($a[0] != 0)
{
for ($i = 0;
$i <= $level; $i++)
echo $a[$i];
for ($i = $level + 1;
$i < $m; $i++)
echo "9";
}
else
{
for ($i = 1; $i < $level; $i++)
echo $a[$i];
for ($i = $level + 1;
$i < $m; $i++)
echo "9";
}
}
// Driver Code
$n = "200";
nondecdigits($n);
// This code is contributed
// by ajit
?>
Javascript
<script>
// Javascript program for efficient approach
// to find largest number having digits in
// non-decreasing order.
// Prints the largest number smaller than
// s and digits in non-decreasing order.
function nondecdigits(s)
{
var m = s.length;
// Array to store digits of number
var a = Array.from({length: m + 1}, (_, i) => 0);
// Conversion of characters of string var number
for(i = 0; i < m; i++)
a[i] = s.charAt(i).charCodeAt(0) -
'0'.charCodeAt(0);
// Variable holds the value of index
// after which all digits are set 9
var level = m - 1;
for(i = m - 1; i > 0; i--)
{
// Checking the condition if the digit is
// less than its left digit
if (a[i] < a[i - 1])
{
a[i - 1]--;
level = i - 1;
}
}
// If first digit is 0 no need to print it
if (a[0] != 0)
{
for(i = 0; i <= level; i++)
document.write(a[i]);
for(i = level + 1; i < m; i++)
document.write("9");
}
else
{
for(i = 1; i < level; i++)
document.write(a[i]);
for(i = level + 1; i < m; i++)
document.write("9");
}
}
// Driver code
var n = "200";
nondecdigits(n);
// This code is contributed by Princi Singh
</script>
Producción:
199
Complejidad del tiempo La complejidad del tiempo es O(d) donde d es no. de dígitos en el número.
Este artículo es una contribución de Ayush Jha . 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