Find the last remaining element after repeated removal of odd and even indexed elements alternately
Given a positive integer N, the task is to print the last remaining element from a sequence [1, N] after repeatedly performing the following operations in the given order alternately:
- Remove all the odd-indexed elements from the sequence.
- Remove all the even-indexed elements from the sequence.
Examples:
Input: N = 9
Output: 6
Explanation:
Sequence = {1, 2, 3, 4, 5, 6, 7, 8, 9}
Step 1: Removing odd-indexed elements modifies sequence to {2, 4, 6, 8}
Step 2: Removing even-indexed elements modifies sequence to {2, 6}
Step 3: Removing odd-indexed elements modifies sequence to {6}
Therefore, the last remaining element is 6.Input: N = 5
Output: 2
Explanation:
Sequence = {1, 2, 3, 4, 5}
Step 1: Removing odd-indexed elements modifies sequence to {2, 4}
Step 2: Removing even-indexed elements modifies sequence to {2}
Therefore, the last remaining element is 2.
Naive Approach: The simplest approach is to store all the elements from 1 to N sequentially in an array. For every operation, remove elements from the array and shift the remaining elements towards the left. After reducing the array to a single element, print that remaining element as the required answer.
Time Complexity: O(N2*log N)
Auxiliary Space: O(N)
Efficient Approach: The above approach can be optimized using Dynamic Programming.
The recurrence relation is as follows:
where, i is in the range [1, N]
dp[i] stores the answer when the array elements are from 1 to i.
Follow the steps below to solve the problem:
- Initialize an array dp[] where dp[i] stores the remaining element or the sequence [1, i].
- For the base condition of i = 1, print 1 as the required answer.
- Calculate the value of dp[N] using the aforementioned recurrence relation and use the already computed subproblems to avoid recomputation of overlapping subproblems.
- After completing the above steps, print the value of dp[N] as the result.
Below is the implementation of the above approach:
// Java program for
// the above approach
import java.util.*;
class GFG{
// Function to calculate the last
// remaining element from the sequence
static int lastRemaining(int n, HashMap<Integer,
Integer> dp)
{
// If dp[n] is already calculated
if (dp.containsKey(n))
return dp.get(n);
// Base Case:
if (n == 1)
return 1;
// Recursive call
else
dp.put(n, 2 * (1 + n / 2 -
lastRemaining(n / 2, dp)));
// Return the value of dp[n]
return dp.get(n);
}
// Driver Code
public static void main(String[] args)
{
// Given N
int N = 5;
// Stores the
HashMap<Integer,
Integer> dp = new HashMap<Integer,
Integer>();
// Function call
System.out.print(lastRemaining(N, dp));
}
}
// This code is contributed by Princi Singh
# Python program for the above approach
# Function to calculate the last
# remaining element from the sequence
def lastRemaining(n, dp):
# If dp[n] is already calculated
if n in dp:
return dp[n]
# Base Case:
if n == 1:
return 1
# Recursive Call
else:
dp[n] = 2*(1 + n//2
- lastRemaining(n//2, dp))
# Return the value of dp[n]
return dp[n]
# Driver Code
# Given N
N = 5
# Stores the
dp = {}
# Function Call
print(lastRemaining(N, dp))
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG{
// Function to calculate the last
// remaining element from the sequence
static int lastRemaining(int n, Dictionary<int,
int> dp)
{
// If dp[n] is already calculated
if (dp.ContainsKey(n))
return dp[n];
// Base Case:
if (n == 1)
return 1;
// Recursive call
else
dp.Add(n, 2 * (1 + n / 2 -
lastRemaining(n / 2, dp)));
// Return the value of dp[n]
return dp[n];
}
// Driver Code
public static void Main(String[] args)
{
// Given N
int N = 5;
// Stores the
Dictionary<int,
int> dp = new Dictionary<int,
int>();
// Function call
Console.Write(lastRemaining(N, dp));
}
}
// This code is contributed by Princi Singh
<script>
// JavaScript program for the above approach
// Function to calculate the last
// remaining element from the sequence
function lastRemaining(n, dp) {
// If dp[n] is already calculated
if (dp.hasOwnProperty(n))
return dp[n];
// Base Case:
if (n === 1)
return 1;
// Recursive call
else
dp[n] =
2 * (1 + parseInt(n / 2) -
lastRemaining(parseInt(n / 2), dp));
// Return the value of dp[n]
return dp[n];
}
// Driver Code
// Given N
var N = 5;
// Stores the
var dp = {};
// Function call
document.write(lastRemaining(N, dp));
</script>
// C++14 program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to calculate the last
// remaining element from the sequence
int lastRemaining(int n, map<int, int> &dp)
{
// If dp[n] is already calculated
if (dp.find(n) != dp.end())
return dp[n];
// Base Case:
if (n == 1)
return 1;
// Recursive call
else
dp[n] = 2 * (1 + n / 2 -
lastRemaining(n / 2, dp));
// Return the value of dp[n]
return dp[n];
}
// Driver Code
int main()
{
// Given N
int N = 5;
// Stores the
map<int, int> dp;
// Function call
cout << lastRemaining(N, dp);
return 0;
}
// This code is contributed by mohit kumar 29
Output
2
Time Complexity: O(N), as we are using a loop to traverse N times.
Auxiliary Space: O(N), as we are using extra space for dp.
Efficient approach : Using DP Tabulation method ( Iterative approach )
The approach to solve this problem is same but DP tabulation(bottom-up) method is better then Dp + memoization(top-down) because memoization method needs extra stack space of recursion calls.
Steps to solve this problem :
- Create an array DP to store the solution of the subproblems and initialize it with 0.
- Initialize the array with base cases
- Now Iterate over subproblems to get the value of the current problem from the previous computation of subproblems stored in DP.
- Return the final solution stored in dp[n].
Implementation :
// C++14 program for the above approach using DP tabulation
#include <bits/stdc++.h>
using namespace std;
// Function to calculate the last
// remaining element from the sequence
int lastRemaining(int n)
{
// Declare and initialize the dp table
int dp[n+1] = {0};
// Base Case
dp[1] = 1;
// Fill the dp table in bottom-up manner
for(int i=2; i<=n; i++)
{
dp[i] = 2 * (1 + i / 2 - dp[i / 2]);
}
// Return the result
return dp[n];
}
// Driver Code
int main()
{
// Given N
int N = 5;
// Function call
cout << lastRemaining(N);
return 0;
}
// this code is contributed by bhardwajji
// Java program for the above approach using DP tabulation
import java.util.*;
public class Main {
// Function to calculate the last
// remaining element from the sequence
public static int lastRemaining(int n) {
// Declare and initialize the dp table
int[] dp = new int[n+1];
// Base Case
dp[1] = 1;
// Fill the dp table in bottom-up manner
for(int i=2; i<=n; i++) {
dp[i] = 2 * (1 + i / 2 - dp[i / 2]);
}
// Return the result
return dp[n];
}
// Driver Code
public static void main(String[] args) {
// Given N
int N = 5;
// Function call
System.out.println(lastRemaining(N));
}
}
# Python3 program for the above approach using DP tabulation
# Function to calculate the last
# remaining element from the sequence
def lastRemaining(n: int) -> int:
# Declare and initialize the dp table
dp = [0] * (n + 1)
# Base Case
dp[1] = 1
# Fill the dp table in bottom-up manner
for i in range(2, n + 1):
dp[i] = 2 * (1 + i // 2 - dp[i // 2])
# Return the result
return dp[n]
# Driver Code
if __name__ == '__main__':
# Given N
N = 5
# Function call
print(lastRemaining(N))
// C# program for the above approach
// using DP tabulation
using System;
class GFG {
// Function to calculate the last
// remaining element from the sequence
static int lastRemaining(int n)
{
// Declare and initialize the dp table
int[] dp = new int[n + 1];
// Base Case
dp[1] = 1;
// Fill the dp table in bottom-up manner
for (int i = 2; i <= n; i++) {
dp[i] = 2 * (1 + i / 2 - dp[i / 2]);
}
// Return the result
return dp[n];
}
// Driver Code
public static void Main()
{
// Given N
int N = 5;
// Function call
Console.WriteLine(lastRemaining(N));
}
}
// JavaScript program for the above approach using DP tabulation
// Function to calculate the last
// remaining element from the sequence
function lastRemaining(n) {
// Declare and initialize the dp table
const dp = Array(n + 1).fill(0);
// Base Case
dp[1] = 1;
// Fill the dp table in bottom-up manner
for (let i = 2; i <= n; i++) {
dp[i] = 2 * (1 + Math.floor(i / 2) - dp[Math.floor(i / 2)]);
}
// Return the result
return dp[n];
}
// Driver Code
const N = 5;
// Function call
console.log(lastRemaining(N));
Output
2
Time Complexity: O(N)
Auxiliary Space: O(N)
Another Approach: In the above approach, we can see there are logN states stored in dp map. So, Why we need to compute for 1 to N states in tabulation approach. We just need to compute those logN states to get the answer. So, compute the states first by repeatedly dividing N by 2 and collecting the states in an array. Then keep ans as 1 and start computing the collected states from the end of the array.
For Example, If we have N = 9, we have {9, 4, 2} in dp array. So, we keep ans=1 and start computing states like 2->4->9. The formula remains same. This approach can even compute answer when N is 1e9.
#include <bits/stdc++.h>
using namespace std;
// Function to calculate the last
// remaining element from the sequence
int lastRemaining(int N)
{
// DP which stores only required states
vector<int> dp;
// compute the states
// which are required
int n = N;
while(n>1){
// As the recursion was linear
// directly store the states.
dp.push_back(n);
n>>=1;
}
// As ans is 1 at beginning
// base case n==1 return 1
int ans = 1;
// Loop from next of n=1
// The dp has states like { n, n/2, n/2/2,...}
// So we need to first compute the small states
// So they are at the end of DP vector
for(int i = dp.size()-1;i>=0;i--) {
// The current N is dp[i]
int currN = dp[i];
// compute the answer for the current state
// similar to above approaches formula
// dp[n] = 2*(1+n/2 - lastRemaining(n/2))
ans = 2*(1 + (currN>>1) - ans);
}
// Last state is obviously N
// the ans has it's value
// return ans
return ans;
}
// Driver Code
int main()
{
// Given N
int N = 5;
// Function call
cout << lastRemaining(N);
return 0;
}
import java.util.ArrayList;
import java.util.List;
public class Main {
// Function to calculate the last remaining element from the sequence
public static int lastRemaining(int N) {
// List to store only required states
List<Integer> dp = new ArrayList<>();
// Compute the states which are required
int n = N;
while (n > 1) {
// As the recursion was linear
// directly store the states.
dp.add(n);
n >>= 1;
}
// As ans is 1 at beginning
// base case n==1 return 1
int ans = 1;
// Loop from next of n=1
// The dp has states like { n, n/2, n/2/2,...}
// So we need to first compute the small states
// So they are at the end of DP list
for (int i = dp.size() - 1; i >= 0; i--) {
// The current N is dp[i]
int currN = dp.get(i);
// Compute the answer for the current state
// similar to above approaches formula
// dp[n] = 2*(1+n/2 - lastRemaining(n/2))
ans = 2 * (1 + (currN >> 1) - ans);
}
// Last state is obviously N
// the ans has its value
// return ans
return ans;
}
// Driver Code
public static void main(String[] args) {
// Given N
int N = 5;
// Function call
System.out.println(lastRemaining(N));
}
}
//This code is contributed by Utkarsh.
def lastRemaining(N):
# DP which stores only required states
dp = []
# compute the states which are required
n = N
while n > 1:
# As the recursion was linear directly store the states.
dp.append(n)
n >>= 1
# As ans is 1 at beginning base case n==1 return 1
ans = 1
# Loop from next of n=1
# The dp has states like { n, n/2, n/2/2,...}
# So we need to first compute the small states
# So they are at the end of DP vector
for i in range(len(dp)-1, -1, -1):
# The current N is dp[i]
currN = dp[i]
# compute the answer for the current state
# similar to above approaches formula
# dp[n] = 2*(1+n/2 - lastRemaining(n/2))
ans = 2*(1 + (currN >> 1) - ans)
# Last state is obviously N
# the ans has its value
# return ans
return ans
# Driver Code
if __name__ == "__main__":
# Given N
N = 5
# Function call
print(lastRemaining(N))
#THis cOde is contributed by Utkarsh
function lastRemaining(N) {
// Array to store required states
let dp = [];
// Compute the required states
let n = N;
while (n > 1) {
// As the recursion was linear, directly store the states
dp.push(n);
n >>= 1; // Right shift by 1 (equivalent to dividing by 2)
}
// Initialize answer as 1
let ans = 1;
// Loop through the stored states in reverse order
// The dp has states like { n, n/2, n/2/2,...}
// So we need to first compute the small states
// So they are at the end of DP array
for (let i = dp.length - 1; i >= 0; i--) {
// The current N is dp[i]
let currN = dp[i];
// Compute the answer for the current state
// Similar to above approach's formula
// dp[n] = 2*(1+n/2 - lastRemaining(n/2))
ans = 2 * (1 + (currN >> 1) - ans);
}
// Last state is obviously N
// The answer has its value
return ans;
}
// Driver Code
let N = 5;
console.log(lastRemaining(N));
Output
2
Time Complexity: O(logN + logN)
Auxiliary Space: O(logN)
Contact Us