Find the last remaining element after repeated removal of odd and even indexed elements alternately | C ++ 14 program for the above approach ; Function to calculate the last remaining element from the sequence ; If dp [ n ] is already calculated ; Base Case : ; Recursive call ; Return the value of dp [ n ] ; Driver Code ; Given N ; Stores the ; Function call
#include <bits/stdc++.h> NEW_LINE using namespace std ; int lastRemaining ( int n , map < int , int > & dp ) { if ( dp . find ( n ) != dp . end ( ) ) return dp [ n ] ; if ( n == 1 ) return 1 ; else dp [ n ] = 2 * ( 1 + n / 2 - lastRemaining ( n / 2 , dp ) ) ; return dp [ n ] ; } int main ( ) { int N = 5 ; map < int , int > dp ; cout << lastRemaining ( N , dp ) ; return 0 ; }