C++を使用してすべての要素を等しくするための最小移動数。

問題の説明

N個の要素の配列と整数Kが与えられた場合、与えられた配列に対して次の操作を何度でも実行できます-

• K ^th を挿入します 配列の最後にある要素を削除し、配列の最初の要素を削除します。

タスクは、配列のすべての要素を等しくするために必要な最小移動数を見つけることです。不可能な場合は-1を印刷します

If arr[] = {1, 2, 3, 4, 5, 6} and k = 6 then minimum 5 moves are
required:
Move-1: {2, 3, 4, 5, 6, 6}
Move-2: {3, 4, 5, 6, 6, 6}
Move-3: {4, 5, 6, 6, 6, 6}
Move-4: {5, 6, 6, 6, 6, 6}
Move-5: {6, 6, 6, 6, 6, 6}

アルゴリズム

1. First we copy a[k] to the end, then a[k+1] and so on
2. To make sure that we only copy equal elements, all elements in the range K to N should be equal. We need to remove all elements in range 1 to K that are not equal to a[k]
3. Keep applying operations until we reach the rightmost term in range 1 to K that is not equal to a[k].

例

#include <iostream>
#define SIZE(arr) (sizeof(arr) / sizeof(arr[0]))
using namespace std;
int getMinMoves(int *arr, int n, int k){
   int i;
   for (i = k - 1; i < n; ++i) {
      if (arr[i] != arr[k - 1]) {
         return -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