盗まれたキーボードの最小台数を求めるC++プログラム

問題概要

n個の要素を持つ配列Aがあるとします。ある電器店で昨夜、強盗事件が発生しました。店内にあったすべてのキーボードには、ある整数xから始まる連番が振られていました。例えば、x=4で店に3台のキーボードがあれば、それらの番号は4、5、6です。また、x=10で7台あれば、番号は10、11、12、13、14、15、16となります。強盗の後、n台のキーボードだけが残り、その番号が配列Aに格納されています。ここで、盗まれたキーボードの最小台数を求めることが課題です。

例えば、入力が A = [10, 13, 12, 8] の場合、出力は 2 になります。これは x = 8 のとき、盗まれたキーボードの最小台数が2台となるためです。具体的には、番号9と11のキーボードが盗まれたことになります。

解法のアプローチ

この問題を解くためには、以下の手順に従います。

配列Aをソートする
n := Aのサイズ
return A[n - 1] - A[0] + 1 - n

このアプローチの背後にある考え方はシンプルです。

• 配列をソートすることで、残っているキーボードの最小番号と最大番号がわかります。
• 強盗が発生していなければ、A[0]からA[n-1]までの連続した番号がすべて存在するはずでした。
• その範囲に含まれる番号の総数は A[n-1] - A[0] + 1 であり、実際に残っている台数はnなので、その差が盗まれたキーボードの最小台数となります。

C++での実装例

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

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

int solve(vector<int> A) {
    sort(A.begin(), A.end());
    int n = A.size();
    return A[n - 1] - A[0] + 1 - n;
}

int main() {
    vector<int> A = { 10, 13, 12, 8 };
    cout << solve(A) << endl;
}

実行結果

入力：

{ 10, 13, 12, 8 }

出力：

2

計算量の分析

このアルゴリズムの時間計算量は O(n log n) で、これは主にソート処理にかかるコストによるものです。範囲の計算自体は定数時間で完了するため、全体の効率はソートに依存します。空間計算量は追加のデータ構造を使用しないため O(1) となり、非常にメモリ効率の良い解法といえます。