C ++を使用して、配列から最後に削除された要素の位置を見つけます

この問題では、サイズNと整数値Mの配列arr []が与えられます。私たちのタスクは、配列から最後に削除された要素の位置を見つけることです。 。

配列からの値の削除は、操作-

• 配列arr[i]の要素の場合。 arr [i]> Mの場合、値をポップし、arr[i]--Mを配列の最後にプッシュします。それ以外の場合は、アレイから削除します。

配列が要素で構成されるまで操作を実行します。

問題を理解するために例を見てみましょう

入力

arr[] = {5, 4, 8}, M = 3

出力

3

説明

Removing values using operations,
{5, 4, 8} -> {4, 8, 2} -> {8, 1, 2} -> {1, 2, 5} -> {2, 5} -> {5} -> {2} ->
empty array.
The last value removed is 8, position is 3.

ソリューションアプローチ

この問題の簡単な解決策は、最後に削除される各値の最大値が ceil（arr [i] / M）であるという事実を使用して、削除される最後の値を見つけることです。 。

最後に配列を終了する要素の位置を見つけるために、配列をトラバースし、最大値が ceil（arr [i] / M）の位置を格納します。 。

例

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

#include <iostream>
using namespace std;
int findLastRemPos(int arr[], int n, int m){
   for (int i = 0; i < n; i++) {
      arr[i] = (arr[i] / m + (arr[i] % m != 0));
   }
   int lastRemPos = -1, largestVal = -1;
   for (int i = n - 1; i >= 0; i--) {
      if (largestVal < arr[i]) {
         largestVal = arr[i];
         lastRemPos = i;
      }
   }
   return lastRemPos + 1;
}
int main(){
   int arr[] = {5, 4, 8, 1};
   int n = sizeof(arr) / sizeof(arr[0]);
   int m = 3;
   cout<<"The position of last removed element in the array is "<<findLastRemPos(arr, n, m);
   return 0;
}

出力

The position of last removed element in the array is 3