题目内容

曾经有一个名叫小红的年轻程序员，他梦想成为一名优秀的算法工程师。一天，他遇到了这样一个问题：给定一个由 $n$ 个非负整数组成的数组，他每次可以选择其中一个数的二进制表示中的某一位进行取反操作，问他最少需要多少次操作才能使得这个数组中的所有数相等。

小红日思夜想也没有想出来怎么解决这个问题，于是，他决定请教你这个问题，希望你能够提供一个更加高效的算法，以便让他能够早日实现自己的梦想。

输入描述

第一行输入一个正整数 $n$ ，代表数组的大小。

第二行输入 $n$ 个非负整数 $a_i$ ，代表数组的元素。

$1\le n \le 10^5$ ， $0 \le a_i \le 2^{31} -1$

输出描述

一个整数，代表最小的操作次数。

样例

输入

5
3 5 1 4 8

输出

6

思路:贪心

容易发现，从二进制的视角来看，只要每一个$bit$都变成一样即可。所以可以分别独立的考虑每一位的最小代价。那么对于每一个$bit$ , 我们要么将所有的$0$ 都变成 $1$ , 要么将所有的$1$ 都变成 $0$. 所以最小代价就是$0,1$ 中出现次数少的那个。