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)