The kth Permutation

Easy
0/40
profile
Contributed by
1 upvote

Problem statement

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.
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1 :
2
5
1 5 2 3 4
3
1 2 3
Sample Output 1 :
2
3
Explanation For Sample Output 1 :
In the first test case, there are two indexes, 1 and 5, such that the subarray (1, 1) and (1, 5) have all the ‘k’ numbers.

In the second test case, as the array is already sorted so every index will give a subarray having all the values between 1 to k. Hence the answer is 3.
Sample Input 2 :
2
4
4 3 2 1
4
4 1 2 3
Sample Output 2 :
1
1
Hint

Check for every index from 1 to ‘N’, and for the current index ‘i’, check if the first ‘i’ values are present or not.

Approaches (2)
Brute Force Approach

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:

  1. Take an array ‘check’ of size ‘N’ and initialize it with zero.
  2. Take an integer ‘answer’ to store the final ‘answer’.
  3. 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.
  4. Return ‘answer’
Time Complexity

O(N ^ 2). Where N is the total number of elements in the array ‘ARR’.

 

We are iterating through all the integers from 1 to ‘N’ and for every element in the first iteration, we are iterating through 1 to the current index.

Hence, the time complexity is O(N ^ 2).

Space Complexity

O( N ).


Since we are taking an array ‘check’ of size ‘N’. 

Hence the space complexity is O(N).

Code Solution
(100% EXP penalty)
The kth Permutation
Full screen
Console