Số lượng số tối thiểu để biểu diễn mọi số nguyên dưới N dưới dạng tổng trong C++

Đề bài

Cho số nguyên N. 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 phần hoặc tất cả các số này ta có được tất cả các số trong khoảng 1 đến N. Nhiệm vụ là tìm giá trị nhỏ nhất của K.

Ví dụ

Nếu N = 8 thì đáp án K = 3

Nếu lấy các số 1, 2, 3, 4 thì cộng một phần hoặc tất cả các nhóm này ta có được mọi số trong khoảng 1 đến N

ví dụ: 1 = 1, 2 = 2, 3 = 3, 4 = 4, 5 = 1 + 4, 6 = 4 + 2, 7 = 4 + 3, 8 = 1 + 3 + 4

Thuật toán

Đếm số bit của số nguyên cho trước

Ví dụ mã C++

#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 << "Số lượng số tối thiểu cần = " << getMinNumbers(n) << endl;
    return 0;
}

Khi biên dịch và thực thi chương trình trên. Nó tạo ra đầu ra sau

Đầu ra

Số lượng số tối thiểu cần = 4