Mayor número N que se puede reducir a 0 en K pasos

Posted on by Rudeus Greyrat

Dado un número entero N . Se realizan las siguientes tareas:  

  • Se anota el número.
  • El primer dígito de N se resta de N y el valor resultante se vuelve a almacenar en N.
  • Se anota nuevamente el nuevo valor de N.
  • Este proceso continúa hasta que N se convierte en 0. Finalmente, se anota 0 al final .

Por ejemplo, tome N = 13 . Los números anotados en el proceso de reducción de 13 a 0 serán:  

  • 13
  • 13 – 1 = 12
  • 12 – 1 = 11
  • 11 – 1 = 10
  • 10 – 1 = 9
  • 9 – 9 = 0 
     

Dado un número entero K , que es el recuento total de números anotados en el proceso de reducción de un número N a 0 como se describió anteriormente, la tarea es encontrar el mayor valor posible del número inicial N.

Ejemplos: 

Entrada: k = 2 
Salida: 9 
Explicación: Números anotados = {9} 

  • Resta el dígito inicial: 9 – 9 = 0. Números anotados = {9, 0} 
     

Entrada: k = 3 
Salida: 10 
Explicación: Números anotados = {10} 

  • Resta el dígito inicial: 10 – 1 = 9. Números anotados = {10, 9}
  • Resta el dígito inicial: 9 – 9 = 0. Números anotados = {10, 9, 0}

Planteamiento: La idea es observar que el valor máximo posible de N siempre será menor que 10*K. Por lo tanto, la idea es aplicar la búsqueda binaria en el rango K a 10*K y buscar el mayor número que se pueda reducir a 0 en K pasos.
Para encontrar el mayor número posible:  

  1. Inicialice de izquierda a k y de derecha a k*10 .
  2. Inicializar medio a (izquierda + derecha) / 2 .
  3. Obtenga el conteo del número anotado para convertir mid a 0 y guárdelo en len .
  4. Siga el enfoque de divide y vencerás: Mientras que len no es igual a k : 
    • Actualice el medio al actual (izquierda + derecha) / 2 .
    • Obtenga el conteo al comenzar con mid .
    • Si el recuento es superior a la mitad , actualice a la derecha hasta la mitad .
    • De lo contrario, actualice de izquierda a mitad .
  5. Ahora, mid tiene un valor que dará como resultado k enteros escritos.
  6. Para encontrar el mayor número de este tipo: 
    • Mientras que la cuenta es igual a k :
    • Si el conteo actual no es igual al conteo obtenido al tomar mid+1 , rompa
    • De lo contrario, siga incrementando mid en 1.
  7. mid es ahora el entero más grande posible si se escriben  k enteros.
     

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

C++

// C++ program to implement above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Utility function to return the first
// digit of a number.
int firstDigit(int n)
{
    // Remove last digit from number
    // till only one digit is left
    while (n >= 10) {
        n /= 10;
    }
 
    // return the first digit
    return n;
}
 
// Utility function that returns the count of numbers
// written down when starting from n
int getCount(int n)
{
    int count = 1;
 
    while (n != 0) {
        int leadDigit = firstDigit(n);
        n -= leadDigit;
        count++;
    }
    return count;
}
 
// Function to find the largest number N which
// can be reduced to 0 in K steps
int getLargestNumber(int k)
{
    int left = k;
    int right = k * 10;
    int mid = (left + right) / 2;
 
    // Get the sequence length of the mid point
    int len = getCount(mid);
 
    // Until k sequence length is reached
    while (len != k) {
 
        // Update mid point
        mid = (left + right) / 2;
 
        // Get count of the new mid point
        len = getCount(mid);
 
        if (len > k) {
 
            // Update right to mid
            right = mid;
        }
        else {
 
            // Update left to mid
            left = mid;
        }
    }
 
    // Increment mid point by one while count
    // is equal to k to get the maximum value
    // of mid point
    while (len == k) {
 
        if (len != getCount(mid + 1)) {
            break;
        }
 
        mid++;
    }
 
    return (mid);
}
 
