1362. Count Bit Changes to Sort Array

Sort the given array in non-decreasing order, then compare it position by position with the original array. Return the total number of bit positions that differ, summed over all positions (the sum of Hamming distances between each original element and the element that ends up in its place).

Input: A JSON object {"nums": [<non-negative integers>]}.

Output: Return the total number of differing bits across all positions.

Examples

Input: {"nums":[3,1,2]}
Output: 4
Explanation: Comparing against the sorted array gives 4 differing bits.

Input: {"nums":[1,2,3]}
Output: 0
Explanation: Already sorted, so nothing differs -> 0.

Constraints

• 1 <= len(nums) <= 10^4
• 0 <= nums[i] <= 10^9

Asked by