### PROBLEM LINKS

### DIFFICULTY

EASY

### EXPLANATION

The straightforward approach of writing a function that simply reverses the bits of an index to get the new index suffices (recalling that indices with fewer bits than k are padded with leading zeros). The complexity of this algorithm is O(n log n) where n = 2^k is the length of the string. While this was fast enough for the contest, an O(n) algorithm can be devised using a slighly more clever approach.

Let a[] be the original string and b[] be the scrambled string we are to compute. Consider a recursive function scramble(x,n,d,i) that will correctly place every character in the substring of a[] of length n starting at index x in its correct place in b[]. Here, d and i are auxiliary variables that will be used to index a location in b[] at the base of the recursion. The base of the recursion is when n == 1 in which case a[x] is assigned to b[d]. Otherwise, if n > 1 then just recursively call serve(x,n/2,d,i * 2) followed by serve(x+n/2,n/2,d+i,i * 2). Initially call serve(0,n,0,1) to begin the recursion. One can see that at a particular recursive call at depth j in the recursion, the function is basically taking the j’th most significant digit of l and placing it at the k-j’th bit of d which, in effect, is reversing the digits.

While the depth of the recursion is O(log n), one sees that only 1 call to the function is at depth 1, 2 are at depth 2, 4 are at depth 3, 8 are at depth 4, etc. Summing over all recursive calls, we see the total number of times serve() is called throughout the recursion is only O(n).

For interest’s sake, reversing the bits of a binary number is not just some contrived problem that resides solely in algorithms competitions. It is a fundamental subroutine used in some implementations of the Fast Fourier Transform which is, perhaps, one of the most important algorithms in computing science with applications in digital signal processing and fast integer multiplication.