C++でnを表すために必要なバイナリデシマルの最小個数を求めるプログラム

問題の概要

ある正整数 n が与えられます。バイナリデシマル(binary decimal)とは、10進表記におけるすべての桁が 0 または 1 のみで構成されている正整数のことです。たとえば、1001(千一)はバイナリデシマルですが、1021 は 2 という桁を含むため該当しません。

この問題では、与えられた数 n を、いくつかのバイナリデシマル(同じ数を何度使っても構いません)の和として表現することを考えます。その際に必要となるバイナリデシマルの最小個数を求めるのが目的です。

たとえば、入力が n = 121 の場合、出力は 2 になります。これは、121 を 110 + 11 または 111 + 10 という2つのバイナリデシマルの和で表せるためです。

解法の考え方

この問題の答えは、n の各桁の数字のうち最大のものになります。その理由は以下の通りです。

• 1つのバイナリデシマルは、どの桁に対しても最大で 1 しか加算できません。
• したがって、n の中で最も大きい桁の値 d を実現するには、少なくとも d 個のバイナリデシマルが必要です。
• 逆に d 個あれば、各桁の値をちょうど組み合わせて表現できるため、d 個で必ず足りります。

つまり、n を 1 桁ずつ走査して最大の桁を求めるだけで答えが得られます。

アルゴリズムの手順

ans := -1
while n > 0, do:
    ans := maximum of ans and (n mod 10)
    n := n / 10
return ans

C++での実装例

理解を深めるために、以下の実装例を見てみましょう。

#include <bits/stdc++.h>
using namespace std;

int solve(int n) {
    int ans = -1;
    while (n > 0) {
        ans = max(ans, n % 10);
        n /= 10;
    }
    return ans;
}
int main() {
    int n = 121;
    cout << solve(n) << endl;
}

入力

121

出力

2

計算量

このアルゴリズムの時間計算量は、n の桁数に比例する O(log₁₀ n) であり、空間計算量は O(1) です。追加のデータ構造も不要で、非常にシンプルかつ効率的な解法となっています。