Dado un número n, tenemos que encontrar el n-ésimo número tal que sus dígitos solo consisten en 0, 1, 2, 3, 4 o 5.
Ejemplos:
Input: n = 6 Output: 5 Input: n = 10 Output: 13
Primero almacenamos 0, 1, 2, 3, 4, 5 en una array. Podemos ver que los próximos números serán 10, 11, 12, 13, 14, 15 y luego los números serán 20, 21, 23, 24, 25 y así sucesivamente. Podemos ver el patrón que se repite una y otra vez. Guardamos el resultado calculado y lo usamos para otros cálculos.
los siguientes 6 números son:
1*10+0 = 10
1*10+1 = 11
1*10+2 = 12
1*10+3 = 13
1*10+4 = 14
1*10+5 = 15
y después de eso los siguientes 6 números serán-
2*10+0 = 20
2*10+1 = 21
2*10+2 = 22
2*10+3 = 23
2*10+4 = 24
2*10+5 = 25
Usamos este patrón para encontrar el n-ésimo número. A continuación se muestra el algoritmo completo.
1) push 0 to 5 in ans vector
2) for i=0 to n/6
for j=0 to 6
// this will be the case when first
// digit will be zero
if (ans[i]*10! = 0)
ans.push_back(ans[i]*10 + ans[j])
3) print ans[n-1]
C++
// C++ program to find n-th number with digits
// in {0, 1, 2, 3, 4, 5}
#include <bits/stdc++.h>
using namespace std;
// Returns the N-th number with given digits
int findNth(int n)
{
// vector to store results
vector<int> ans;
// push first 6 numbers in the answer
for (int i = 0; i < 6; i++)
ans.push_back(i);
// calculate further results
for (int i = 0; i <= n / 6; i++)
for (int j = 0; j < 6; j++)
if ((ans[i] * 10) != 0)
ans.push_back(ans[i]
* 10 + ans[j]);
return ans[n - 1];
}
// Driver code
int main()
{
int n = 10;
cout << findNth(n);
return 0;
}
Java
// Java program to find n-th number with digits
// in {0, 1, 2, 3, 4, 5}
import java.io.*;
import java.util.*;
class GFG
{
// Returns the N-th number with given digits
public static int findNth(int n)
{
// vector to store results
ArrayList<Integer> ans = new ArrayList<Integer>();
// push first 6 numbers in the answer
for (int i = 0; i < 6; i++)
ans.add(i);
// calculate further results
for (int i = 0; i <= n / 6; i++)
for (int j = 0; j < 6; j++)
if ((ans.get(i) * 10) != 0)
ans.add(ans.get(i) * 10 + ans.get(j));
return ans.get(n - 1);
}
// Driver code
public static void main(String[] args)
{
int n = 10;
int ans = findNth(n);
System.out.println(ans);
}
}
// This code is contributed by RohitOberoi.
Python3
# Python3 program to find n-th number with digits
# in {0, 1, 2, 3, 4, 5}
# Returns the N-th number with given digits
def findNth(n):
# vector to store results
ans = []
# push first 6 numbers in the answer
for i in range(6):
ans.append(i)
# calculate further results
for i in range(n // 6 + 1):
for j in range(6):
if ((ans[i] * 10) != 0):
ans.append(ans[i]
* 10 + ans[j])
return ans[n - 1]
# Driver code
if __name__ == "__main__":
n = 10
print(findNth(n))
# This code is contributed by ukasp.
C#
// C# program to find n-th number with digits
// in {0, 1, 2, 3, 4, 5}
using System;
using System.Collections.Generic;
class GFG{
// Returns the N-th number with given digits
public static int findNth(int n)
{
// Vector to store results
List<int> ans = new List<int>();
// Push first 6 numbers in the answer
for(int i = 0; i < 6; i++)
ans.Add(i);
// Calculate further results
for(int i = 0; i <= n / 6; i++)
for(int j = 0; j < 6; j++)
if ((ans[i] * 10) != 0)
ans.Add(ans[i] * 10 + ans[j]);
return ans[n - 1];
}
// Driver code
public static void Main(String[] args)
{
int n = 10;
int ans = findNth(n);
Console.WriteLine(ans);
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// Javascript program to find n-th
// number with digits
// in {0, 1, 2, 3, 4, 5}
// Returns the N-th number with given digits
function findNth(n)
{
// vector to store results
var ans = [];
// push first 6 numbers in the answer
for (i = 0; i < 6; i++)
ans.push(i);
// calculate further results
for (i = 0; i <= n / 6; i++)
for (j = 0; j < 6; j++)
if ((ans[i] * 10) != 0)
ans.push(ans[i] * 10 + ans[j]);
return ans[n - 1];
}
// Driver code
var n = 10;
var ans = findNth(n);
document.write(ans);
// This code contributed by Rajput-Ji
</script>
Producción
13
Método eficiente:
Algoritmo:
- Primero convierte el número n a la base 6.
- Almacene el valor convertido simultáneamente en una array.
- Imprime esa array en orden inverso.
A continuación se muestra la implementación del algoritmo anterior:
C++
// CPP code to find nth number
// with digits 0, 1, 2, 3, 4, 5
#include <bits/stdc++.h>
using namespace std;
#define max 100000
// function to convert num to base 6
int baseconversion(int arr[], int num, int base)
{
int i = 0, rem, j;
if (num == 0) {
return 0;
}
while (num > 0) {
rem = num % base;
arr[i++] = rem;
num /= base;
}
return i;
}
// Driver code
int main()
{
// initialize an array to 0
int arr[max] = { 0 };
int n = 10;
// function calling to convert
// number n to base 6
int size = baseconversion(arr, n - 1, 6);
// if size is zero then return zero
if (size == 0)
cout << size;
for (int i = size - 1; i >= 0; i--) {
cout << arr[i];
}
return 0;
}
// Code is contributed by Anivesh Tiwari.
Java
// Java code to find nth number
// with digits 0, 1, 2, 3, 4, 5
class GFG {
static final int max = 100000;
// function to convert num to base 6
static int baseconversion(int arr[],
int num, int base)
{
int i = 0, rem, j;
if (num == 0) {
return 0;
}
while (num > 0) {
rem = num % base;
arr[i++] = rem;
num /= base;
}
return i;
}
// Driver code
public static void main (String[] args)
{
// initialize an array to 0
int arr[] = new int[max];
int n = 10;
// function calling to convert
// number n to base 6
int size = baseconversion(arr, n - 1, 6);
// if size is zero then return zero
if (size == 0)
System.out.print(size);
for (int i = size - 1; i >= 0; i--) {
System.out.print(arr[i]);
}
}
}
// This code is contributed by Anant Agarwal.
Python3
# Python code to find nth number # with digits 0, 1, 2, 3, 4, 5 max = 100000; # function to convert num to base 6 def baseconversion(arr, num, base): i = 0; if (num == 0): return 0; while (num > 0): rem = num % base; i = i + 1; arr[i] = rem; num = num//base; return i; # Driver code if __name__ == '__main__': # initialize an array to 0 arr = [0 for i in range(max)]; n = 10; # function calling to convert # number n to base 6 size = baseconversion(arr, n - 1, 6); # if size is zero then return zero if (size == 0): print(size); for i in range(size, 0, -1): print(arr[i], end = ""); # This code is contributed by gauravrajput1
C#
// C# code to find nth number
// with digits 0, 1, 2, 3, 4, 5
using System;
class GFG {
static int max = 100000;
// function to convert num to base 6
static int baseconversion(int []arr,
int num, int bas)
{
int i = 0, rem;
if (num == 0) {
return 0;
}
while (num > 0) {
rem = num % bas;
arr[i++] = rem;
num /= bas;
}
return i;
}
// Driver code
public static void Main ()
{
// initialize an array to 0
int []arr = new int[max];
int n = 10;
// function calling to convert
// number n to base 6
int size = baseconversion(arr, n - 1, 6);
// if size is zero then return zero
if (size == 0)
Console.Write(size);
for (int i = size - 1; i >= 0; i--) {
Console.Write(arr[i]);
}
}
}
// This code is contributed by nitin mittal
Javascript
<script>
// javascript code to find nth number
// with digits 0, 1, 2, 3, 4, 5
var max = 100000;
// function to convert num to base 6
function baseconversion(arr , num , base) {
var i = 0, rem, j;
if (num == 0) {
return 0;
}
while (num > 0) {
rem = num % base;
arr[i++] = rem;
num = parseInt(num/base);
}
return i;
}
// Driver code
// initialize an array to 0
var arr = Array(max).fill(0);
var n = 10;
// function calling to convert
// number n to base 6
var size = baseconversion(arr, n - 1, 6);
// if size is zero then return zero
if (size == 0)
document.write(size);
for (i = size - 1; i >= 0; i--) {
document.write(arr[i]);
}
// This code contributed by Rajput-Ji
</script>
Producción:
13
Otro método eficiente:
Algoritmo:
- Disminuya el número N en 1.
- 2. Convierte el número N a base 6.
A continuación se muestra la implementación del algoritmo anterior:
C++
// C++ code to find nth number
// with digits 0, 1, 2, 3, 4, 5
#include <iostream>
using namespace std;
int ans(int n){
// If the Number is less than 6 return the number as it is.
if(n < 6){
return n;
}
//Call the function again and again the get the desired result.
//And convert the number to base 6.
return n%6 + 10*(ans(n/6));
}
int getSpecialNumber(int N)
{
//Decrease the Number by 1 and Call ans function
// to convert N to base 6
return ans(--N);
}
/*Example:-
Input: N = 17
Output: 24
Explanation:-
decrease 17 by 1
N = 16
call ans() on 16
ans():
16%6 + 10*(ans(16/6))
since 16/6 = 2 it is less than 6 the ans returns value as it is.
4 + 10*(2)
= 24
hence answer is 24.*/
int main()
{
int N = 17;
int answer = getSpecialNumber(N);
cout<<answer<<endl;
return 0;
}
// This Code is contributed by Regis Caelum
Java
// Java code to find nth number
// with digits 0, 1, 2, 3, 4, 5
import java.util.*;
class GFG{
static int ans(int n)
{
// If the Number is less than 6 return
// the number as it is.
if (n < 6)
{
return n;
}
// Call the function again and again
// the get the desired result.
// And convert the number to base 6.
return n % 6 + 10 * (ans(n / 6));
}
static int getSpecialNumber(int N)
{
// Decrease the Number by 1 and Call
// ans function to convert N to base 6
return ans(--N);
}
/*
* Example:- Input: N = 17 Output: 24
*
* Explanation:- decrease 17 by 1 N = 16 call ans() on 16
*
* ans(): 16%6 + 10*(ans(16/6)) since 16/6 = 2 it is less
* than 6 the ans returns value as it is. 4 + 10*(2) = 24
*
* hence answer is 24.
*/
// Driver code
public static void main(String[] args)
{
int N = 17;
int answer = getSpecialNumber(N);
System.out.println(answer);
}
}
// This code is contributed by Rajput-Ji
Python3
# Python3 code to find nth number # with digits 0, 1, 2, 3, 4, 5 def ans(n): # If the Number is less than 6 return # the number as it is. if (n < 6): return n # Call the function again and again # the get the desired result. # And convert the number to base 6. return n % 6 + 10 * (ans(n // 6)) - 1 def getSpecialNumber(N): # Decrease the Number by 1 and Call # ans function to convert N to base 6 return ans(N) ''' * Example:- Input: N = 17 Output: 24 * * Explanation:- decrease 17 by 1 N = 16 call ans() on 16 * * ans(): 16%6 + 10*(ans(16/6)) since 16/6 = 2 it is less than 6 the ans returns * value as it is. 4 + 10*(2) = 24 * * hence answer is 24. ''' # Driver code if __name__ == '__main__': N = 17 answer = getSpecialNumber(N) print(answer) # This code contributed by aashish1995
C#
// C# code to find nth number
// with digits 0, 1, 2, 3, 4, 5
using System;
public class GFG{
static int ans(int n)
{
// If the Number is less than 6 return
// the number as it is.
if (n < 6)
{
return n;
}
// Call the function again and again
// the get the desired result.
// And convert the number to base 6.
return n % 6 + 10 * (ans(n / 6));
}
static int getSpecialNumber(int N)
{
// Decrease the Number by 1 and Call
// ans function to convert N to base 6
return ans(--N);
}
/*
* Example:- Input: N = 17 Output: 24
*
* Explanation:- decrease 17 by 1 N = 16 call ans() on 16
*
* ans(): 16%6 + 10*(ans(16/6)) since 16/6 = 2 it is less
* than 6 the ans returns value as it is. 4 + 10*(2) = 24
*
* hence answer is 24.
*/
// Driver code
public static void Main(String[] args)
{
int N = 17;
int answer = getSpecialNumber(N);
Console.WriteLine(answer);
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// javascript code to find nth number
// with digits 0, 1, 2, 3, 4, 5
function ans(n) {
// If the Number is less than 6 return
// the number as it is.
if (n < 6) {
return n;
}
// Call the function again and again
// the get the desired result.
// And convert the number to base 6.
return n % 6 + 10 * (ans(parseInt(n / 6)));
}
function getSpecialNumber(N) {
// Decrease the Number by 1 and Call
// ans function to convert N to base 6
return ans(--N);
}
/*
* Example:- Input: N = 17 Output: 24
*
* Explanation:- decrease 17 by 1 N = 16 call ans() on 16
*
* ans(): 16%6 + 10*(ans(16/6)) since 16/6 = 2 it is less than 6 the ans returns
* value as it is. 4 + 10*(2) = 24
*
* hence answer is 24.
*/
// Driver code
var N = 17;
var answer = getSpecialNumber(N);
document.write(answer);
// This code contributed by Rajput-Ji
</script>
Producción
24
Complejidad temporal: O(logN)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA