Số tối thiểu cần thiết để biểu thị mọi số nguyên dưới N dưới dạng tổng trong C ++

Tuyên bố vấn đề

Chúng ta có một số nguyên N. Chúng ta cần biểu diễn N dưới dạng tổng của K số nguyên sao cho bằng cách cộng một số hoặc tất cả các số nguyên này, chúng ta có thể nhận được tất cả các số trong phạm vi từ 1 đến N. Nhiệm vụ là tìm giá trị nhỏ nhất của K

Ví dụ

Nếu N =8 thì câu trả lời cuối cùng, tức là K sẽ là 3

Nếu chúng ta lấy các số nguyên 1, 2, 3 và 4 sau đó thêm một số hoặc tất cả các nhóm này, chúng ta có thể nhận được tất cả các số trong phạm vi từ 1 đến N

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

Thuật toán

Count number of bits from given integer

Ví dụ

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

Khi bạn biên dịch và thực thi chương trình trên. Nó tạo ra kết quả sau

Đầu ra

Minimum required numbers = 4