I am looking at this code challenge:

Write a function that takes one integer argument (index), which will return a number in the range 0-1. The returned number can be derived by successively splitting ranges into smaller ranges, each time selecting the largest available range, giving precedence to the right most range when tied. The number of splits corresponds to the argument. The offset where the last split occurred should be returned.

Here follows a visualisation of how the expected results are produced for the first few values for the index argument:

If possible, the function should be O(1).

I can understand the logic that is performed here, but I can't see how this could possibly be done in O(1). How could that be achieved?

CodePudding user response：

You could look at how these fractions are expressed as a division of two integers. The sequence then is:

1, 1/2, 3/4, 1/4, 7/8, 5/8, 3/8, 1/8, 15/16, 13/16, 11/16, 9/16, 7/16...

There is a pattern here that looks like this:

Denominator: