在C ++中删除n个整数数组中的第二个元素后，查找最后一个元素

考虑我们有一个圆形数组，其中包含从1到n的整数。查找删除从第一个元素开始的每个第二个元素之后将保留在列表中的最后一个元素。如果输入为5，则数组将为[1、2、3、4、5]。从1开始。删除第二个元素后，将类似于-

1 0 3 4 5
1 0 3 0 5
0 0 3 0 5
0 0 3 0 0

因此，列表中剩余的元素为3。

我们将使用递归解决此问题。假设n是偶数。数字2、4、6将被删除，然后我们将从1重新开始。这样就删除了n / 2个数字。然后，我们开始于n / 2数组中的形式1，该数组仅包含奇数1、3、5…n / 2。因此我们可以将公式写成-

solve(n)=2*solve(n/2)-1[when n is even]
solve(n)=2*solve(n-1/2)+1[when n is odd]

基本条件是solve(1)= 1。

示例

#include<iostream>
using namespace std;
int deleteSecondElement(int n) {
   if (n == 1)
      return 1;
   if (n % 2 == 0)
      return 2 * deleteSecondElement(n / 2) - 1;
   else
      return 2 * deleteSecondElement(((n - 1) / 2)) + 1;
}
int main() {
   int n = 5;
   cout << "Remaining Element: " << deleteSecondElement(n) << endl;
   n = 10;
   cout << "Remaining Element: " << deleteSecondElement(n) << endl;
}

输出结果

Remaining Element: 3
Remaining Element: 5