Last Updated: 23 Oct, 2021
The kth Permutation
Easy
You are given a permutation of ‘N’ integers from 1 to ‘N’. You have to count the number of index ‘k’ such that on sorting these first ‘k’ indexes, you will get a subarray of ‘k’ integers having values from 1 to ‘k’.
For Example :
‘N’ = 5, ‘ARR’ = {3, 1, 2, 4, 5}.
Now in this example, There are three indexes 3, 4, 5(indexing starting from 1):
Sorted subarray(1, 3): 1, 2, 3.
Sorted subarray(1, 4): 1, 2, 3, 4.
Sorted subarray(1, 5): 1, 2, 3, 5.
Hence the answer is 3.
Input Format :
The first line of input format contains ‘T’, denoting the number of test cases. Then each test case follows.
The first line of each test case contains an integer ‘N’, denoting the number of elements in the array.
The second line of the test case contains an array of ‘N’ integers denoting the array ‘ARR’.
Output Format :
For each test case, print a single integer denoting the total number of index ‘k’.
Output for every query will be printed in a separate line.
Note :
You are not required to print anything explicitly. It has already been taken care of. Just implement the functions.
Constraints :
1 <= T <= 10
1 <= ‘N’ <= 1000
1 <= ‘ARR[i]’ <= N
Time Limit: 1 second
Approaches
The approach is simple brute force, Take an array ‘check’ of size ‘N’ and iterate through all the elements from 1 to ‘N’ and update the number at ‘i’th index as one, and for the current index, iterate through the array ‘check’ and check if all the elements from 1 to ‘i’ are updated to one or not.
The steps are as follows:
- Take an array ‘check’ of size ‘N’ and initialize it with zero.
- Take an integer ‘answer’ to store the final ‘answer’.
- Iterate through the loop from 1 to ‘N’(say iterator be i):
- For the current index ‘i’, update the value of ‘check[ARR[i - 1]]’ = 1.
- Now iterate through the array check from 1 to ‘i’(say iterator be j):
- If every value at ‘check[j]’ equals 1, then Increment ‘answer’ by 1.
- Return ‘answer’
So according to the problem, we will increment the counter only when we encounter all the elements from 1 to ‘i’, which means that there will be no element that is remaining. This is really simple to check, we will only check if the largest element we obtained is equal to ‘i’ or not. As the largest element is equal to ‘i’ that means we have ‘i’ elements and all the elements are less than or equal to ‘i’. As all the elements are unique that means there is no element that remains from 1 to ‘i’.
The steps are as follows:
- Take two integers ‘high’ and ‘answer’ in which we will store the largest element and the final answer.
- Iterate through the loop from 1 to ‘N’(say iterator be i):
- Update ‘high’ as max of ‘high’ and ARR[i - 1].
- Check if ‘high’ equals ‘i’:
- Increment ‘answer’ by 1.
- Return answer.
Similar problems