-2
$\begingroup$

http://codeforces.com/problemset/problem/535/B

The problem is:

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: a lucky number n (1 ≤ n ≤ 109).

Output: index of n among all lucky numbers.

Examples:

  • input: 4, output: 1
  • input: 7, output: 2
  • input: 77, output: 6

The Editorial solutions says,

1 : 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.

2 : Count the number of lucky numbers less than or equal to n using bitmask (assign a binary string to each lucky number by replacing 4s with 0 and 7s with 1).

My question is ,how the Binary representations are used to calculate the position of the string?I am just not understanding this.

$\endgroup$
  • $\begingroup$ I can not understand your question! What means string in your last statement? Is it lucky number? $\endgroup$ – hadi.mansouri Aug 7 '17 at 6:54
  • 1
    $\begingroup$ What is the original problem? The link could rot, so you have to include the problem in your post. $\endgroup$ – Yuval Filmus Aug 7 '17 at 7:47
  • $\begingroup$ I included the problem statement. $\endgroup$ – Abhijit Sarkar Aug 10 '17 at 4:48
0
$\begingroup$

I think you have a mistake in formula for answer. Answer is

$$ index = \sum_{i=1}^{(x-1)} 2^i + f(m) + 1 = 2^1 + 2^2 + ... + 2^{x-1} + f(m) + 1 $$

And how it is:

Because lucky numbers are only two digit 4 and 7 so you can map each lucky number to a binary string by converting each 4 to 0 and each 7 to 1. For example: $74474 \to 10010$. By this way you can calculate index of each lucky number by computing decimal value of related binary string. But there is a problem in this way. All following lucky numbers have same index: $4, 44, 444, 4444, ...$ or $ 47, 447, 4447, ...$. To fix this problem you should compute number of all these situations lesser than lucky number which you want compute its index, and add this number to decimal value of binary representation of lucky number plus one.

Main problem is occurred when left most digit/digits is 4. You could find that for an lucky number with x digit, number of this situations is $\sum_{i=1}^{(x-1)} 2^i$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.