// Driver Code
int main()
{
    int k = 3;
 
    cout << getLargestNumber(k);
 
    return 0;
}

Java

// Java program to implement above approach
import java.io.*;
 
class GFG
{
     
// Utility function to return the first
// digit of a number.
static int firstDigit(int n)
{
    // Remove last digit from number
    // till only one digit is left
    while (n >= 10)
    {
        n /= 10;
    }
 
    // return the first digit
    return n;
}
 
// Utility function that returns the count of numbers
// written down when starting from n
static int getCount(int n)
{
    int count = 1;
 
    while (n != 0)
    {
        int leadDigit = firstDigit(n);
        n -= leadDigit;
        count++;
    }
    return count;
}
 
// Function to find the largest number N which
// can be reduced to 0 in K steps
static int getLargestNumber(int k)
{
    int left = k;
    int right = k * 10;
    int mid = (left + right) / 2;
 
    // Get the sequence length of the mid point
    int len = getCount(mid);
 
    // Until k sequence length is reached
    while (len != k)
    {
 
        // Update mid point
        mid = (left + right) / 2;
 
        // Get count of the new mid point
        len = getCount(mid);
 
        if (len > k)
        {
 
            // Update right to mid
            right = mid;
        }
        else
        {
 
            // Update left to mid
            left = mid;
        }
    }
 
    // Increment mid point by one while count
    // is equal to k to get the maximum value
    // of mid point
    while (len == k)
    {
 
        if (len != getCount(mid + 1))
        {
            break;
        }
 
        mid++;
    }
 
    return (mid);
}
 
    // Driver Code
    public static void main (String[] args)
    {
 
        int k = 3;
        System.out.println (getLargestNumber(k));
    }
}
 
// This code is contributed by jit_t

Python3

# Python3 program to implement above approach
 
# Utility function to return the first
# digit of a number.
def firstDigit(n) :
 
    # Remove last digit from number
    # till only one digit is left
    while (n >= 10) :
        n //= 10;
     
    # return the first digit
    return n;
 
# Utility function that returns
# the count of numbers written
# down when starting from n
def getCount(n) :
     
    count = 1;
 
    while (n != 0) :
        leadDigit = firstDigit(n);
        n -= leadDigit;
        count += 1;
     
    return count;
 
# Function to find the largest number N
# which can be reduced to 0 in K steps
def getLargestNumber(k) :
 
    left = k;
    right = k * 10;
    mid = (left + right) // 2;
 
    # Get the sequence length of the mid point
    length = getCount(mid);
 
    # Until k sequence length is reached
    while (length != k) :
 
        # Update mid point
        mid = (left + right) // 2;
 
        # Get count of the new mid point
        length = getCount(mid);
 
        if (length > k) :
 
            # Update right to mid
            right = mid;
         
        else :
 
            # Update left to mid
            left = mid;
         
    # Increment mid point by one while count
    # is equal to k to get the maximum value
    # of mid point
    while (length == k) :
 
        if (length != getCount(mid + 1)) :
            break;
         
        mid += 1;
     
    return mid;
 
# Driver Code
if __name__ == "__main__" :
 
    k = 3;
 
    print(getLargestNumber(k));
 
# This code is contributed by Ryuga

C#

// C# implementation of the approach
using System;
 
class GFG
{
 
// Utility function to return the first
// digit of a number.
static int firstDigit(int n)
{
    // Remove last digit from number
    // till only one digit is left
    while (n >= 10)
    {
        n /= 10;
    }
 
    // return the first digit
    return n;
}
 
// Utility function that returns the count of numbers
// written down when starting from n
static int getCount(int n)
{
    int count = 1;
 
    while (n != 0)
    {
        int leadDigit = firstDigit(n);
        n -= leadDigit;
        count++;
    }
    return count;
}
 
// Function to find the largest number N which
// can be reduced to 0 in K steps
static int getLargestNumber(int k)
{
    int left = k;
    int right = k * 10;
    int mid = (left + right) / 2;
 
    // Get the sequence length of the mid point
    int len = getCount(mid);
 
    // Until k sequence length is reached
    while (len != k)
    {
 
        // Update mid point
        mid = (left + right) / 2;
 
        // Get count of the new mid point
        len = getCount(mid);
 
        if (len > k)
        {
 
            // Update right to mid
            right = mid;
        }
        else
        {
 
            // Update left to mid
            left = mid;
        }
    }
 
    // Increment mid point by one while count
    // is equal to k to get the maximum value
    // of mid point
    while (len == k)
    {
 
        if (len != getCount(mid + 1))
        {
            break;
        }
 
        mid++;
    }
 
    return (mid);
}
 
// Driver Code
public static void Main(String []args)
{
    int k = 3;
 
    Console.WriteLine( getLargestNumber(k));
}
}
 
