C ++中的消除游戏

假设我们有一个从1到n的排序整数列表。从左到右结束，我们必须删除第一个数字，然后再删除其他所有数字，直到到达列表的末尾。我们将再次重复上一步，但是这次从右到左，从剩余数字中删除最右边的数字和其他所有数字。我们将再次重复这些步骤，从左到右，从右到左，直到剩下一个数字为止。我们必须找到最后一个以长度为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

• 左：=左的倒数

• 雷姆：=雷姆/ 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