Friday, May 22, 2009

Unlucky Numbers

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)

Source: Topcoder

Solution:
Idea is to find the number of digits in a, let that be n. now
1. Start with a number which has n 4s, so if n is 2 start with 44, if n i 5 start with 44444.
2. increment the count.
3. If the curr number greater than b break and print the count.
4. Now start with the curr digit(last digit) of curr number, if the curr is 4 change it to 7 and
go to step2. if it is 7 set the curr digit to 4 and go to next digit to the left. do this step 4 again
until u reach a number greater than b, or reach a place where all digits are 7s and then u add 4
to it and go to step2.


Example:
a = 10 b = 500
actual numbers are 44, 47, 74, 77, 444, 447, 474, 477

6 comments:

P1 said...

this one isnt exactly clear.

Can you please post a pseudo code for this one.

surender said...

what about 40,41,42,43,45,46,48.........

Ghotter said...

@surrender... unluck number can contain only digits 4 or 7..... no other...

surender said...

sorry got it....needs to be either all 4's or 7's or combination of both...right!!

Siva said...
This comment has been removed by the author.
Siva said...
This comment has been removed by the author.