CODEWITHSUNDEEP
algorithmc++11
Magdy.A
Magdy.A

Reputation: 53

How to generate the nth numbers containing only 2 types of digits?

We define a special number as a number containing only 4s and 7s.

Let's see examples: 447 , 477 , 444 and 777 are special numbers while 407 isn't.

I need help to understand what is the law/rule to generate the Nth special number.

I tried the code below but it didn't work

int x[2000];
int k=0;

void dfs( int a ) {
  if(k==1021)
    return;
  x[k++]=a;
  dfs(a*10+4);
  dfs(a*10+7);
}

dfs(4);
dfs(7);

Any solution or idea about how to do it ?

Upvotes: 3

Views: 2056

Answers (4)

Lin Li
Lin Li

Reputation: 11

i try to follow your idea to answer this question. Maybe somebody will get help from this.

int x[2000];
int k = 0;
const int num_len = 8;

void dfs(int a, int level)
{
    if (level > num_len)
        return;
    x[k++] = a;
    dfs(a * 10 + 4, level + 1);
    dfs(a * 10 + 7, level + 1);
}

int main()
{
    memset(x, 0, sizeof(x));
    dfs(0, 0);
    sort(x, x+k);

    int nth;
    cin >> nth;
    cout << x[nth] << endl;
    return 0;
}

Upvotes: 1

Nicholas Pipitone
Nicholas Pipitone

Reputation: 4142

For this we can use binary. Call the 4s as 0s and the 7s as 1s, since 7>4. Say we are looking for the nth special number. Define k as the number of special numbers with fewer digits that the nth special number. Now, we see how binary can be used. Say we know that the 10th special number has 3 digits, and that k=6. We are looking for the 10-6=4th number into the list of 3-digit special numbers.

4 - 0      77 - 11

7 - 1      444 - 000

44 - 00      447 - 001

47 - 01      474 - 010

74 - 10      477 - 011 <-Here

Mapping them to binary like shown, the problem becomes easier. The number of m-digit special numbers is going to be 2^m, and remember that the sum of the first m powers of two is 2^(m+1)-1. If we have a 3-digit number, then we find k by summing the 1 digit and 2 digit numbers, leaving us with 2^0+2^1+2^2=2^3-1. Excluding 0-digit numbers we have 2^3-2 as k, and this generalizes to 2^digits-2. In order to find the number of digits, we need to find out how many powers of two are below n. This is simply log2(n), but we have to line it up and get an integer so we take floor(log2(n+1)). From here, we simply use the binary representation of n-k-1 and then use bitwise functions to extract each digit and add the digit to our answer.

int nthspecialnum( int n )
{
    int digits = (int)(log2(n+1));
    int k = pow( 2, digits ) - 2;
    int binary = n - k - 1;
    int answer = 0;
    for( int i = 0; i < digits; i++ ) {
        bool is7 = ((binary >> i) % 2) == 1;
        answer += (is7 ? 7 : 4)*pow( 10, i );
    }
    return answer;
}

These numbers get large decently quickly, so if you're looking for large n and don't want negative numbers to come out, you can simply save the digits in an array rather than an integer and print them out sequentially.

Upvotes: 5

fjardon
fjardon

Reputation: 7996

Why your code is broken

Your code doesn't work because your termination condition depends on a global variable k which is not reset before the second call dfs(7). So this call terminates without producing any new special number. So in the end you miss all special numbers starting with a 7.

You could fix that by just calling: dfs(0) and discarding the first entry of you x array. But the whole program is badly written. Relying on global variable inside a function is a call for a disaster.

Algorithm to generate all special numbers

If the number is between 0 and 100 then it has got either 0, 1 or 2 digits.

So basically all special numbers are: 4, 7, 44, 47, 74, 77.

If you want to extend to a number d of digits, then you can use a binary number of d bits. Choose that a bit whose value is 0 will be a decimal digit 4, and a bit whose value is 1 will translate into a decimal digit 7. Then by enumerating all the values between 0 and 2^d-1 you can generate all the special numbers.

In the previous case we enumerated all special numbers with:

  • 1 bit, which translates into 2 special numbers: 4 ad 7
  • 2 bits, which translates into 4 special numbers: 44, 47, 74, 77

How to get the Nth special number First of all we consider a 1 based indexing.

You just need to remark that the count of special numbers whose binary representation has got less that d bits is: 2^1+2^2+...+ 2^d = 2(2^d-1) = 2^(d+1)-2

You can do a simple loop incrementing d until 2^(d+1)-2 is not strictly inferior to n. This tells you should use a d bits binary representation for n. You substract 2^d-2 to n and you substract 1 because we use a 1 based indexing. The final number can now pass through the steps described above to generate a special number.

Example: 5th special numbers

2^2-2 = 2 <  5   => d+1 > 2
2^3-2 = 6 >= 5   => d+1 = 3  => d = 2

n-2^d+2-1 = 5-4+2-1 = 2 = 10b (using 2 bits as d = 2)

=> 5th special number is: 74

Upvotes: 1

Marcus M&#252;ller
Marcus M&#252;ller

Reputation: 36337

Obvious answer: Test for 7 and 4:

bool check (unsigned int number) {
    if(number == 0)
        return false;
    while(number != 0) {
        unsigned int digit = number % 10;
        if( digit != 4 && digit != 7 )
            return false;
        number /= 10; // integer division, ie. "rounding down"
    }
    return true;
}

int main(int argc, char **argv) {
    for(int number = 0; number <= 100; number ++) {
        if(check(number)) 
             do_what_ever_you_want(number);
    }
    return 0;
}

Upvotes: 0

Related Questions