An integer is a lucky number if each number in it is 3 or 7. To give an example, the numbers 7, 73, and 33777 are lucky numbers. Your task is to calculate the number of lucky numbers between int(a) and int(b).
How could one achieve this efficiently (in less than 1 sec) without going through all the numbers? I have attempted many solutions in Java however none of them are fast enough.
Since you have to count the numbers and not list the numbers, you can use permutation and combination to find the answer.
Eg let say find between 1 and 999 where you can use 3, 7
Then you have 3 lengths single, double and triple digits with constraints on single and triple digits. For single since minimum number is 1 and 3, 7 both are greater there 2 numbers. For double digits you have no constraints hence you have 2 * 2 = 4 combinations Similarly for 3 digits as max number allowed is 9 in each place and 3,7 are lesser than them there will be 2 * 2 * 2 = 8
So answer is 14 after summing them all... This algorithm will run fast as it depends on the size of the numbers to generate ie o(n) time complexity where n is max length of number.