Find last element after deleting every second element in array of n integers
Given a circular array of size n containing integers from 1 to n. Find the last element that would remain in the list after erasing every second element starting from the first element.
Example:
Input: 5 Output: 3 Explanation Element in circular array are: 1 2 3 4 5 Starting from first element i.e, '1' delete every second element like this, 1 0 3 4 5 1 0 3 0 5 0 0 3 0 5 0 0 3 0 0 For demonstration purpose erased element would be treated as '0'. Thus at the end of list, the last element remains is 3. Input: 10 Output: 5
The Naive approach is to remove every second element from the array until the size of the array becomes equals to ‘1’. The time complexity of this approach is O(n2) which would not be feasible for a large value of ‘n’.
The Efficient approach is to use recursion. Let’s consider n to be even. In one traversal, numbers 2, 4, 6 … N will be removed and we start again from 1. Thus, exactly n/2 numbers are removed, and we start as if from 1 in an array of N/2 containing only odd digits 1, 3, 5, … n/2.
Thus, by this intuition, their recursive formula can be written as,
If n is even: solve(n) = 2 * solve(n/2) - 1 else solve(n) = 2 * solve((n-1) / 2) + 1 Base condition would occur when n = 1, then answer would be 1.
Implementation:
C++
// C++ program return last number // after removing every second // element from circular array #include<iostream> using namespace std; // Utility function to return last // number after removing element int removeAlternate( int n) { if (n == 1) return 1; if (n % 2 == 0) return 2 * removeAlternate(n / 2) - 1; else return 2 * removeAlternate(((n - 1) / 2)) + 1; } // Driver code int main() { int n = 5; cout << removeAlternate(n) << "\n" ; n = 10; cout << removeAlternate(n) << "\n" ; return 0; } |
Java
// Java program return // last number after // removing every second // element from circular // array import java.util.*; class Circular { // Utility function to // return last number // number after removing // element public static int removeAlternate( int n) { if (n == 1 ) return 1 ; if (n % 2 == 0 ) return 2 * removeAlternate(n / 2 ) - 1 ; else return 2 * removeAlternate(((n - 1 ) / 2 )) + 1 ; } // Driver Code public static void main(String[] args) { int n = 5 ; System.out.print(removeAlternate(n)); n = 10 ; System.out.print( "\n" + removeAlternate(n)); } } // This code is contributed by rishabh_jain |
Python3
# Python program return last number # after removing every second # element from circular array # Utility function to return last # number after removing element def removeAlternate(n): if (n = = 1 ): return 1 if (n % 2 = = 0 ): return 2 * removeAlternate(n / 2 ) - 1 else : return 2 * removeAlternate(((n - 1 ) / 2 )) + 1 # Driver code n = 5 print (removeAlternate(n)) n = 10 print (removeAlternate(n)) # This code is contributed by Smitha Dinesh Semwal |
C#
// C# program return last number after // removing every second element from // circular array using System; class Circular { // Utility function to return last number // number after removing element public static int removeAlternate( int n) { if (n == 1) return 1; if (n % 2 == 0) return 2 * removeAlternate(n / 2) - 1; else return 2 * removeAlternate(((n - 1) / 2)) + 1; } // Driver Code public static void Main() { int n = 5; Console.WriteLine(removeAlternate(n)); n = 10; Console.WriteLine(removeAlternate(n)); } } // This code is contributed by vt_m |
PHP
<?php // PHP program return last number // after removing every second // element from circular array // Utility function to return last // number after removing element function removeAlternate( $n ) { if ( $n == 1) return 1; if ( $n % 2 == 0) return 2 * removeAlternate( $n / 2) - 1; else return 2 * removeAlternate((( $n - 1) / 2)) + 1; } // Driver code $n = 5; echo removeAlternate( $n ) , "\n" ; $n = 10; echo removeAlternate( $n ) , "\n" ; // This code is contributed by ajit ?> |
Javascript
<script> //Javascript program return last number // after removing every second // element from circular array // Utility function to return last // number after removing element function removeAlternate(n) { if (n == 1) return 1; if (n % 2 == 0) return 2 * removeAlternate(n / 2) - 1; else return 2 * removeAlternate(((n - 1) / 2)) + 1; } // Driver code let n = 5; document.write(removeAlternate(n) + "<br>" ); n = 10; document.write(removeAlternate(n) + "<br>" ); // This code is contributed by Mayank Tyagi </script> |
3 5
Time complexity: O(log(n))
Auxiliary space: O(1)
Most Another Approach:
Another approach is by observing the pattern in which the numbers repeat. I observed that the output were all odd numbers incremented by 2 every time the n value increased by one and the value got reset to ‘1’ at the powers of 2.
For example, The outputs were 1 1 3 1 3 5 7 1 3 5 7 9 11 13 15 1 respectively for the value of n ranging from 1 to 16.
Hence this approach uses the closest value of the power of 2 less than or equal to the given input.
Implementation:
C++
#include <iostream> #include<bits/stdc++.h> using namespace std; // find the value nearest // to power of 2 int nearestPowerof2( int n) { int p = ( int )log2(n); return p; } // eliminate n int circularElimination( int n) { // power of 2 int power=nearestPowerof2(n); int result=1+2*(n- pow (2,power)); return result; } // Driver Code int main() { int n=5; // Function call int result=circularElimination(n); cout<<result<< "\n" ; n=10; result=circularElimination(n); cout<<result<< "\n" ; return 0; } |
Java
import java.io.*; class GFG { // find the power of 2 static int highestPowerof2( int n) { int p = ( int )(Math.log(n) / Math.log( 2 )); return p; } // eliminate the element n static int circularElimination( int n) { // power of 2 int power = highestPowerof2(n); int res = 1 + 2 * ( int )(n - Math.pow( 2 , power)); return res; } // Driver Code public static void main(String[] args) { int n = 5 ; // Function call System.out.println(circularElimination(n)); n = 10 ; System.out.println(circularElimination(n)); } } |
Python3
# Find the value nearest # to power of 2 import math def nearestPowerof2(n): p = int (math.log2(n)) return p # Eliminate n def circularElimination(n): # power of 2 power = nearestPowerof2(n); result = ( 1 + 2 * (n - pow ( 2 ,power))) return result n = 5 # Driver code # Function call result = circularElimination(n) print (result) n = 10 result = circularElimination(n) print (result) # This code is contributed by divyeshrabadiya07 |
C#
using System; class GFG{ // Find the power of 2 static int highestPowerof2( int n) { int p = ( int )(Math.Log(n) / Math.Log(2)); return p; } // Eliminate the element n static int circularElimination( int n) { // Power of 2 int power = highestPowerof2(n); int res = 1 + 2 * ( int )( n - Math.Pow(2, power)); return res; } // Driver Code public static void Main( string [] args) { int n = 5; // Function call Console.WriteLine(circularElimination(n)); n = 10; Console.WriteLine(circularElimination(n)); } } // This code is contributed by shivanisinghss2110 |
Javascript
<script> // Find the power of 2 function highestPowerof2(n) { let p = parseInt(Math.log(n) / Math.log(2), 10); return p; } // Eliminate the element n function circularElimination(n) { // Power of 2 let power = highestPowerof2(n); let res = 1 + 2 * (n - Math.pow(2, power)); return res; } let n = 5; // Function call document.write(circularElimination(n) + "</br>" ); n = 10; document.write(circularElimination(n)); </script> |
3 5
Time Complexity: O(1)
Space Complexity: O(1)
Contact Us