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개의 숫자가 제거됩니다. 그리고 홀수 숫자 1, 3, 5, … n/2만 포함하는 n/2의 배열에서 형식 1처럼 시작합니다. 따라서 −

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