-
Notifications
You must be signed in to change notification settings - Fork 25
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
某算法竞赛初试题解 - 3K问题 #15
Milestone
Comments
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
题目
给定包含N个正整数的非递减数组A,假设该数组以以下形式保存了某个正整数K的值,即:
$$K = \sum_{i=0}^N 2^{A[i]}$$
例如给定$A=[1,4,5]$,则$K=2^1+2^4+2^5=50$。
则给出一个算法,计算出$3K$的二进制表示中为
1
的比特个数。例如$3K=150=10010110_2$,程序返回值为
4
。要求:时间复杂度控制在$O(N)$;空间复杂度控制在$O(1)$。
题解
对于二进制的题,一般都要从二进制本质出发,从数组A的定义可以得到:
然后我们对数组中的每一位都加上1,然后合并回到数组A中,得到新的数组B,那么问题就转化为计算数组B代表的K的二进制中比特
1
的个数,为了表述方便,我们下文依然用数组A来举例表述。让我们再次回到二进制的基本概念上来,对于一个二进制数:
$$110_2=0\times 2^0 + 1\times 2^1 + 1\times 2^2$$
那么数组A所代表的数字就变成了:
$$K=2^1+2^4+2^5=1\times2^1+0\times2^2+0\times2^3+1\times2^4+1\times2^5=11001_2$$
也就是说,数组A中的每一位数字
A[i]
,都代表了K的二进制中低A[i]
位的比特位为1
。于是问题就简化为,将数组B表示的每个比特位加起来,最后的结果中
1
的个数,就是我们想要的结果。代码实现如下:
题外话
然而,这道题是我在比赛结束一个小时之后才解出来的,认清了自己是菜鸡的事实。
The text was updated successfully, but these errors were encountered: