Difficulty: Easy | Acceptance: 61.00% | Paid: No Topics: Array, Sorting
You are given an array of integers. Sort the array in ascending order based on the value of each integer’s binary reflection. The binary reflection of an integer is obtained by reversing the bits in its binary representation.
For example, the binary representation of 6 is 110. Reversing the bits gives 011, which is 3 in decimal. Therefore, the binary reflection of 6 is 3.
Return the sorted array.
- Examples
- Constraints
- Approach 1: Brute Force with Pair Array
- Approach 2: Custom Sort Comparator
- Approach 3: Precompute Reflections with Index Mapping
Examples
Example 1
Input: nums = [5, 2, 3, 6]
Output: [2, 3, 6, 5]
Explanation:
- Binary reflection of 5 (101) is 5
- Binary reflection of 2 (10) is 1
- Binary reflection of 3 (11) is 3
- Binary reflection of 6 (110) is 3
Sorted by reflection: [2(1), 3(3), 6(3), 5(5)]
Example 2
Input: nums = [1, 2, 3, 4]
Output: [1, 2, 4, 3]
Explanation:
- Binary reflection of 1 (1) is 1
- Binary reflection of 2 (10) is 1
- Binary reflection of 3 (11) is 3
- Binary reflection of 4 (100) is 1
Sorted by reflection: [1(1), 2(1), 4(1), 3(3)]
Constraints
- 1 <= nums.length <= 100
- 1 <= nums[i] <= 10^9
Approach 1: Brute Force with Pair Array
Intuition Create pairs of (binary reflection, original value) for each number, then sort these pairs by the reflection value and extract the original values.
Steps
- Calculate binary reflection for each number
- Create an array of pairs (reflection, original)
- Sort the array by reflection values
- Extract and return original values in sorted order
class Solution:
def binaryReflection(self, n: int) -> int:
result = 0
while n > 0:
result = (result << 1) | (n & 1)
n >>= 1
return result
def sortIntegersByBinaryReflection(self, nums: list[int]) -> list[int]:
pairs = [(self.binaryReflection(num), num) for num in nums]
pairs.sort(key=lambda x: x[0])
return [num for _, num in pairs]
Complexity
- Time: O(n log n × k) where k is the average number of bits in each number
- Space: O(n) for storing pairs
- Notes: Simple and readable, but uses extra space for pairs
Approach 2: Custom Sort Comparator
Intuition Use the language’s built-in sort with a custom comparator that compares binary reflections directly, avoiding the need to create separate pair arrays.
Steps
- Define a comparator function that compares binary reflections
- Apply the comparator to sort the array
- Return the sorted array
class Solution:
def binaryReflection(self, n: int) -> int:
result = 0
while n > 0:
result = (result << 1) | (n & 1)
n >>= 1
return result
def sortIntegersByBinaryReflection(self, nums: list[int]) -> list[int]:
nums.sort(key=lambda x: self.binaryReflection(x))
return nums
Complexity
- Time: O(n log n × k) where k is the average number of bits
- Space: O(1) extra space (in-place sort)
- Notes: More memory efficient but may compute binary reflection multiple times for the same element during sorting
Approach 3: Precompute Reflections with Index Mapping
Intuition Precompute all binary reflections once and store them, then use these precomputed values during sorting to avoid redundant calculations.
Steps
- Calculate and store binary reflection for each number
- Create indexed array with original indices
- Sort indices based on precomputed reflections
- Build result array using sorted indices
class Solution:
def binaryReflection(self, n: int) -> int:
result = 0
while n > 0:
result = (result << 1) | (n & 1)
n >>= 1
return result
def sortIntegersByBinaryReflection(self, nums: list[int]) -> list[int]:
reflections = [self.binaryReflection(num) for num in nums]
indexed = list(enumerate(nums))
indexed.sort(key=lambda x: reflections[x[0]])
return [num for _, num in indexed]
Complexity
- Time: O(n × k + n log n) where k is the average number of bits
- Space: O(n) for storing reflections
- Notes: Computes each reflection exactly once, optimal for large arrays