配列の範囲を完成させるために追加が必要な要素数を求めるC++プログラム

この問題では、n個の整数からなる配列arr[]が与えられます。私たちのタスクは、配列の最小値から最大値までの範囲に含まれるすべての要素が揃うようにするために、追加が必要な要素の数を求めるプログラムを作成することです。

問題の概要

ここで求めたいのは、配列に含まれる最小値から最大値までの連続した範囲を完成させるために、あといくつの要素を追加すればよいかという数です。

入出力例で問題を理解しよう

入力: arr[] = {5, 8, 3, 1, 6, 2}

出力: 2

解説:

配列の最小値は1、最大値は8なので、揃えるべき範囲は「1〜8」となります。

この範囲の中で配列に存在しないのは4と7の2つであるため、答えは2になります。

解法のアプローチ

最もシンプルな解決策は、範囲の中で配列に存在しない要素を見つけることです。そのためには、まず配列をソートし、隣接する要素同士を比較して「連続していない箇所(抜けている数字)」を順番に確認していきます。

アルゴリズム

ステップ1: 配列を昇順にソートします。

ステップ2: iを0からn-2まで動かしながら配列を走査します。

ステップ2.1: arr[i] + 1 が arr[i+1] と等しくない場合、countを1増やします。

ステップ3: countを出力します。

補足: 隣接する要素の差が2より大きい場合(例：1と5の間に2・3・4の3つが欠けているケース)では、「arr[i+1] - arr[i] - 1」を加算することで、より正確な不足要素数を求められます。

ソリューションの動作を示すプログラム

コード例(C++)

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

int calcEleRequired(int arr[], int n)
{
    int count = 0;
    sort(arr, arr + n);
    for (int i = 0; i < n - 1; i++)
        if (arr[i]+1 != arr[i+1] )
            count ++;

    return count;
}

int main()
{
    int arr[] = { 5, 7, 3, 1, 6, 2 };
    int n = sizeof(arr) / sizeof(arr[0]);
    cout<<"The number of elements required to complete the range is "<<calcEleRequired(arr, n);
    return 0;
}

出力

The number of elements required to complete the range is 1