PROBLEM
You are given a lucky number n. Lucky numbers are the positive integers whose decimal representations contain only the lucky digits 4 and 7. For example, numbers 47, 744, 4 are lucky and 5, 17, 467 are not.
If we sort all lucky numbers in increasing order, what’s the 1-based index of n?
Input:
4
7
44
47
output:
1
2
3
4
Solution:Consider n has x digits, f(i) = decimal representation of binary string i, m is a binary string of size x and its i - th digit is 0 if and only if the i - th digit of n is 4. Finally, answer equals to 21 + 22 + … + 2x - 1 + f(m) + 1.
I didnt quite understand it.
There’s another very easy solution of is using queue. Initially insert two numbers 4 and 7 in the queue or you can insert pair which corresponds to the number and its index i.e.
Initially queue has (4,1) and (7,2)
Next, Pop (4,1) and insert (4*10 + 4,3),(4*10 +7,4) i.e. append 4 and 7 to the popped item
Pop (7,2) and push (7*10 +4,5) and (7*10 +7,6) and so on...
@damn_me
Thank you so much for your kind concern.
I had an idea of this approach but i want to know, whats the basis of the solution,which i provided above.
For now, assume that lucky strings are those who have only 0’s and 1’s. Hence the first few lucky strings would be:
- 0
- 1
- 00
- 01
- 10
- 11
- 000
- 001
- 010
- 011
- 100
- 101
- 110
- 111
Now if I were to replace all 0’s with 4’s, and all 1’s with 7’s, it is easy to see that we obtain your list of lucky numbers.
We can now clearly see how the solution you posted works. If the number has x digits, then the index of the lowest x-digit number is simply 2^x - 1. It is then a matter of providing an offset to get the index of the desired number, which is what your solution effectively does.
Eg: Consider 474. It has 3-digits (x = 3), and corresponds to 010 of my list. The index of the lowest 3-digit number is 2^3 - 1 = 7. We now add the decimal representation of 010 to 7, which is 2 + 7 = 9. As you can see, this is the correct answer.
I hope this answers your query. 