How to generate the nth number that consists only of even digits?

Question

I'm novice to Programming. I can find numbers consisting of even digits but my algorithm complexity is O(n). For large n my algorithm is too slow. So I need a more efficient algorithm. Can anyone help me?

For example, the first numbers with even digits are 0 , 2 , 4 , 6 , 8 , 20 , 22 , 24 , 26 , 28 , 40 etc. 2686 is another example of a number with even digits.

Here is my code: http://ideone.com/nsBzej

#include<bits/stdc++.h>
using namespace std;
long long int a[10],b[20];
long long int powr(int i)
{
    long long int ans=5;
    for(int j=2;j<=i;j++)
    {
        ans=ans*5;
    }
    return ans;
}
int main()
{
    //freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);

    long long int n,s,sum,p;
    int t;
    cin>>t;
    for(int j=1;j<=t;j++)
    {
        s=20,sum=0;
        a[1]=0, a[2]=2, a[3]=4, a[4]=6, a[5]=8;

        for(int i=1;i<=17;i++)
        {
            b[i]=s;
            s=s*10;
        }

        cin>>n;
        for(int i=17;i>=1;i--)
        {
            p=powr(i);
            while(p<n)
            {
                sum=sum+b[i];
                n=n-p;
            }
        }

        printf("Case %d: %lld\n",j,sum);
    }
}

It is complexity O(n). But I get wrong verdict.

Answer 1

We need to find numbers made of 5 digits, 0, 2, 4, 6 and 8. When we convert a number into base 5 number, it will only be made of numbers {0, 1, 2, 3, 4}. It can be clearly seen that each digit in the required digit set {0, 2, 4, 6, 8} is double the digit in the corresponding index of the base-5 digit set. So to find the n-th number made of only even digits follow the below mentioned steps

Step 1: Convert n to n-1 this is done so as to exclude zero. Step 2: Convert n to 5 base decimal number. Step 3: Multiply the above found number by 2. This is the required number

code:

#include<bits/stdc++.h>
using namespace std;

int help(int n)
{
    if (n == 1)
        return 0;
    vector< int> v;
    n = n - 1;
    while (n > 0)
    {
        v.push_back(n % 5);
        n = n / 5;
    }
    int result = 0;
    for (int i = v.size() - 1; i >= 0; i--)
    {
        result = result * 10;
        result = result + v[i];
    }
    return 2*result;
}

// Driver Code
int main()
{
    cout << help(2) 
        << endl;
    return 0;
}

Answer 2

#include <stdio.h>

int main(void){
    unsigned long long nth = 1000000000000ULL-1;//-1: 1 origin
    unsigned long long k[30] = {0, 5};//28:Log10(ULL_MAX)/Log10(5) + 1
    unsigned long long sum = k[1];
    unsigned long long temp = 4;//4 : 2,4,6,8
    int i;
    //make table
    for(i = 1; i < 30 ; ++i){
        if(k[i] == 0){
            temp *= 5;//5 : 0,2,4,6,8 , 2digits: 4*5, 3digits: 4*5*5
            sum += temp;
            k[i] = sum;
        }
        if(k[i] > nth)
            break;
    }
    while(--i){//The same basically barakmanos
        int n = nth / k[i];
        printf("%d", n * 2);
        nth -= n * k[i];
    }
    printf("%d\n", nth * 2);
    return 0;
}