Last Updated: 25 Nov, 2021

Alice And The Game Of Coins

Moderate

Asked in companies

Solve now

Problem statement

Alice and Bob are playing a game on coins; there are 'N' coins placed along an imaginary X-axis, and Bob asks Alice to solve the following problem.

A coin is special if it is on one of the ends of the coin stream. In one move, a person can move any special coin to make it not special. And after movement, according to its updated position, it should not be a special coin again. If there is no possible move, the game will be stopped.

Alice has to tell Bob the maximum, and a minimum number of coins can be moved.

Your task is to help Alice to find the minimum and maximum number of coins that can be moved.

EXAMPLE:

Input: 'N' = 3, 'COINS' = [8, 5, 10]
Output: Maximum = 2, Minimum = 1

Alice can move 5 -> 9 for one move, and then the game will be stopped.
Also, she can move 10 -> 6, 5 -> 7 for two moves, and then the game will be stopped.

Input Format :

The first line of input contains an integer ‘T', denoting the number of test cases. 

For each test case, the first line contains an integer 'N' denoting that number of coins placed. And next line contains 'N' integers denoting the position of every coin on the X-axis.

Output format :

For each test case, print two integers maximum and minimum number of coins can be moved.

Output for each test case will be printed in a separate line.

Note :

You don’t need to print anything. It has already been taken care of. Just implement the given function.

Constraints :

1 <= 'T' <= 10
1 <= 'N' <= 10^4
1 <= ‘COINS[i]’ <= 10^5
All values of ‘COINS[i]’ will be unique

Time Limit: 1 sec

Solve now

Approaches

01 Approach

Approach: We will use the sliding window technique to solve this problem.

To find maximum moves, we will start moving from one of the end coins. This consumes one move, and after that, we will calculate the number of free spaces available, and then we will go through these spaces one by one.

To find maximum move by using a sliding window. We will consider sliding a window of size <=n, which has a maximum number of coins in it. Minimum moves will then be equal to n - number of stones already in the max sliding window.

Algorithm :

Sort the array 'coins'.
Declare the variables 'start', 'end', 'maxMoves', and 'minMoves'.
Run a while loop till 'end' < ‘N’:
Initialize the variable 'windowSize' with 'coins[end]' - 'coins[start]' + 1.
Initialize the variable 'coinCount' with 'end' - 'start' + 1.
If 'windowSize' > ‘N’ then increment 'start' by 1 and continue with the loop.
If 'windowSize == N - 1' and 'coinCount == N - 1' then update 'minMoves' by 'minMoves= min(minMoves, 2)'
Else update 'minMoves' with minimum of ‘minMoves’ and ‘N’ - 'coinCount'.
Increment 'end' by 1.
Return {maxMoves, minMoves} at the end.

Solve now