Introduction
Given a positive integer N, print the last remaining element from the sequence [1, N] by performing the following operations alternately in the given order:
- Remove all the odd-indexed elements(1,3,5, …) from the sequence.
- Remove all the even-indexed elements(2,4,6, …) from the sequence.
Input: An integer N
Output: An integer representing the last remaining element.
Examples
Input
5Output
2Explanation:
- Given N = 5, elements are [1,2,3,4,5].
- After removing all the odd-indexed elements, we get: [2,4].
- After removing all the even-indexed elements, we get: [2].
- Therefore, the last remaining element is 2.
Input
8Output
6Explanation:
- Given N = 8, elements are [1,2,3,4,5,6,7,8].
- After removing all the odd-indexed elements, we get: [2,4,6,8].
- After removing all the even-indexed elements, we get: [2,6].
- After removing all the odd-indexed elements, we get: [6].
- Therefore, the last remaining element is 6.
Approach 1
Idea
The naive approach would be to maintain two arrays to store the remaining elements after the alternative removal of elements. Remove elements from one array as needed and add the remaining elements to the other array. Repeat this until only one element is left.
C++
#include <bits/stdc++.h>
using namespace std;
// Function to find the last element.
int findLastElement(int n) {
// Vectors to store the array elements.
vector<int> arr1;
vector<int> arr2;
for(int i = 1; i <= n ; i++)
arr1.push_back(i);
bool odd = 1;
while(1){
// To remove odd indexed elements.
if( odd){
for(int i = 1; i < arr1.size() ; i+=2)
arr2.push_back(arr1[i]);
arr1.clear();
if( arr2.size() == 1)
return arr2[0];
odd = 0;
}
// To remove even indexed elements.
else{
for(int i = 0 ; i < arr2.size() ; i+=2)
arr1.push_back(arr2[i]);
arr2.clear();
if( arr1.size() == 1)
return arr1[0];
odd = 1;
}
}
return -1;
}
int main()
{
int N = 5;
int ans = findLastElement(N);
cout << "The last remaining element is " << ans;
}
You can also try this code with Online C++ Compiler
Output
The last remaining element is 2
250+ registered 
