# 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 = 3Output: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 = 6Output: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 **2 ^{i}**. 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 |

2^{i} – 2^{i + 1} – 1 | 2^{i} |

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>` ` ` |

**Output:**

8

**Time Complexity:** O(logN) **Auxiliary Space: **O(1)