Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
1.1.
Examples
2.
Approach 1
2.1.
Idea 
2.2.
C++
2.3.
Output 
3.
Complexity Analysis
3.1.
Time complexity: O(N2 * log N)
3.2.
Space Complexity: O(N)
4.
Better Approach
4.1.
Idea: 
4.2.
C++
4.3.
Output: 
5.
Complexity Analysis
5.1.
Time Complexity: O(N)
5.2.
Space Complexity: O(N) 
6.
FAQs
7.
Key takeaways
Last Updated: Mar 27, 2024

The last remaining element after repeated removal of odd and even indexed elements alternately

Author Ayush Prakash
1 upvote
Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @

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:

  1. Remove all the odd-indexed elements(1,3,5, …) from the sequence.
  2. 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

5

Output 

2

Explanation: 

  1. Given N = 5, elements are [1,2,3,4,5].
  2. After removing all the odd-indexed elements, we get: [2,4].
  3. After removing all the even-indexed elements, we get: [2].
  4. Therefore, the last remaining element is 2.

 

Input

8

Output

6

Explanation: 

  1. Given N = 8, elements are [1,2,3,4,5,6,7,8].
  2. After removing all the odd-indexed elements, we get: [2,4,6,8].
  3. After removing all the even-indexed elements, we get: [2,6].
  4. After removing all the odd-indexed elements, we get: [6].
  5. 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;
}

Output 

The last remaining element is 2
Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Complexity Analysis

Time complexity: O(N* log N)

we're eliminating half of the elements at a time, it'll take logN steps to get to an array with one element left. Every step involves traversing the array and removing odd or even indexed elements. Traversing takes O(N) time while removing takes O(N) time. Therefore a total of O(N* log N) time is required.

Space Complexity: O(N)

It is the space required to store the elements in the array.

Better Approach

Idea

The idea is to use Dynamic Programming to improve time complexity.

Initialize a dp array where dp[i] stores the last remaining element with the sequence [1,2,...,i]. Use the following dp state transition relation:

dp[i] = 2 * ( 1 + i/2 - dp[i/2] )

where i belong to [1,2,..N].

At every step, we eliminate half of the elements. If the number of elements is i, then after one step, we will have i/2 number of elements. If we have precomputed dp[i/2], we save many redundant calculations. Hence using dynamic programming, we can reduce the overall time complexity. 

Answer will be dp[n] as dp[n] stores the last remaining element with the sequence [1,2,...,N].

C++

#include <bits/stdc++.h>
using namespace std;

// function to find the last element.
int findLastElement( int n ){    

 
    // dp vector.
    vector<int> dp(n + 1, -1);

    // Base Condition.
    if( n == 1)
        return 1;

    dp[1] = 1;
    
    // looping over the numbers.
    for(int i = 2; i <= n ; i++){

 
        // using dp relation to calculate dp[i].
        dp[i] = 2* (1 + i / 2 - dp[i / 2]);
    } 

    return dp[n];
}

int main()
{
    int N = 8;
    int ans = findLastElement(N);
    cout << "The last remaining element is " << ans;
}

Output: 

The Last remaining element is 6

Complexity Analysis

Time Complexity: O(N)

We are running a loop from i = 1 to N and calculating dp[i] in constant time using the relation: dp[i] = 2 * ( 1 + i/2 - dp[i/2] ). We have already discussed how we reach to this relation in previous sections. 

Space Complexity: O(N) 

As we are using extra space for dp array of size n.

Check out this problem - First And Last Occurrences Of X

FAQs

  1. Can this problem be solved in less than O(N) time? 
    Yes, try to develop a mathematical relation, and you can solve it in O(1) time.
     
  2. When do we use Dynamic programming?
    Dynamic programming is a general problem-solving technique that involves breaking problems down into smaller, overlapping subproblems, storing the solutions computed from the sub-problems, and reusing those results on bigger chunks of the problem.

Key takeaways

In this article, we solved a DP programming problem where we have to find the last element after repeatedly removing odd and even indexed elements alternately. 

We solved it using two approaches, where approach 1 was a basic naive approach and took O(N* log N) time. In approach 2, we optimised our solution using DP and solved it in O(N) time complexity.

Remember, always try to find the time and space complexity of your solutions because you will be asked to find the complexities of your solutions in your interviews. If you love solving coding problems, please visit this incredible platform Coding Ninjas Studio.

If you feel that this blog has helped you in any way, then please do share it with your friends. 

Happy Coding!

Previous article
Rod Cutting Problem
Next article
House Robber
Live masterclass