Question Name:PERMUTATION OF FIRST N NATURAL NUMBERS

#include<iostream>
using namespace std;
int main()
{
int t,n,k;
{
cin>>n>>k;
int a[n+1],pos[n+1];
for(int i=1;i<=n;i++)
{
cin>>a[i];
pos[a[i]]=i; 
}
for(int i=1;i<=n;i++)
{
if(!k) 
break;
else
{
if(a[i]!=n-i+1)
{
k--;
int temp = a[i];
a[i] = n-i+1;
a[pos[n-i+1]] = temp;
pos[temp] = pos[n-i+1]; 
pos[n-i+1] = i;
}
}
}
for(int i=1;i<=n;i++) 
cout<<a[i]<<" ";
  return 0;
}

}
  • Problem Description
    You are given an array of N integers which is a permutation of the first N natural numbers. You can swap any two elements of the array. You can make at most K swaps. What is the largest permutation, in numerical order, you can make? 

    Input Format:

    The first line of the input contains two integers, N and K, the size of the input array and the maximum swaps you can make, respectively. The second line of the input contains a permutation of the first N natural numbers.

    Output Format:

    Print the lexicographically largest permutation you can make with at most K swaps.

    Constraints 
    1 <= N <= 10^5 
    1 <= K <= 10^9
  • Test Case 1
    Input (stdin)5 1
    4 2 3 5 1
    Expected Output5 2 3 4 1
  • Test Case 2
    Input (stdin)3 1
    2 1 3
    Expected Output3 1 2

Leave a Reply

Your email address will not be published. Required fields are marked *

Ads Blocker Image Powered by Code Help Pro

Ads Blocker Detected!!!

We have detected that you are using extensions to block ads. Please support us by disabling these ads blocker.