算法题（找到第n个数字，其数字仅包含为0、1、2、3、4或5） _第n个数字

本文概述

CPP
C ++
Java
C#
C ++

给定数字n, 我们必须找到第n个数字, 使得它的数字仅包含0、1、2、3、4或5。
例子：

Input: n = 6 Output: 5Input:n = 10 Output: 13

推荐：请在”
实践
首先, 在继续解决方案之前。
我们首先将0、1、2、3、4、5存储在一个数组中。我们可以看到下一个数字将是10、11、12、13、14、15, 之后的数字将是20、21、23、24、25, 依此类推。我们可以看到不断重复的模式。我们保存计算的结果, 并将其用于进一步的计算。
接下来的6个数字是-
1 * 10 + 0 = 10
1 * 10 + 1 = 11
1 * 10 + 2 = 12
1 * 10 + 3 = 13
1 * 10 + 4 = 14
1 * 10 + 5 = 15
之后, 接下来的6个数字将是-
2 * 10 + 0 = 20
2 * 10 + 1 = 21
2 * 10 + 2 = 22
2 * 10 + 3 = 23
2 * 10 + 4 = 24
2 * 10 + 5 = 25
我们使用这种模式来找到第n个数字。下面是完整的算法。

1) push 0 to 5 in ans vector 2) for i=0 to n 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]

CPP

// 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; 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; }

高效方法：
算法：
1.首先将数字n转换为6。
2.将转换后的值同时存储在数组中。
3.以相反的顺序打印该阵列。
下面是上述算法的实现：
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.

// 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

输出如下：

13

另一种有效的方法：
算法：
1.将数字N减1。
2.将数字N转换为以6为底的数字。
下面是上述算法的实现：
C ++

// CPP 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 Explaination:- 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

输出如下