Twitter-OA-grouping ones and zeros

groupingOnesZeros.py

"""
Given the binary array, a move is defined as a swapping adjacent 1 and 0. 
Return the min number of moves to sort the array.
Here "sort" is defined as a grouping all 1's in one end, all 0's in the other end,
and which end doesn't matter. For example, arr=[1,1,0,0], no need to move as it's
already sorted.

Example 1:
Input:  arr = [1, 0, 1, 1]
Output: 1 
Explanation: Just one move (arr[0]<->arr[1]) yields a sorted array [0, 1, 1, 1]

Example 2:
Input:  arr = [1, 0, 0, 1, 0, 1] 
Output: 4 
Explanation: 
  100101
  --
->010101 move1
   --
->001101 move2
     --
->001011 move3
    --
->000111 move4
"""
class Solution:
    def groupingOnesZeros(self, arr):
        """
        bubble sort     i=0 1 2 3 4 5
        first pass: i=0: [1-0 0 1 0 1]
                    i=1: [0 1-0 1 0 1] swap=1
                    i=2: [0 0 1-1 0 1] swap=2
                    i=3: [0 0 1 1-0 1]
                    i=4: [0 0 1 0 1 1] swap=3
       second pass: i=1: [0 0-1 0 1 1]
                    i=2: [0 0 0-1 1 1] swap=4
        """
        n = len(arr)
        firstHalfSum = sum([x for x in arr[:n//2] if x == 1])
        lastHalfSum = sum([x for x in arr[n//2:] if x == 1])
        #print(f'n//2={n//2}, firstHalfSum={firstHalfSum}; lastHalfSum={lastHalfSum}')
        swap = 0
        # bubble-sort swapping adjacent elements
        if firstHalfSum  < lastHalfSum:
            # zeros followed by ones
            print("grouping [0's, 1's], thus if found (1,0) pair, swap")
            for i in range(n-1):
                for j in range(n-1-i): # last element is in place
                    if arr[j] > arr[j+1]: # if arr[i]=1, arr[i+1]=0, then swap
                        print(f'{i+1}-th pass: swap{arr[i],arr[i+1]}=swap(arr[{i}]<->arr[{i+1}])')
                        arr[j], arr[j+1] = arr[j+1], arr[j] #
                        swap += 1
        else:
            # ones followed by zeros
            print("grouping [1's, 0's], thus if found (0,1) pair, swap")
            for i in range(n-1):
                for j in range(n-1-i): # last element is in place
                    if arr[j] < arr[j+1]: # if arr[i]=0, arr[i+1]=1, then swap   
                        print(f'{i+1}-th pass: swap{arr[i],arr[i+1]}=swap(arr[{i}]<->arr[{i+1}])')
                        arr[j], arr[j+1] = arr[j+1], arr[j] #
                        swap += 1
        return swap
 
s = Solution()
arrays = [[1, 0, 1, 1], # 1
         [1, 1, 1, 0, 0, 0], # 0
         [1, 0, 0, 1, 0, 1]  # 4
        ]
for arr in arrays:
    print('arr=', arr)
    print('swaps=',s.groupingOnesZeros(arr))
    print()