Finding n'th character in a Lucky String Lucky numbers are those numbers which contain only "4" and/or "5". For example 4, 5, 44, 54,55,444 are lucky numbers while 457, 987 ,154 are not.

Lucky number sequence is one in which all lucky numbers exist in increasing order for example       4,5,44,45,54,55,444,445,454,455...

Now we concatenate all the lucky numbers (in ascending order) to make a lucky string     "4544455455444445454455..."

Given n, your task is to find the nth digit of the lucky string. If the digit is 4 then you have to print "F" else you have to print "E".

1&lt;=n&lt;=10^15
JavaScript - 49

for(s=i=0;!(r=s[n+i++]);s+=i.toString(2));"FE"[r]


Execute this on a JavaScript console (tested on Node), with n set to the 1-based index of the digit you want.

Explanation:

The script builds a version of the lucky string, and stops when the character we're looking for exists.

Lucky string:        4 5 44 45 54 55
Generated string: 011011100101110111


The lucky string is equivalent to the concatenation of all binary numbers with the leading one stripped. We can get the index of the appropriate character in s from n by adding the number of leading ones in the string to skip, or, equivalently, how many binary numbers we generated. Luckily for us, we can just grab the current value of i.

It greatly helps to see the final values of s and i after running. For sake of brevity, I won't post a table here, but you can certainly check their values in the console.

Details:

s=i=0


Initializes s and i. s later becomes a string, but rather than initialize to "0", 0 works fine because of implicit type conversion.

i++


Increments i every iteration.

r=s[n+i++]


Gets the character of s at n+i (0 or 1) and stores it in r.

!(r=s[n+i++])


Loops while the character we are looking for is still undefined.

s+=i.toString(2)


Appends the next binary number in sequence to s.

"FE"[r]


Causes the expression to evaluate to F if r is 0, E if r is 1.