Given a Non-Negative integer N, denoting the first 2N positive integers where consecutive integers starting from 1 are paired with each other, the task is to find the last number remaining after performing the following operations:
- Consider a pair (x, y) of two consecutive integers which are not yet deleted from the 2N integers.
- If the sum of two integers x + y is even then delete x (the minimum one).
- If the sum of two integers x + y is odd then delete y (the maximum one).
Examples:
Input: N = 2
Output: 3
Explanation:
For N = 2 we have 2^N i.e; 4 integers and 4/2 pairs which are as follows-:
(1, 2), (3, 4)
Now after performing the operations:
1 + 2 = 3 which is odd, delete y. So remains 1.
3 + 4 = 7 which is odd, delete y. So remains 3
Now the remaining numbers are 1 and 3 and the pair is (1, 3).
Sum = 1 + 3 = 4 which is even, so delete 1.
So the last remaining element is 3.Input: N = 3
Output: 7
Explanation:
For N = 2 we have 2^N i.e; 8 integers and 8/2 pairs which are as follows-:
(1, 2), (3, 4), (5, 6) and (7, 8)
Now after performing the operations:
1 + 2 = 3 which is odd, delete y. So remains 1.
3 + 4 = 7 which is odd, delete y. So remains 3.
5 + 6 = 11 which is odd, delete y. So remains 5.
7 + 8 = 15 which is odd, delete y. So remains 7.
Now the remaining numbers are 1, 3, 5 and 7 and the pairs are (1, 3), (5, 7).
1 + 3 = 4 which is even, delete x. So remains 3.
5 + 7 = 12 which is even, delete x. So remains 7.
Now the remaining numbers are 3 and 7 and the pair is (3, 7)
3 + 7 = 10 which is even, so delete 3.
So the last remaining element is 7.
Approach: The given problem can be solved using the below mathematical observation:
- The idea is to consider when the sum is odd or even while adding two numbers.
- If we add one even and one odd number then sum will always be an odd number
- If we add two odd numbers or two even numbers then sum will always be an even number.
Based on the above observation the solution for the problem can be derived as follows:
- For the first time, each pair has an odd number and an even number where the even number is the greater one. So the sum is always odd and the even number gets deleted.
- In the next steps, remaining numbers are all odd so the sum of pairs will always be even. Therefore the alternative odd numbers starting from the first (smaller one) get removed in each step.
- From the above observation clearly, the maximum among all odd numbers will be the last remaining one i.e. 2N -1
Below is the implementation of the above approach:
C++
// C++ program to implement the approach#include <bits/stdc++.h>using namespace std;// Function to calculate// the last remaining numberlong long int lastdigit(int N){ // 1<<n is 2^n long long int ans = (1 << N) - 1; return ans;}// Driver codeint main(){ int N = 3; // Function call cout << lastdigit(N) << endl; return 0;} |
Java
// Java program to implement the approachimport java.io.*;class GFG {// Function to calculate// the last remaining numberstatic long lastdigit(int N){ // 1<<n is 2^n long ans = (1 << N) - 1; return ans;}// Driver code public static void main (String[] args) { int N = 3; // Function call System.out.println(lastdigit(N)); }}// This code is contributed by hrithikgarg03188. |
Python3
# Python3 code for the above approach# Function to calculate# the last remaining numberdef lastdigit(N): # 1<<n is 2^n ans = (1 << N) - 1 return ans# Driver codeN = 3# function callprint(lastdigit(N))# This code is contributed by phasing17 |
C#
// C# program to implement the approachusing System;public class GFG{// Function to calculate// the last remaining numberstatic long lastdigit(int N){ // 1<<n is 2^n long ans = (1 << N) - 1; return ans;}// Driver code static public void Main (){ int N = 3; // Function call Console.Write(lastdigit(N)); }} |
Javascript
<script> // JavaScript code for the above approach// Function to calculate// the last remaining numberfunction lastdigit(N){ // 1<<n is 2^n let ans = (1 << N) - 1; return ans;} // Driver code let N = 3; // Function call document.write(lastdigit(N));// This code is contributed by sanjoy_62.</script> |
7
Time Complexity: O(1)
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
