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.

Powered By
CHP Adblock Detector Plugin | Codehelppro