Unlucky numbers

Question

Bad Numbers (NOT HOMEWORK)

There are several numbers that are considered unsuccessful (it contains only 4 and 7.). Our goal is to find the number of such numbers in the range of positive integers a and b.
For instance:
Input: a = 10 b = 20
Output: 0
Input: a = 30 b = 50
Output: 2 (44, 47)

Below is the code I tried using the static array approach, in which I first compute all the possible unsuccessful numbers for a 32-bit integer. This is done in O (n), and then a sequential scan helps to get a counter, which again is an O (n) operation. Is there a better approach to solving this without using 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 Unlucky numbers in this range is %d\n", ki); return (0); } 

Answer 1

Consider the following:

How many numbers exist between

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

How many total unlucky numbers exist 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 largest unlucky number, less than 800.

No need to generate numbers, just subtraction.

For cases like a = 10, b = 800, first find your number for 10-100, and then 100-800 (because you will count several 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.

It is also O (1) time and space if you find auxiliary numbers efficiently, which should not be too heavy ...