Dado un entero positivo N , la tarea es encontrar el N número natural después de eliminar todos los números naturales que contienen el dígito 9 .
Ejemplos:
Entrada: N = 8
Salida: 8
Explicación:
Dado que 9 es el primer número natural que contiene el dígito 9 y es el noveno número natural, por lo tanto, no es necesario eliminar para encontrar el octavo número natural, que es 8.Entrada: N = 9
Salida: 10
Explicación:
Quitando el número 9, los primeros 9 números naturales son {1, 2, 3, 4, 5, 6, 7, 8, 10}.
Por lo tanto, el noveno número natural es 10.
Enfoque ingenuo: el enfoque más simple para resolver el problema anterior es iterar hasta N y seguir excluyendo todos los números menores que N que contengan el dígito 9. Finalmente, imprimir el N número natural obtenido.
Siga los pasos a continuación para resolver los problemas:
- Inicializar una cuenta variable = 0
- y use for loop y pase el elemento del bucle a la función isDigitNine (i) para verificar si ese número contiene 9 o no e incrementarlo si no está presente
- Y una vez que Count golpea N, asigne el último i para contar y romper el ciclo.
- Devolver la respuesta como recuento
C++
#include <bits/stdc++.h>
using namespace std;
// isDigitNine function return true if number contain digit
// 9 else will return false
bool isDigitNine(int i)
{
while (i > 0) {
int rem = i % 10;
if (rem == 9) {
return true;
}
i = i / 10;
}
return false;
}
long long findNth(long long N)
{
long long count = 0;
for (int i = 1; i > 0; i++) {
// call function digitnine() with i
if (isDigitNine(i) == false) {
count++;
if (count == N) {
count = i; // once count is equal to N then
break; // assign last i to count and break
// the loop
}
}
}
return count;
}
int main()
{
long long N = 18976;
long long ans = findNth(N);
cout << ans << endl;
return 0;
}
Java
public class nthnaturalNum {
public static void main(String[] args) {
long N = 18976;
long ans = findNth(N);
System.out.println(ans);
}
static long findNth(long N)
{
//code here
long count = 0;
for(int i = 1; i > 0; i++ ){
// call function digitnine() with i
if(isDigitNine(i) == false)
{
count ++;
if(count == N ) {
count = i; // once count is equal to N then
break; //assign last i to count and break the loop
}
}
}
return count ;
}
// isDigitNine function return true if number contain digit 9
// else will return false
static boolean isDigitNine(int i){
while(i > 0){
int rem = i % 10;
if(rem == 9){
return true;
}
i = i / 10;
}
return false;
}
}
/* This code is contributed by devendra solunke */
Python3
# defining findNth function to find the Nth value def findNth(N): count = 0 i = 1 while(i != 0): # calling isDigitNine to check the digit is nine or not if(isDigitNine(i) == False): count = count + 1 if(count == N): count = i # break when we reached to the count equals to N break i = i + 1 return count # defining isDigitNine function to check digit is 9 or nor def isDigitNine(i): while(i != 0): rem = i % 10 if(rem == 9): return True i = i//10 return False N = 18976 solution = findNth(N) print(solution) # This code is contributed by Gayatri Deshmukh
Producción
28024
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Enfoque eficiente: el enfoque anterior se puede optimizar en función de las siguientes observaciones:
- Se sabe que los dígitos de los números de base 2 varían de 0 a 1 . Del mismo modo, los dígitos de los números de base 10 varían de 0 a 9 .
- Por lo tanto, los dígitos de los números de base 9 variarán de 0 a 8 .
- Se puede observar que el número N en base 9 es igual al número N después de omitir los números que contienen el dígito 9 .
- Entonces la tarea se reduce a encontrar el equivalente en base 9 del número N.
Siga los pasos a continuación para resolver el problema:
- Inicialice dos variables, digamos res = 0 y p = 1 , para almacenar el número en base 9 y para almacenar la posición de un dígito.
- Iterar mientras N es mayor que 0 y realizar las siguientes operaciones:
- Actualice res como res = res + p*(N%9) .
- Divide N por 9 y multiplica p por 10.
- Después de completar los pasos anteriores, imprima el valor de res .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find Nth number in base 9
long long findNthNumber(long long N)
{
// Stores the Nth number
long long result = 0;
long long p = 1;
// Iterate while N is
// greater than 0
while (N > 0) {
// Update result
result += (p * (N % 9));
// Divide N by 9
N = N / 9;
// Multiply p by 10
p = p * 10;
}
// Return result
return result;
}
// Driver Code
int main()
{
int N = 9;
cout << findNthNumber(N);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG
{
// Function to find Nth number in base 9
static long findNthNumber(long N)
{
// Stores the Nth number
long result = 0;
long p = 1;
// Iterate while N is
// greater than 0
while (N > 0) {
// Update result
result += (p * (N % 9));
// Divide N by 9
N = N / 9;
// Multiply p by 10
p = p * 10;
}
// Return result
return result;
}
// Driver Code
public static void main(String[] args)
{
int N = 9;
System.out.print(findNthNumber(N));
}
}
// This code is contributed by splevel62.
Python3
# Python 3 implementation of above approach # Function to find Nth number in base 9 def findNthNumber(N): # Stores the Nth number result = 0 p = 1 # Iterate while N is # greater than 0 while (N > 0): # Update result result += (p * (N % 9)) # Divide N by 9 N = N // 9 # Multiply p by 10 p = p * 10 # Return result return result # Driver Code if __name__ == '__main__': N = 9 print(findNthNumber(N)) # This code is contributed by bgangwar59.
C#
// C# implementation of above approach
using System;
class GFG
{
// Function to find Nth number in base 9
static long findNthNumber(long N)
{
// Stores the Nth number
long result = 0;
long p = 1;
// Iterate while N is
// greater than 0
while (N > 0) {
// Update result
result += (p * (N % 9));
// Divide N by 9
N = N / 9;
// Multiply p by 10
p = p * 10;
}
// Return result
return result;
}
// Driver code
static void Main ()
{
int N = 9;
Console.Write(findNthNumber(N));
}
}
// This code is contributed by divyesh072019.
Javascript
<script>
// Javascript implementation of above approach
// Function to find Nth number in base 9
function findNthNumber(N)
{
// Stores the Nth number
let result = 0;
let p = 1;
// Iterate while N is
// greater than 0
while (N > 0) {
// Update result
result += (p * (N % 9));
// Divide N by 9
N = parseInt(N / 9, 10);
// Multiply p by 10
p = p * 10;
}
// Return result
return result;
}
let N = 9;
document.write(findNthNumber(N));
</script>
Producción
10
Complejidad de Tiempo: O(log 9 N)
Espacio Auxiliar: O(1)