C++でのエリミネーションゲーム

1からnまでのソートされた整数のリストがあるとします。それは左から始まり右で終わります。リストの最後に到達するまで、最初の番号とその後のすべての番号を削除する必要があります。前の手順をもう一度繰り返しますが、今回は右から左に、残りの番号から右端の番号と1つおきの番号を削除します。 1つの数字が残るまで、左から右、右から左に交互に手順を繰り返します。長さnのリストで始まる最後の番号を見つける必要があります。

したがって、入力がn =9の場合、手順は次のようになります-

• 1 、2、 3 、4、 5 、6、 7 、8、 9

• 2、 4 、6、 8

• 2 、6

• 6

したがって、答えは6になります。

これを解決するには、次の手順に従います-

• 左：=1、ヘッド：=1、ステップ：=1、レム：=n

• rem> 1

  • leftがゼロ以外の場合、またはremが奇数の場合、head：=head + step

  • ステップ：=ステップ* 2

  • 左：=左の逆

  • rem：=rem / 2

• リターンヘッド

例（C ++）

理解を深めるために、次の実装を見てみましょう-

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   int lastRemaining(int n) {
      int head = 1;
      int step = 1;
      int rem = n;
      int left = 1;
      while(rem > 1){
         if(left || rem % 2 == 1){
            head += step;
         }
         step *= 2;
         left = !left;
         rem /= 2;
      }
      return head;
   }
};
main(){
   Solution ob;
   cout << (ob.lastRemaining(9));
}

入力

9

出力

6