// This code is contributed by Arnab Kundu

PHP

<?php
// PHP program to implement above approach
 
// Utility function to return the
// first digit of a number.
function firstDigit($n)
{
     
    // Remove last digit from number
    // till only one digit is left
    while ($n >= 10)
    {
        $n = (int)($n / 10);
    }
 
    // return the first digit
    return $n;
}
 
// Utility function that returns the
// count of numbers written down when
// starting from n
function getCount($n)
{
    $count = 1;
 
    while ($n != 0)
    {
        $leadDigit = firstDigit($n);
        $n -= $leadDigit;
        $count++;
    }
    return $count;
}
 
// Function to find the largest number N
// which can be reduced to 0 in K steps
function getLargestNumber($k)
{
    $left = $k;
    $right = $k * 10;
    $mid = (int)(($left + $right) / 2);
 
    // Get the sequence length
    // of the mid point
    $len = getCount($mid);
 
    // Until k sequence length is reached
    while ($len != $k)
    {
 
        // Update mid point
        $mid = (int)(($left + $right) / 2);
 
        // Get count of the new mid point
        $len = getCount($mid);
 
        if ($len > $k)
        {
 
            // Update right to mid
            $right = $mid;
        }
        else
        {
 
            // Update left to mid
            $left = $mid;
        }
    }
 
    // Increment mid point by one while count
    // is equal to k to get the maximum value
    // of mid point
    while ($len == $k)
    {
        if ($len != getCount($mid + 1))
        {
            break;
        }
 
        $mid++;
    }
 
    return ($mid);
}
 
// Driver Code
$k = 3;
echo(getLargestNumber($k));
 
// This code is contributed by Code_Mech.
?>

Javascript

<script>
    // Javascript implementation of the approach
 
      // Utility function to return the first
    // digit of a number.
    function firstDigit(n)
    {
        // Remove last digit from number
        // till only one digit is left
        while (n >= 10)
        {
            n = parseInt(n / 10, 10);
        }
 
        // return the first digit
        return n;
    }
 
    // Utility function that returns the count of numbers
    // written down when starting from n
    function getCount(n)
    {
        let count = 1;
 
        while (n != 0)
        {
            let leadDigit = firstDigit(n);
            n -= leadDigit;
            count++;
        }
        return count;
    }
 
    // Function to find the largest number N which
    // can be reduced to 0 in K steps
    function getLargestNumber(k)
    {
        let left = k;
        let right = k * 10;
        let mid = parseInt((left + right) / 2, 10);
 
        // Get the sequence length of the mid point
        let len = getCount(mid);
 
        // Until k sequence length is reached
        while (len != k)
        {
 
            // Update mid point
            mid = parseInt((left + right) / 2, 10);
 
            // Get count of the new mid point
            len = getCount(mid);
 
            if (len > k)
            {
 
                // Update right to mid
                right = mid;
            }
            else
            {
 
                // Update left to mid
                left = mid;
            }
        }
 
        // Increment mid point by one while count
        // is equal to k to get the maximum value
        // of mid point
        while (len == k)
        {
 
            if (len != getCount(mid + 1))
            {
                break;
            }
 
            mid++;
        }
 
        return (mid);
    }
     
    let k = 3;
   
    document.write( getLargestNumber(k));
 
</script>
Producción: 

10

 

Publicación traducida automáticamente

Artículo escrito por AbhijeetSridhar y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *