C ++
 Computer >> コンピューター >  >> プログラミング >> C ++

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

  1. C++を使用して配列を適切にするために削除する必要のある要素の最小数。

    問題の説明 配列「arr」が与えられた場合、タスクは、配列を適切にするために削除する要素の最小数を見つけることです。 シーケンスa1、a2、a3。 。 .anは、各要素a [i]に対して、a [i] + a [j]が2の累乗であるような要素a[j](iはjと等しくない)が存在する場合に適切と呼ばれます。 arr1[] = {1, 1, 7, 1, 5} 上記の配列で要素「5」を削除すると、配列は適切な配列になります。この後、arr [i] +arr[j]の任意のペアは2の累乗です- arr [0] + arr [1] =(1 + 1)=2この2の累乗 arr [0] + arr [

  2. C++で配列のすべての要素を同じにするための最小限の削除操作。

    問題の説明 要素が繰り返されるようなn個の要素の配列が与えられます。配列から任意の数の要素を削除できます。タスクは、配列から削除する要素の最小数を見つけて、配列を等しくすることです。 arr[] = {10, 8, 10, 7, 10, -1, -4, 12} すべての配列要素を同じにするには、強調表示された5つの要素を削除する必要があります。 アルゴリズム 1. Count frequency of each element 2. Find maximum frequecy among the frequencies. Let us call this as maxFrequncy 3.