Dados los números enteros N, K y una secuencia infinita de números naturales donde se eliminan todos los números que contienen el dígito K (1<=K<=9). La tarea es devolver el número N de esta secuencia.
Ejemplo:
Entrada: N = 12, K = 2
Salida: 14
Explicación: La secuencia generada para la entrada anterior sería así: 1, 3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 14, 15, 16, 17, hasta el infinitoEntrada: N = 10, K = 1
Salida: 22
Enfoque ingenuo: el enfoque básico para resolver el problema anterior sería iterar hasta N y seguir excluyendo todos los números menores que N que contengan el dígito dado K. Finalmente, imprimir el N-ésimo número natural obtenido.
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Enfoque eficiente: el enfoque eficiente para resolver esto se inspira en el número natural N después de eliminar todos los números que consisten en el dígito 9 .
El problema dado se puede resolver convirtiendo el valor de K a la forma base 9 si es más de 8. Se pueden seguir los pasos a continuación:
- Calcular el enésimo número natural en formato base 9
- Incremente 1 a cada dígito del número de base 9 que sea mayor o igual a K
- El siguiente número es la respuesta deseada.
A continuación se muestra el código para el enfoque anterior:
C++
// C++ implementation for the above approach
#include <iostream>
using namespace std;
long long convertToBase9(long long n)
{
long long ans = 0;
// Denotes the digit place
long long a = 1;
// Method to convert any number
// to binary equivalent
while (n > 0) {
ans += (a * (n % 9));
a *= 10;
n /= 9;
}
return ans;
}
long long getNthnumber(long long base9,
long long K)
{
long long ans = 0;
// denotes the current digits place
long long a = 1;
while (base9 > 0) {
int cur = base9 % 10;
// If current digit is >= K
// increment its value by 1
if (cur >= K) {
ans += a * (cur + 1);
}
// Else add the digit as it is
else {
ans += a * cur;
}
base9 /= 10;
// Move to the next digit
a *= 10;
}
return ans;
}
// Driver code
int main()
{
long long N = 10, K = 1;
long long base9 = convertToBase9(N);
cout << getNthnumber(base9, K);
return 0;
}
Java
// Java implementation for the above approach
import java.io.*;
class GFG {
static long convertToBase9(long n)
{
long ans = 0;
// Denotes the digit place
long a = 1;
// Method to convert any number
// to binary equivalent
while (n > 0) {
ans += (a * (n % 9));
a *= 10;
n /= 9;
}
return ans;
}
static long getNthnumber(long base9,
long K)
{
long ans = 0;
// denotes the current digits place
long a = 1;
while (base9 > 0) {
int cur = (int)(base9 % 10);
// If current digit is >= K
// increment its value by 1
if (cur >= K) {
ans += a * (cur + 1);
}
// Else add the digit as it is
else {
ans += a * cur;
}
base9 /= 10;
// Move to the next digit
a *= 10;
}
return ans;
}
// Driver code
public static void main (String[] args) {
long N = 10, K = 1;
long base9 = convertToBase9(N);
System.out.println(getNthnumber(base9, K));
}
}
// This code is contributed by Dharanendra L V.
Python3
# Python 3 implementation for the above approach def convertToBase9(n): ans = 0 # Denotes the digit place a = 1 # Method to convert any number # to binary equivalent while(n > 0): ans += (a * (n % 9)) a *= 10 n //= 9 return ans def getNthnumber(base9, K): ans = 0 # denotes the current digits place a = 1 while (base9 > 0): cur = base9 % 10 # If current digit is >= K # increment its value by 1 if (cur >= K): ans += a * (cur + 1) # Else add the digit as it is else: ans += a * cur base9 //= 10 # Move to the next digit a *= 10 return ans # Driver code if __name__ == '__main__': N = 10 K = 1 base9 = convertToBase9(N) print(getNthnumber(base9, K)) # This code is contributed by SURENDRA_GANGWAR.
C#
// C# implementation for the above approach
using System;
class GFG {
static long convertToBase9(long n)
{
long ans = 0;
// Denotes the digit place
long a = 1;
// Method to convert any number
// to binary equivalent
while (n > 0) {
ans += (a * (n % 9));
a *= 10;
n /= 9;
}
return ans;
}
static long getNthnumber(long base9,
long K)
{
long ans = 0;
// denotes the current digits place
long a = 1;
while (base9 > 0) {
int cur = (int)(base9 % 10);
// If current digit is >= K
// increment its value by 1
if (cur >= K) {
ans += a * (cur + 1);
}
// Else add the digit as it is
else {
ans += a * cur;
}
base9 /= 10;
// Move to the next digit
a *= 10;
}
return ans;
}
// Driver code
public static void Main (String[] args) {
long N = 10, K = 1;
long base9 = convertToBase9(N);
Console.Write(getNthnumber(base9, K));
}
}
// This code is contributed by shivanisinghss2110
Javascript
<script>
// Javascript implementation for the above approach
function convertToBase9(n)
{
let ans = 0;
// Denotes the digit place
let a = 1;
// Method to convert any number
// to binary equivalent
while (n > 0) {
ans += a * (n % 9);
a *= 10;
n = Math.floor(n / 9);
}
return ans;
}
function getNthnumber(base9, K) {
let ans = 0;
// denotes the current digits place
let a = 1;
while (base9 > 0) {
let cur = base9 % 10;
// If current digit is >= K
// increment its value by 1
if (cur >= K) {
ans += a * (cur + 1);
}
// Else add the digit as it is
else {
ans += a * cur;
}
base9 = Math.floor(base9 / 10);
// Move to the next digit
a *= 10;
}
return ans;
}
// Driver code
let N = 10,
K = 1;
let base9 = convertToBase9(N);
document.write(getNthnumber(base9, K));
// This code is contributed by gfgking.
</script>
22
Complejidad de Tiempo: O(log 9 N)
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por mahim_mittal y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA