Reduce the array to a single element with the given operation
Given an integer N and an array arr containing integers from 1 to N in a sorted fashion. The task is to reduce the array to a single element by performing the following operation:
All the elements in the odd positions will be removed after a single operation. This operation will be performed until only a single element is left int the array and it prints that element at the end.
Examples:
Input: N = 3
Output: 2
Initially the array will be arr[] = {1, 2, 3}
After the 1st operation, ‘1’ and ‘3’ will be removed and the array becomes arr[] = {2}
So 2 is the only element left at the end.Input: N = 6
Output: 4
arr[] = {1, 2, 3, 4, 5, 6}
After the first iteration, the array becomes {2, 4, 6}
After the second iteration, the array becomes {4}
So 4 is the last element.
Approach: For this kind of problem:
- Write multiple test cases and the respective output.
- Analyze the output for the given input and the relation between them.
- Once we find the relation we will try to express it in the form of a mathematical expression if possible.
- Write the code/algorithm for the above expression.
So let’s create a table for the given input N and its respective output.
Input(N) | Output |
---|---|
3 | 2 |
4 | 4 |
6 | 4 |
8 | 8 |
12 | 8 |
20 | 16 |
Analyzed Relation: The output is at 2i. Using the above table, we can create the output table for the range of inputs.
Input(N) | Output |
---|---|
2-3 | 2 |
4-7 | 4 |
8-15 | 8 |
16-31 | 16 |
32-63 | 32 |
2i – 2i + 1 – 1 | 2i |
Below is the implementation of the above approach:
C++
// C++ implementation of the approach #include<bits/stdc++.h> using namespace std; // Function to return the final element long getFinalElement( long n) { long finalNum; for (finalNum = 2; finalNum * 2 <= n; finalNum *= 2) ; return finalNum; } // Driver code int main() { int N = 12; cout << getFinalElement(N) ; return 0; } // This code is contributed by Ryuga |
Java
// Java implementation of the approach class OddPosition { // Function to return the final element public static long getFinalElement( long n) { long finalNum; for (finalNum = 2 ; finalNum * 2 <= n; finalNum *= 2 ) ; return finalNum; } // Driver code public static void main(String[] args) { int N = 12 ; System.out.println(getFinalElement(N)); } } |
Python3
# Python 3 implementation of the approach # Function to return the final element def getFinalElement(n): finalNum = 2 while finalNum * 2 < = n: finalNum * = 2 return finalNum # Driver code if __name__ = = "__main__" : N = 12 print ( getFinalElement(N)) # This code is contributed # by ChitraNayal |
C#
// C# implementation of the approach using System; public class GFG{ // Function to return the final element public static long getFinalElement( long n) { long finalNum; for (finalNum = 2; finalNum * 2 <= n; finalNum *= 2) ; return finalNum; } // Driver code static public void Main (){ int N = 12; Console.WriteLine(getFinalElement(N)); } } |
PHP
<?php //PHP implementation of the approach // Function to return the final element function getFinalElement( $n ) { $finalNum =0; for ( $finalNum = 2; ( $finalNum * 2) <= $n ; $finalNum *= 2) ; return $finalNum ; } // Driver code $N = 12; echo getFinalElement( $N ) ; // This code is contributed by akt_mit ?> |
Javascript
<script> // Javascript implementation of the approach // Function to return the final element function getFinalElement(n) { let finalNum; for (finalNum = 2; finalNum * 2 <= n; finalNum *= 2) ; return finalNum; } // Driver code let N = 12; document.write(getFinalElement(N)); // This code is contributed by avanitrachhadiya2155 </script> |
8
Time Complexity: O(logN), since every time the finalNum value is becoming twice its current value.
Auxiliary Space: O(1), since no extra space has been taken.
Contact Us