Dado un entero positivo N y un dígito D , la tarea es encontrar el número no negativo más pequeño que se requiere agregar al número dado de manera que, después de la suma, el número resultante no contenga el dígito D .
Ejemplo:
Entrada: N = 25, D = 2
Salida: 5
Explicación: El número 30 es el número más pequeño después de 25 que no contiene el dígito 2. Por lo tanto, el número requerido debe agregarse a 25 para eliminar el dígito 2 es 30 – 25 = 5Entrada: N = 100, D = 0
Salida: 11
Explicación: El número 111 es el número más pequeño después de 100 que no tiene el dígito 0. Por lo tanto, el número requerido debe agregarse a 100 para eliminar el dígito 0 es 111 – 100 = 11
Enfoque: este problema se puede resolver iterando sobre los dígitos del número dado de derecha a izquierda y encontrando el dígito más cercano que no contiene el dígito D.
Siga los pasos que se mencionan a continuación:
- Iterar el número dado y verificar si el dígito dado está presente en el número o no.
- Si el dígito actual coincide con el dígito dado, verifique las siguientes condiciones :
- Si el dígito actual está en el rango de 1 a 9 , incremente el dígito actual en 1 y convierta todos los dígitos a su derecha en 0 .
- De lo contrario, si el dígito actual es 0 , aumente el dígito actual en 1 y haga que todos los dígitos sean 1
- La diferencia entre el número formado usando la condición anterior y el número original es el número más pequeño requerido.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to calculate smallest positive
// number to be added to remove
// the given digit
int smallestNumber(int n, int d)
{
// Copy the number to another variable
int temp = n;
int ans = 0, count = 0;
// Iterate over digits of the given
// number from right to left
while (temp > 0) {
// Extract the last digit of the
// number and check if it is
// equal to the given digit (d)
int remainder = temp % 10;
temp = temp / 10;
count++;
if (remainder == d) {
// If the digit which
// need to be replaced
// is equal to 0 then
// increment the current
// digit and make the all digits
// to its right 1
if (d == 0) {
string num = string(count, '1');
temp = temp * pow(10, count) + stoi(num);
}
// Else, increment the current digit
// by 1 and make the all digits
// to its right 0
else {
temp = temp * pow(10, count)
+ (remainder + 1)
* pow(10, count - 1);
}
// After the removal of given
// digit the number will be temp
// So, the required smallest
// number is (temp - n)
ans = temp - n;
// Set count as 0
count = 0;
}
}
// Return the result
return ans;
}
// Driver code
int main()
{
int N = 100;
int D = 0;
// print the smallest number required
// to be added to remove
// the digit 'D' in number 'N'
cout << smallestNumber(N, D) << "\n";
return 0;
}
Java
// Java implementation of the above approach
class GFG{
// Function to calculate smallest positive
// number to be added to remove
// the given digit
public static int smallestNumber(int n, int d)
{
// Copy the number to another variable
int temp = n;
int ans = 0, count = 0;
// Iterate over digits of the given
// number from right to left
while (temp > 0)
{
// Extract the last digit of the
// number and check if it is
// equal to the given digit (d)
int remainder = temp % 10;
temp = temp / 10;
count++;
if (remainder == d)
{
// If the digit which need to be
// replaced is equal to 0 then
// increment the current digit
// and make the all digits to
// its right 1
if (d == 0)
{
String num = "";
for(int i = 0; i < count; i++)
{
num = num + "1";
}
temp = (int)(temp * Math.pow(10, count) +
Integer.parseInt(num));
}
// Else, increment the current digit
// by 1 and make the all digits
// to its right 0
else
{
temp = (int) (temp * Math.pow(10, count) +
(remainder + 1) * Math.pow(10, count - 1));
}
// After the removal of given
// digit the number will be temp
// So, the required smallest
// number is (temp - n)
ans = temp - n;
// Set count as 0
count = 0;
}
}
// Return the result
return ans;
}
// Driver code
public static void main(String args[])
{
int N = 100;
int D = 0;
// Print the smallest number required
// to be added to remove the digit 'D'
// in number 'N'
System.out.println(smallestNumber(N, D));
}
}
// This code is contributed by _saurabh_jaiswal
Python3
# Python 3 implementation of the above approach # Function to calculate smallest positive # number to be added to remove # the given digit def smallestNumber(n, d): # Copy the number to another variable temp = n ans = 0 count = 0 # Iterate over digits of the given # number from right to left while (temp > 0): # Extract the last digit of the # number and check if it is # equal to the given digit (d) remainder = temp % 10 temp = temp // 10 count += 1 if (remainder == d): # If the digit which # need to be replaced # is equal to 0 then # increment the current # digit and make the all digits # to its right 1 if (d == 0): num = '1'*count temp = temp * pow(10, count) + int(num) # Else, increment the current digit # by 1 and make the all digits # to its right 0 else: temp = (temp * pow(10, count) + (remainder + 1) * pow(10, count - 1)) # After the removal of given # digit the number will be temp # So, the required smallest # number is (temp - n) ans = temp - n # Set count as 0 count = 0 # Return the result return ans # Driver code if __name__ == "__main__": N = 100 D = 0 # print the smallest number required # to be added to remove # the digit 'D' in number 'N' print(smallestNumber(N, D)) # This code is contributed by ukasp.
C#
// C# implementation for the above approach
using System;
class GFG {
// Function to calculate smallest positive
// number to be added to remove
// the given digit
public static int smallestNumber(int n, int d)
{
// Copy the number to another variable
int temp = n;
int ans = 0, count = 0;
// Iterate over digits of the given
// number from right to left
while (temp > 0)
{
// Extract the last digit of the
// number and check if it is
// equal to the given digit (d)
int remainder = temp % 10;
temp = temp / 10;
count++;
if (remainder == d)
{
// If the digit which need to be
// replaced is equal to 0 then
// increment the current digit
// and make the all digits to
// its right 1
if (d == 0)
{
string num = "";
for(int i = 0; i < count; i++)
{
num = num + "1";
}
temp = (int)(temp * Math.Pow(10, count) +
Int32.Parse(num));
}
// Else, increment the current digit
// by 1 and make the all digits
// to its right 0
else
{
temp = (int) (temp * Math.Pow(10, count) +
(remainder + 1) * Math.Pow(10, count - 1));
}
// After the removal of given
// digit the number will be temp
// So, the required smallest
// number is (temp - n)
ans = temp - n;
// Set count as 0
count = 0;
}
}
// Return the result
return ans;
}
// Driver code
public static void Main(String[] args)
{
int N = 100;
int D = 0;
// Print the smallest number required
// to be added to remove the digit 'D'
// in number 'N'
Console.Write(smallestNumber(N, D));
}
}
// This code is contributed by sanjoy_62.
Javascript
<script>
// JavaScript Program to implement
// the above approach
// Function to calculate smallest positive
// number to be added to remove
// the given digit
function smallestNumber(n, d)
{
// Copy the number to another variable
let temp = n;
let ans = 0, count = 0;
// Iterate over digits of the given
// number from right to left
while (temp > 0) {
// Extract the last digit of the
// number and check if it is
// equal to the given digit (d)
let remainder = temp % 10;
temp = Math.floor(temp / 10);
count++;
if (remainder == d)
{
// If the digit which
// need to be replaced
// is equal to 0 then
// increment the current
// digit and make the all digits
// to its right 1
if (d == 0) {
let num = ''
for (let i = 0; i < count; i++) {
num = num + '1';
}
temp = temp * Math.pow(10, count) + parseInt(num);
}
// Else, increment the current digit
// by 1 and make the all digits
// to its right 0
else {
temp = temp * Math.pow(10, count)
+ (remainder + 1)
* Math.pow(10, count - 1);
}
// After the removal of given
// digit the number will be temp
// So, the required smallest
// number is (temp - n)
ans = temp - n;
// Set count as 0
count = 0;
}
}
// Return the result
return ans;
}
// Driver code
let N = 100;
let D = 0;
// print the smallest number required
// to be added to remove
// the digit 'D' in number 'N'
document.write(smallestNumber(N, D) + "<br>");
// This code is contributed by Potta Lokesh
</script>
Producción
11
Complejidad de tiempo: O((log(N))^2)
Espacio auxiliar: O(log(N))