New update is available. Click here to update.

Last Updated: 24 Dec, 2020

Easy

```
INPUT : ARR [ ] = [ 1 , 2 , 3 , 4 , 5 ] , N = 4
OUTPUT: ARR [ ] = [ 1 , 2 , 4, 5 ]
The above example contains an odd number of elements, hence the middle element is clearly the (N+1) / 2th element, which is removed from the stack in the output.
INPUT : ARR [ ] = [ 5, 6, 7, 8 ] , N = 3
OUTPUT: ARR [ ] = [ 5, 7, 8 ]
The above example contains an even number of elements, so out of the two middle elements, we consider the one which occurs first. Hence, the middle element would be ((N+1) / 2 - 1) element, which is 6 and is removed from the stack in the output.
```

```
The first line of input contains an integer 'T' representing the number of the test case. Then the test case follows.
The first line of each test case contains an integer 'N', where 'N+1' denotes the number of elements in the stack initially.
The second line of each test case contains 'N+1' space-separated integers, denoting the elements of the stack.
```

```
For every test case, print 'N' space-separated integer, denoting the elements in the stack after removing the middle element from the input stack.
The output of every test case will be printed in a separate line.
```

```
You donβt have to print anything, it has already been taken care of. Just implement the given function.
```

```
1 <= T <= 100
1 <= N+1 <= 3000
0 <= data <= 10^9
Where βTβ is the number of test cases, βN+1β is the number of elements in the input Stack. βdataβ is the value of each element in the stack.
Time limit: 1 second
```

Approaches

The idea is to use recursive calls. We first remove all items one by one, then we recur. After recursive calls, we push all items back except for the middle item.

- We have an input stack as βINPUTSTACKβ, βNβ denotes the number of elements in the stack.
- We define a function "DELETEMIDDLE" that accepts, a stack of integers "STACK" and an integer βCOUNTβ (initially 0) as input parameters.
- Now we define the base condition. If the stack is empty or, if all the elements are traversed (COUNT == N), we return.
- Now we create a new integer variable, say βTOPβ, and we store the top of the "STACK" in "TOP", simultaneously pop out the top element of the stack.
- Call the recursive function βDELETEMIDDLEβ by incrementing the value of "COUNT" by 1.
- Add "TOP" back to βSTACKβ, if COUNT != N / 2.
- At the end of recursive calls, our stack will contain βN - 1β elements, after removing the middle element of the input stack.

Algorithm:

- Initialise βDELETEMIDDLE"( STACK, N, COUNT = 0)
- IF "STACK" is empty OR βCOUNTβ is equal to βNβ:
- Return

- If βTOPβ is equal to the top element of "STACK"
- Pop the top element of "STACK"
- Recursively call βDELETEMIDDLEβ( STACK, N, COUNT+1 )
- STACK.push(TOP) if COUNT != N / 2

- We have the given input stack, with the name "INPUTSTACK" with 'N' integers.
- Maintain a new temporary stack, say βTEMPSTACKβ and a counter variable βCOUNTβ, and initialize it with 0. "COUNT" variable will help us to find the middle element of the stack. When "COUNT" is equal to βN / 2β, it means we have arrived at the middle element of the stack.
- Now while the value of βCOUNTβ is less than βN / 2β, push the top of "INPUTSTACK" into the βTEMPSTACKβ. Simultaneously pop the top element out of the "INPUTSTACK".
- Before the end of every iteration, increment the βCOUNTβ variable by 1.
- When the "COUNT" is equal to "N / 2", and we are out of the loop, pop the top element out from the βINPUTSTACKβ. This element is the middle element of the stack.
- Now we have to add the stored elements back into the βINPUTSTACKβ.
- While βTEMPSTACKβ is not empty, push the top of "TEMPSTACK" into INPUTSTACK. Simultaneously pop out the top of βTEMPSTACKβ.
- Now our βINPUTSTACKβ contains "N - 1" integers, and the middle element is removed.

Algorithm :

- Initialise a variable COUNT = 0
- Until "COUNT" is less than N / 2:
- push top element of βINPUTSTACKβ in βTEMPSTACKβ.
- pop() the top element of "INPUTSTACK"
- Increment "COUNT" by 1.

- pop() the top element of βINPUTSTACKβ to remove the middle element.
- Until βTEMPSTACKβ is not empty:
- push top element of βTEMPSTACKβ into βINPUTSTACKβ.
- pop() the top element of "TEMPSTACK".

Similar problems

Mario And His Princess

Moderate

Posted: 12 May, 2022

Stock Span

Moderate

Posted: 16 Jun, 2022

Hills and Soldier

Moderate

Posted: 7 Jul, 2022

Hills and Soldier

Moderate

Posted: 7 Jul, 2022

Hills and Soldier

Moderate

Posted: 7 Jul, 2022

Next Greater Element II

Moderate

Posted: 9 Sep, 2022

8-Queen Problem

Easy

Posted: 19 Dec, 2022