Problem Statement
Let nums be an array of size n, where n=2^k for some integer k. Then the indices of nums can each be written in binary using k bits. In this problem, you will permute nums by moving each element to the position whose index is determined by reading the binary representation of the element's original index backwards. For example, if n=32, then each index can be written using 5 bits. Consider the element at index 25. 25 is written as 11001 in binary. Reading the binary representation backward, we get 10011, which is the binary representation of 19. Therefore, the element at index 25 of nums would be moved to index 19 of the resulting array. Similarly, the element at index 2 (binary 00010) would be moved to index 8 (binary 01000), and so on for all the remaining elements of nums.
Given an array nums of type int[], return the permuted array according to this transformation.
Definition
- Class:
- BitReversals
- Method:
- permutation
- Parameters:
- int[]
- Returns:
- int[]
- Method signature:
- int[] permutation(int[] nums)
- (be sure your method is public)
Notes
- Although it may sound obscure, this transformation is actually very common in scientific computations.
Constraints
- nums contains 1, 2, 4, 8, 16, or 32 elements.
- Each element of nums is between 1 and 1000, inclusive.
Examples
{ 5,13,99,33 }Returns: { 5, 99, 13, 33 }Each index is written as a two-bit number. The reversals of those bits and the resulting indices are shown in the following table: reversed resulting index bits bits index --------------------------------------- 0 00 00 0 1 01 10 2 2 10 01 1 3 11 11 3 So the 5 stays in place, the 13 moves from position 1 to position 2, the 99 moves from position 2 to position 1, and the 33 stays in place.{ 1000 }Returns: { 1000 }{ 57,62,19,38,17,91,90,22 }Returns: { 57, 17, 19, 90, 62, 91, 38, 22 }{ 5,5,5,5,5,5,5,5 }Returns: { 5, 5, 5, 5, 5, 5, 5, 5 }{ 9,34,8,7,26,12,1,4,30,22,3,6,37,11,10,5 }Returns: { 9, 30, 26, 37, 8, 3, 1, 10, 34, 22, 12, 11, 7, 6, 4, 5 }
Back to all problems