Minimum numbers needed to express every integer below N as a sum in C++

Problem statement

We have an integer N. We need to express N as a sum of K integers such that by adding some or all of these integers we can get all the numbers in the range 1 to N. The task is to find minimum value of K

Example

If N = 8 then final answer i.e. K would be 3

If we take integers 1, 2, 3, and 4 then adding some or all of these groups we can get all number in the range 1 to N

e.g. 1 = 1 2 = 2 3 = 3 4 = 4 5 = 1 + 5 6 = 4 + 2 7 = 4 + 3 8 = 1 + 3 + 4

Algorithm

Count number of bits from given integer

Example

 Live Demo

#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; }

When you compile and execute above program. It generates following output

Output

Minimum required numbers = 4