Dado un número positivo N , el objetivo es encontrar el número más grande que se puede formar después de eliminar K dígitos de N .
Ejemplos:
Entrada: N = 6358, K = 1
Salida: 658
Entrada: N = 2589, K = 2
Salida: 89
Acercarse:
- Iterar un bucle K veces.
- Durante cada iteración, elimine cada dígito del valor actual de N una vez y almacene el máximo de todos los números obtenidos.
- Para lograr esto, almacenamos el máximo de (N / (i * 10)) * i + (N % i) donde i oscila entre [1, 10 l – 1 ] donde l denota el número de dígitos del actual valor de n
- Considere este máximo como el valor actual de N y continúe con la siguiente iteración y repita el paso anterior.
- Por lo tanto, después de cada iteración, se elimina el menor dígito del valor actual de N. Al repetir el proceso K veces, obtenemos el mayor número posible.
Por ejemplo:
Analicemos este enfoque para N = 6358, K = 1
Las diferentes posibilidades después de eliminar cada dígito una vez son las siguientes:
(6358 / 10) * 1 + 6358 % 1 = 635 + 0 = 635
(6358 / 100) * 10 + 6358 % 10 = 630 + 8 = 638
(6358 / 1000) * 100 + 6358 % 100 = 600 + 58 = 658
(6358 / 10000) * 1000 + 6358 % 1000 = 0 + 358 = 358
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to return the
// largest number possible
int maxnumber(int n, int k)
{
// Generate the largest number
// after removal of the least
// K digits one by one
for (int j = 0; j < k; j++) {
int ans = 0;
int i = 1;
// Remove the least digit
// after every iteration
while (n / i > 0) {
// Store the numbers formed after
// removing every digit once
int temp = (n / (i * 10))
* i
+ (n % i);
i *= 10;
// Compare and store the maximum
ans = max(ans, temp);
}
// Store the largest
// number remaining
n = ans;
}
// Return the remaining number
// after K removals
return n;
}
// Driver code
int main()
{
int n = 6358;
int k = 1;
cout << maxnumber(n, k) << endl;
return 0;
}
Java
// Java program to implement
// the above approach
import java.util.*;
import java.math.*;
class GFG {
// Function to return the
// largest number possible
static int maxnumber(int n, int k)
{
// Generate the largest number
// after removal of the least
// K digits one by one
for (int j = 0; j < k; j++) {
int ans = 0;
int i = 1;
// Remove the least digit
// after every iteration
while (n / i > 0) {
// Store the numbers formed after
// removing every digit once
int temp = (n / (i * 10))
* i
+ (n % i);
i *= 10;
// Compare and store the maximum
ans = Math.max(ans, temp);
}
n = ans;
}
// Return the remaining number
// after K removals
return n;
}
// Driver code
public static void main(String[] args)
{
int n = 6358;
int k = 1;
System.out.println(maxnumber(n, k));
}
}
Python3
# Python program to implement # the above approach def maxnumber(n, k): # Function to return the # largest number possible for i in range(0, k): # Generate the largest number # after removal of the least K digits # one by one ans = 0 i = 1 while n // i > 0: # Remove the least digit # after every iteration temp = (n//(i * 10))*i + (n % i) i *= 10 # Store the numbers formed after # removing every digit once # Compare and store the maximum if temp > ans: ans = temp n = ans # Return the remaining number # after K removals return ans; n = 6358 k = 1 print(maxnumber(n, k))
C#
// C# program to implement
// the above approach
using System;
class GFG {
// Function to return the
// largest number possible
static int maxnumber(int n, int k)
{
// Generate the largest number
// after removal of the least
// K digits one by one
for (int j = 0; j < k; j++) {
int ans = 0;
int i = 1;
// Remove the least digit
// after every iteration
while (n / i > 0) {
// Store the numbers formed after
// removing every digit once
int temp = (n / (i * 10))
* i
+ (n % i);
i *= 10;
// Compare and store the maximum
if (temp > ans)
ans = temp;
}
// Store the largest
// number remaining
n = ans;
}
// Return the remaining number
// after K removals
return n;
}
// Driver code
static public void Main()
{
int n = 6358;
int k = 1;
Console.WriteLine(maxnumber(n, k));
}
}
Javascript
<script>
// Javascript program to implement
// the above approach
// Function to return the
// largest number possible
function maxnumber(n, k)
{
// Generate the largest number
// after removal of the least
// K digits one by one
for (var j = 0; j < k; j++) {
var ans = 0;
var i = 1;
// Remove the least digit
// after every iteration
while (parseInt(n / i) > 0) {
// Store the numbers formed after
// removing every digit once
var temp = parseInt(n / (i * 10))
* i
+ (n % i);
i *= 10;
// Compare and store the maximum
ans = Math.max(ans, temp);
}
// Store the largest
// number remaining
n = ans;
}
// Return the remaining number
// after K removals
return n;
}
// Driver code
var n = 6358;
var k = 1;
document.write( maxnumber(n, k));
</script>
Producción:
658
Complejidad de tiempo: O (log 10 N)
Espacio Auxiliar: O(1)