Unlucky Numbers

Unlucky Numbers (NOT HOMEWORK)

There are few numbers considered to be unlucky(It contains only 4 and 7. ). Our goal is to find count of such numbers in the range of positive integers a and b.

For Example:

Input : a = 10 b = 20

Output : 0

Input : a = 30 b = 50

Output : 2 (44, 47)

Below is the Code I tried out using a static array approach, wherein I calculate all possible unlucky numbers for a 32-bit integer initially. This is done in O(n) and later a sequential scan helps obtain the count which is again an O(n) operation. Is there a better approach to solve this without the help of a static array ?

#define MAX_UNLUCKY 1022
static int unlucky[MAX_UNLUCKY];  
int main(int argc, char **argv) { 
    int i, j, k;  
    int a, b, factor;  
    printf("Enter the numbers : \n");  
    scanf("%d",&a);  
    scanf("%d",&b);  
    unlucky[0] = 4;  
    unlucky[1] = 7;  
    factor = 10;  
    k = 1;  
    for(i = 2; i < MAX_UNLUCKY; ++i) 
        unlucky[i] = unlucky[(i >> 1) - 1]*factor + unlucky[k ^= 1];  
    for (i = 0; i < MAX_UNLUCKY;++i) 
        if (unlucky[i] > a) break;  
    for (k = i; k < MAX_UNLUCKY;++k) { 
        if (unlucky[k] > b) break;
        printf("Unlukcy numbers = %d\n", unlucky[k]);  
    }  
    printf ("Total Number of Un开发者_StackOverflow社区lucky numbers in this range is %d\n", k-i);  
    return (0);
}  

Consider the following:

How many numbers are there between

0x100 and 0x111?

100,101,110,111 ( 4 = 0x111 - 0x100 + 1 )

That's exactly how many unlucky numbers there are between 744 and 777 (744,747,774,777).

Now:

700 and 800 have the same number of unlucky numbers between them as 744 and 777. 744 is the smallest unlucky number greater than 700 and 777 is the greatest unlucky number smaller than 800.

No need to generate numbers, just substraction.

For cases like a = 10, b = 800, first find your number for 10-100 and then 100-800 (because you'll be counting some numbers twice):

For 10-100:

a = 44
b = 77

0x11 - 0x00 = 3 + 1 = 4 ( 44,47,74,77 )

For 100-800:

a = 444
b = 777

0x111 - 0x000 = 7 + 1 = 8 ( 444, 447, 474, 477, 744, 747, 774, 777 )

So between 10 and 800: 4+8 = 12 numbers, which is also correct.

This is also O(1) time & space if you find the auxiliary numbers efficiently, which shouldn't be too hard...