C++를 사용하여 모든 요소를 ​​동일하게 만들기 위한 최소 이동 횟수입니다.

문제 설명

N 요소의 배열과 정수 K가 주어지면 주어진 배열에 대해 다음 작업을 여러 번 수행할 수 있습니다. -

• K ^번째 삽입 배열 끝에 요소를 추가하고 배열의 첫 번째 요소를 삭제합니다.

작업은 배열의 모든 요소를 ​​동일하게 만드는 데 필요한 최소 이동 횟수를 찾는 것입니다. 불가능한 경우 -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