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

本文概述

• CPP
• C ++
• Java
• C#
• C ++

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

例子 ：

Input: n = 6 Output: 5 Input: 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#

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

输出如下

24

时间复杂度：O(logN)

辅助空间：O(1)