'''simple docstring'''





def 	lowerCAmelCase_				(					snake_case_       : str			)    ->      int:


     '''simple docstring'''




     UpperCAmelCase_           =   0
     UpperCAmelCase_           =   len(snake_case_			)

     for i in range(n - 1			):
          for j in range(i + 1					,    snake_case_			):
               if arr[i] > arr[j]:
                    num_inversions += 1

     return num_inversions





def 	lowerCAmelCase_				(					snake_case_       : str			)    ->      Tuple:


     '''simple docstring'''




     if len(snake_case_			) <= 1:
          return arr, 0
     UpperCAmelCase_           =   len(snake_case_			) // 2
     UpperCAmelCase_           =   arr[0:mid]
     UpperCAmelCase_           =   arr[mid:]

     UpperCAmelCase_    , UpperCAmelCase_           =   count_inversions_recursive(snake_case_			)
     UpperCAmelCase_    , UpperCAmelCase_           =   count_inversions_recursive(snake_case_			)
     UpperCAmelCase_    , UpperCAmelCase_           =   _count_cross_inversions(snake_case_					,    snake_case_			)

     UpperCAmelCase_           =   inversion_p + inversions_q + cross_inversions
     return c, num_inversions





def 	lowerCAmelCase_				(					snake_case_       : Any					,    snake_case_       : Tuple			)    ->      Optional[Any]:


     '''simple docstring'''




     UpperCAmelCase_           =   []
     UpperCAmelCase_           =   UpperCAmelCase_           =   UpperCAmelCase_           =   0
     while i < len(snake_case_			) and j < len(snake_case_			):
          if p[i] > q[j]:
               # if P[1] > Q[j], then P[k] > Q[k] for all  i < k <= len(P)
               # These are all inversions. The claim emerges from the
               # property that P is sorted.
               num_inversion += len(snake_case_			) - i
               r.append(q[j]			)
               j += 1
          else:
               r.append(p[i]			)
               i += 1

     if i < len(snake_case_			):
          r.extend(p[i:]			)
     else:
          r.extend(q[j:]			)

     return r, num_inversion





def 	lowerCAmelCase_				(					)    ->      Optional[Any]:


     '''simple docstring'''




     UpperCAmelCase_           =   [10, 2, 1, 5, 5, 2, 11]

     # this arr has 8 inversions:
     # (10, 2), (10, 1), (10, 5), (10, 5), (10, 2), (2, 1), (5, 2), (5, 2)

     UpperCAmelCase_           =   count_inversions_bf(snake_case_			)
     UpperCAmelCase_    , UpperCAmelCase_           =   count_inversions_recursive(snake_case_			)

     assert num_inversions_bf == num_inversions_recursive == 8

     print("number of inversions = "					,    snake_case_			)

     # testing an array with zero inversion (a sorted arr_1)

     arr_a.sort()
     UpperCAmelCase_           =   count_inversions_bf(snake_case_			)
     UpperCAmelCase_    , UpperCAmelCase_           =   count_inversions_recursive(snake_case_			)

     assert num_inversions_bf == num_inversions_recursive == 0
     print("number of inversions = "					,    snake_case_			)

     # an empty list should also have zero inversions
     UpperCAmelCase_           =   []
     UpperCAmelCase_           =   count_inversions_bf(snake_case_			)
     UpperCAmelCase_    , UpperCAmelCase_           =   count_inversions_recursive(snake_case_			)

     assert num_inversions_bf == num_inversions_recursive == 0
     print("number of inversions = "					,    snake_case_			)


if __name__ == "__main__":
    main()





'''simple docstring'''





def 	lowerCAmelCase_				(					snake_case_       : int					,    snake_case_       : int			)    ->      str:


     '''simple docstring'''




     if a < 0 or b < 0:
          raise ValueError("the value of both inputs must be positive"			)
     UpperCAmelCase_           =   str(bin(snake_case_			)			)[2:]  # remove the leading "0b"
     UpperCAmelCase_           =   str(bin(snake_case_			)			)[2:]
     UpperCAmelCase_           =   max(len(snake_case_			)					,    len(snake_case_			)			)
     return "0b" + "".join(
         str(int("1" in (char_a, char_b)			)			)
         for char_a, char_b in zip(a_binary.zfill(snake_case_			)					,    b_binary.zfill(snake_case_			)			)			)


if __name__ == "__main__":
    import doctest

    doctest.testmod()




