C++で配列の全要素を等しくするための最小操作回数を求める方法

問題文

N個の要素からなる配列と整数Kが与えられます。この配列に対して、以下の操作を何度でも繰り返し実行できます。

• 配列のK番目の要素を配列の末尾に挿入し、同時に配列の先頭の要素を削除する

この操作を用いて、配列のすべての要素を等しくするために必要な最小の操作回数を求めるのが課題です。もしすべての要素を等しくすることが不可能な場合は、-1を出力してください。

具体例

配列 arr[] = {1, 2, 3, 4, 5, 6}、k = 6 の場合、最小5回の操作で全要素を等しくできます。

操作1: {2, 3, 4, 5, 6, 6}
操作2: {3, 4, 5, 6, 6, 6}
操作3: {4, 5, 6, 6, 6, 6}
操作4: {5, 6, 6, 6, 6, 6}
操作5: {6, 6, 6, 6, 6, 6}

アルゴリズム

この問題は以下の手順で解くことができます。

1. まず a[k] を末尾にコピーし、続いて a[k+1]、a[k+2] と順番に末尾へコピーしていきます。
2. 等しい要素だけがコピーされることを保証するため、K番目からN番目までの範囲のすべての要素が等しい必要があります。また、1番目からK番目までの範囲に存在する a[k] と異なる要素は、すべて削除される必要があります。
3. 1番目からK番目までの範囲で、a[k] と等しくない最も右側の要素に到達するまで操作を繰り返し適用します。

つまり、後半部分(K〜N)に異なる値が含まれている場合は答えは -1 となり、そうでなければ、前半部分(1〜K)の中で a[k] と異なる最後の要素の位置がそのまま必要な操作回数になります。

C++での実装例

#include <iostream>
#define SIZE(arr) (sizeof(arr) / sizeof(arr[0]))
using namespace std;

int getMinMoves(int *arr, int n, int k){
    int i;
    // K番目以降の要素がすべて等しいかチェック
    for (i = k - 1; i < n; ++i) {
        if (arr[i] != arr[k - 1]) {
            return -1;
        }
    }
    // 前半部分で a[k-1] と異なる最も右側の要素を探す
    for (i = k - 1; i >= 0; --i) {
        if (arr[i] != arr[k - 1]) {
            return i + 1;
        }
    }
    return 0;
}

int main(){
    int arr[] = {1, 2, 3, 4, 5, 6};
    int k = 6;
    cout << "Minimum moves required = " << getMinMoves(arr, SIZE(arr), k) << endl;
    return 0;
}

出力結果

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

Minimum moves required = 5

計算量について

このアルゴリズムの時間計算量は O(N) です。配列を最大2回走査するだけで答えが求まるため、非常に効率的です。空間計算量も O(1) と、追加のメモリをほとんど必要としません。