Sort by Equal-Bit Swaps
Problem
You may swap two neighbouring elements of a list, as often as you like, but only when both have the same number of 1 bits in binary. Given a list of non-negative whole numbers, return True if these swaps can sort it into ascending order, and False otherwise.
Examples
Input: nums = [6, 5, 3, 16, 8, 31]
Output: True
Why: 6, 5, 3 all have two 1 bits and sort to 3, 5, 6; 16 and 8 have one and sort to 8, 16Input: nums = [6, 3, 1, 4, 2]
Output: False
Why: 6 has two 1 bits, 1 has one, so 1 can never get past 6Input: nums = [7]
Output: True
Why: edge case, a single value is already sortedHints
0 / 3
Bubble sort shows that swapping neighbours alone is enough to sort any stretch. The question is which stretches the rule lets you work on.
Split the list into maximal runs of neighbours that share a bit count. Inside a run anything can be rearranged, but no value can ever leave its run, because it would have to swap with a value whose bit count differs.
Each run can be sorted on its own, so the whole list can be sorted exactly when every run's smallest value is at least the largest value of the run before it. Walk the runs once, carrying the previous run's maximum.
Solution
Two neighbours with different bit counts can never swap, so the boundaries between runs of equal bit count never move and every value stays inside its run. Within a run, neighbour swaps can reach any order, just as bubble sort sorts with nothing else, so each run can end up sorted. The whole list is then sorted exactly when the runs fit together, which means no run holds a value smaller than the largest value of the run before it. Time is O(n log m) for n values up to m, since counting bits takes O(log m) each, and space is O(1).
def can_sort(nums):
prev_max = -1 # largest value in the runs already checked
i = 0
while i < len(nums):
bits = bin(nums[i]).count("1")
lo = hi = nums[i]
j = i
while j < len(nums) and bin(nums[j]).count("1") == bits:
lo, hi = min(lo, nums[j]), max(hi, nums[j]) # one run of equal bit count
j += 1
if lo < prev_max: # this run's smallest can never pass the earlier maximum
return False
prev_max, i = hi, j
return True
print(can_sort([6, 5, 3, 16, 8, 31])) # -> True
print(can_sort([6, 3, 1, 4, 2])) # -> False
print(can_sort([7])) # -> TrueStuck on the idea rather than the code? Bubble Sort covers it.