算法题：找到第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)