Reduzca un número N en D como máximo para maximizar el conteo de nueves finales

Dados dos enteros positivos N y D , la tarea es disminuir el valor de N en D como máximo, de modo que N contenga el recuento máximo de 9 s finales.

Ejemplos:

Entrada: N = 1025, D = 6 
Salida: 1019 
Explicación: 
Decrementar N en 6 modifica N a 1019, que consiste en el conteo máximo posible de 9 finales. 
Por lo tanto, la salida requerida es 1019.

Entrada: N = 1025, D = 5 
Salida: 1025 
Decrementando N por todos los valores posibles hasta D(= 5), no se puede obtener ningún número que contenga 9 al final. 
Por lo tanto, la salida requerida es 1025.

Enfoque ingenuo: el enfoque más simple para resolver este problema es iterar sobre el rango [0, D] usando la variable i y disminuir el valor de N en i . Finalmente, imprima el valor de N que contiene el recuento máximo posible de 9 finales . 
Complejidad de Tiempo: O(D * log ₁₀ (N))  
Espacio Auxiliar: O(1)

Enfoque eficiente: el enfoque anterior se puede optimizar en función de las siguientes observaciones: 
 

N % pow(10, i) da los últimos i dígitos de N 
 

Siga los pasos a continuación para resolver el problema:

• Inicialice una variable, por ejemplo, res para almacenar el valor decrementado de N con un recuento máximo de 9 finales .
• Inicialice una variable, por ejemplo, cntDigits para almacenar el recuento de dígitos en N .
• Iterar sobre el rango [1, cntDigits] usando la variable i y verificar si N % pow(10, i) es mayor o igual que D o no. Si se encuentra que es cierto, imprima el valor de res .
• De lo contrario, actualice res a N % pow(10, i) – 1 .

A continuación se muestra la implementación del enfoque anterior:

// CPP program for the above approach
#include <bits/stdc++.h>
#define ll long long int
using namespace std;
   
// Function to find a number with
// maximum count of trailing nine
void maxNumTrailNine(int n, int d)
{
    int res = n;
   
    // Stores count of digits in n
    int cntDigits = log10(n) + 1;
   
    // Stores power of 10
    int p10 = 10;
   
    for (int i = 1; i <= cntDigits; i++) {
   
        // If last i digits greater than
        // or equal to d
        if (n % p10 >= d) {
            break;
        }
   
        else {
   
            // Update res
            res = n - n % p10 - 1;
        }
   
        // Update p10
        p10 = p10 * 10;
    }
    cout << res;
}
   
// Driver Code
int main()
{
    int n = 1025, d = 6;
   
    // Function Call
    maxNumTrailNine(n, d);
}

// Java program for the above approach
class GFG
{
         
    // Function to find a number with
    // maximum count of trailing nine
    static void maxNumTrailNine(int n, int d)
    {
        int res = n;
       
        // Stores count of digits in n
        int cntDigits = (int)Math.log10(n) + 1;
       
        // Stores power of 10
        int p10 = 10;
       
        for (int i = 1; i <= cntDigits; i++)
        {
       
            // If last i digits greater than
            // or equal to d
            if (n % p10 >= d)
            {
                break;
            }
       
            else
            {
       
                // Update res
                res = n - n % p10 - 1;
            }
       
            // Update p10
            p10 = p10 * 10;
        }
        System.out.println(res);
    }
   
    // Driver Code
    public static void main (String[] args)
    {
        int n = 1025, d = 6;
       
        // Function Call
        maxNumTrailNine(n, d);
    }
}
 
// This code is contribute by AnkThon

# Python3 program for the above approach
from math import log10
 
# Function to find a number with
# maximum count of trailing nine
def maxNumTrailNine(n, d):
    res = n
 
    # Stores count of digits in n
    cntDigits = int(log10(n) + 1)
 
    # Stores power of 10
    p10 = 10
 
    for i in range(1, cntDigits + 1):
 
        # If last i digits greater than
        # or equal to d
        if (n % p10 >= d):
            break
 
        else:
 
            # Update res
            res = n - n % p10 - 1
 
        # Update p10
        p10 = p10 * 10
 
    print (res)
 
# Driver Code
if __name__ == '__main__':
    n, d = 1025, 6
 
    # Function Call
    maxNumTrailNine(n, d)
 
    # This code is contributed by mohit kumar 29

// C# program for the above approach
using System;
class GFG
{
 
  // Function to find a number with
  // maximum count of trailing nine
  static void maxNumTrailNine(int n, int d)
  {
    int res = n;
 
    // Stores count of digits in n
    int cntDigits = (int)Math.Log10(n) + 1;
 
    // Stores power of 10
    int p10 = 10;     
    for (int i = 1; i <= cntDigits; i++)
    {
 
      // If last i digits greater than
      // or equal to d
      if (n % p10 >= d)
      {
        break;
      }
 
      else
      {
 
        // Update res
        res = n - n % p10 - 1;
      }
 
      // Update p10
      p10 = p10 * 10;
    }
    Console.WriteLine(res);
  }
 
  // Driver Code
  public static void Main(String[] args)
  {
    int n = 1025, d = 6;
 
    // Function Call
    maxNumTrailNine(n, d);
  }
}
 
 
// This code contributed by shikhasingrajput

<script>
 
// Javascript program for the above approach
   
// Function to find a number with
// maximum count of trailing nine
function maxNumTrailNine(n, d)
{
    let res = n;
   
    // Stores count of digits in n
    let cntDigits = parseInt(Math.log(n) /
                             Math.log(10)) + 1;
   
    // Stores power of 10
    let p10 = 10;
   
    for(let i = 1; i <= cntDigits; i++)
    {
         
        // If last i digits greater than
        // or equal to d
        if (n % p10 >= d)
        {
            break;
        }
        else
        {
             
            // Update res
            res = n - n % p10 - 1;
        }
   
        // Update p10
        p10 = p10 * 10;
    }
    document.write(res);
}
   
// Driver Code
let n = 1025, d = 6;
 
// Function Call
maxNumTrailNine(n, d);
 
// This code is contributed by souravmahato348
 
</script>

1019

Complejidad de tiempo: O(min(log ₁₀ (D), log ₁₀ (N))  
Espacio auxiliar: O(1)