C++で1〜Nのすべての整数を部分和として表すために必要な最小の個数を求める方法

問題文

整数 N が与えられます。K 個の整数を選び、そのうちのいくつか（またはすべて）を足し合わせることで、1 から N までの範囲に含まれるすべての整数を作り出せるようにします。このとき必要な K の最小値を求めるのがこの問題の目的です。

例

N = 8 の場合、答えは K = 4 となります。

たとえば 1, 2, 3, 4 の 4 つの整数を選ぶと、それらをいくつか組み合わせるだけで、1 から 8 までのすべての数を作り出せます。

1 = 1
2 = 2
3 = 3
4 = 4
5 = 1 + 4
6 = 2 + 4
7 = 3 + 4
8 = 1 + 3 + 4

アルゴリズム

この問題は、与えられた整数 N のビット数（2進表現の桁数）を数えるだけで解くことができます。

K 個の整数から作れる空でない部分集合の和は、最大で 2^K − 1 通りです。1 から N までの N 個の数をすべてカバーするには 2^K − 1 ≥ N が必要であり、これを満たす最小の K は「N の 2進表現におけるビット数」と一致します。

計算量

N を 1 ビットずつ右シフトしながらカウントするため、時間計算量は O(log N)、空間計算量は O(1) と非常に効率的です。

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 << "Minimum required numbers = " << getMinNumbers(n) << endl;
    return 0;
}

このプログラムをコンパイルして実行すると、次の出力が得られます。

出力

Minimum required numbers = 4

N = 8 は 2進数で「1000」と表され、ビット数は 4 です。そのため、必要な最小の整数の個数も 4 となります。