本教程将讨论将一个数字表示为最小伪二进制数之和。伪二进制数是由二进制数字0和1组成的数字。伪二进制数的例子有00、11、10、100、111、1011等。
以下是一些以伪二进制数之和表示的数字的示例。
Input : 23
Output : 11 + 11 + 1
Explanation : 23 = 11 + 11 + 1, sum of pseudo-binary numbers(11, 11, 1) is 23.
Input : 50
Output : 10 + 10 + 10 + 10 + 10
登录后复制
寻找解决方案的方法
以下是寻找表示N的最小伪二进制数的最佳方法之一。
-
取一个数字X，并根据数字N的各个位更新X的位数为1或0。
-
检查N的每个位数：
-
如果为0，则将X的该位设为0。
-
如果不为0，则将X的该位设为1。
-
假设N = 32，则X将变为11。
-
-
然后X将成为一个伪二进制数。
-
现在将N减去X，并重复步骤1，直到N变为零。
示例
上述方法的C++代码
#include
using namespace std;
int main(){
int N = 51;
// find a pseudo-binary number until N becomes 0.
cout
