Alice And The Game Of Coins

Moderate
0/80
profile
Contributed by
2 upvotes
Asked in companies
FacebookUrban Company (UrbanClap)

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.
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1 :
2
3
8 5 10
5
7 6 5 4 11
Sample Output 1 :
2 1
3 2
Explanation Of Sample Input 1 :
For the first test case, 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.

For the second test case, Alice can move 4 -> 9 then 11 -> 8
And then the game will be stopped. Also, she can move 4 -> 8, 5 -> 9, 6 -> 10 for three moves, and then the game will be stopped.
Sample Input 2 :
2
3
1 2 3
5
1 2 3 6 9
Sample Output 2 :
0 0
2 4
Hint

Starting from the end coins try to use the sliding window over the number of available positions.

Approaches (1)
Sliding Window

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 :  

  1. Sort the array 'coins'.
  2. Declare the variables 'start', 'end', 'maxMoves', and 'minMoves'.
  3. 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.
  4. Return {maxMoves, minMoves} at the end.
Time Complexity

O(N * Log(N)), where 'N' is the number of coins placed on the X - axis.

 

As we are sorting the input array and it will take the N * LogN complexity hence the time complexity will be O(N * LogN)

Space Complexity

O(1)

 

As we are using constant extra memory space the space complexity will be O(1)

Code Solution
(100% EXP penalty)
Alice And The Game Of Coins
Full screen
Console