Minimum coins

Easy
0/40
Average time to solve is 5m
profile
Contributed by
5 upvotes
Asked in company
Amazon

Problem statement

You are given a permutation 'A' of length 'N'. You can apply the following operation any number of times which costs 1 coin for each operation.

Select any subarray of length at most 'N' - 1 and rearrange the elements in any order.

Return the minimum number of coins required to sort the permutation in increasing order.

A permutation is an array in which each element from 1 to 'N' occurs exactly once.

For Example:- 
Let 'N' = 5, 'A' = [1, 2, 3, 5, 4].
We can apply the operation to the subarray from index 4 to 5 (1-based indexing).
So our answer is 1.
Detailed explanation ( Input/output format, Notes, Images )
Input Format:- 
First-line contains an integer 'T', which denotes the number of test cases.
For every test case:-
First-line contains an integer 'N', denoting the length of the array 'A'.
Second-line contains 'N' space-separated integers, elements of array 'A'.
Output Format:- 
For each test case, Return the minimum number of coins required to sort the permutation in increasing order.
Note:- 
You don’t need to print anything. Just implement the given function.
Constraints:- 
1 <= 'T' <= 10
3 <= 'N' <= 10^5

The Sum of 'N' overall test cases does not exceed 10^5.
Time Limit: 1 sec
Sample Input 1:-
2
4
1 3 2 4
3
1 2 3
Sample Output 1:-
1
0
Explanation of sample input 1:-
First test case:-
We can apply the operation to the subarray from index 2 to 3 (1-based indexing).
So our answer is 1.

Second test case:-
The array is already sorted.
So our answer is 0.
Sample Input 2:-
2
5
5 4 3 1 2
5
3 2 1 4 5
Sample Output 2:-
2
1
Hint

Can the answer be greater than 3?

 

Approaches (1)
Ad-Hoc Approach

Approach:-

 

  • If the array is already sorted:
    • The answer is 0.
  • Otherwise, we can reduce the problem to the following 3 conditions (Assume 1 based indexing),
  • If 'A[1]' == 1 || 'A[N]' == N:
    • The answer is 1, we can select a subarray from (2 to N) or (1 to N-1) respectively.
  • If the 'A[1]' == N && 'A[N]' == 1:
    • The answer is 3, we have to first select a subarray from (1 to N-1) to take N from index 1, then we select a subarray from (2 to N) to take 1 from index N and place N to index N, then we again select subarray from (1 to N-1) to place 1 to index 1.
    • We can place other elements in their correct position in these operations itself.
  • Else:
    • The answer is 2:
      • We can select a subarray from (1 to N-1), then select a subarray from (2 to N).
      • Or, We can select a subarray from (2 to N), then select a subarray from (1 to N-1).
    • With this, we can place all elements in their correct position.

 

Algorithm:-
 

  • If the array is sorted, return 0.
  • If ('A[1]' == 1 || 'A[N]' == N):
    • Return 1.
  • Else if('A[1]' == N && 'A[N]' == 1):
    • Return 3.
  • Return 2.
Time Complexity

O(N), where 'N' is the length of 'A'.

 

We are traversing in 'A' to check whether 'A' is sorted or not and the complexity associated with this is O(N). Hence, the overall time complexity is of the order O(N).

Space Complexity

O(1).

 

We are using constant extra space, So the Space Complexity is O(1).

Code Solution
(100% EXP penalty)
Minimum coins
Full screen
Console