在C ++中将N以下的每个整数表示为总和所需的最小数字
问题陈述
我们有一个整数N。我们需要将N表示为K个整数的总和，这样，通过将这些整数中的一些或全部相加，我们可以得到1到N范围内的所有数字。任务是找到K的最小值
示例
如果N=8，则最终答案，即K为3
如果我们取整数1、2、3和4，然后加上这些组中的一些或全部，我们可以得到1到N之间的所有数字
e.g. 1 = 1 2 = 2 3 = 3 4 = 4 5 = 1 + 5 6 = 4 + 2 7 = 4 + 3 8 = 1 + 3 + 4
算法
Count number of bits from given integer
示例
#include <bits/stdc++.h>
using namespace std;
int getMinNumbers(int n) {
int cnt = 0;
while (n) {
++cnt;
n = n >> 1;
}
return cnt;
}
int main() {
int n = 8;
cout << "Minimum required numbers = " <<getMinNumbers(n) << endl;
return 0;
}当您编译并执行上述程序时。它产生以下输出
输出结果
Minimum required numbers = 4