In this HackerRank Largest Permutation problem solution, You are given an unordered array of unique integers incrementing from 1. You can swap any two elements a limited number of times. Determine the largest lexicographical value array that can be created by executing no more than the limited number of swaps.
Problem solution in Python.
#!/usr/bin/env python import sys if __name__ == '__main__': N, K = list(map(int, sys.stdin.readline().split())) A = list(map(int, sys.stdin.readline().split())) if K >= N - 1: print(*sorted(A, reverse = True), sep = ' ') else: X = sorted(A) i, swaps = 0, 0 while swaps < K: x = X.pop() if A[i] != x: A[A.index(x)] = A[i] A[i] = x swaps += 1 i += 1 print(*A, sep = ' ')
Problem solution in Java.
import java.io.*; import java.util.*; public class Solution { static void swap(int[]a ,int ind1, int ind2){ int tmp = a[ind1]; a[ind1]=a[ind2]; a[ind2]=tmp; } static int find(int[]a,int ind1,int ind2){ int max=0; int maxV = Integer.MIN_VALUE; for(int i=ind1;i<=ind2;i++){ if(a[i]>maxV){ maxV=a[i]; max=i; } } return max; } public static void main(String[] args) { /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */ Scanner in = new Scanner(System.in); int N=in.nextInt(); int K=in.nextInt(); int[]a=new int[N]; for(int i=0;i<N;i++) a[i]=in.nextInt(); int ind=0; int max; int k=K; while(ind<a.length && k>0){ max=find(a,ind,a.length-1); if(a[max]>a[ind]){ swap(a,ind,max); k--; } ind++; } for(int i=0;i<N;i++) System.out.print(a[i]+" "); } }
Problem solution in C++.
#include<iostream> #include<sstream> #include<cstdio> #include<cstring> #include<algorithm> #include<string> #include<vector> #include<cmath> #include<set> #include<map> #include<stack> #include<queue> #include<numeric> #include<functional> #include<complex> using namespace std; #define BET(a,b,c) ((a)<=(b)&&(b)<(c)) #define FOR(i,n) for(int i=0,i##_end=(int(n));i<i##_end;i++) #define SZ(x) (int)(x.size()) #define ALL(x) (x).begin(),(x).end() #define MP make_pair #define CLS(x,val) memset((x) , val , sizeof(x)) #define FOR_EACH(it,v) for(__typeof(v.begin()) it=v.begin(),it_end=v.end() ; it != it_end ; it++) typedef long long ll_t; typedef long double ld_t; typedef vector<int> VI; typedef vector<VI> VVI; typedef complex<int> xy; int P[100000+10]; int IndexFromValue[100000+10]; int main() { int N,K; cin>>N>>K; FOR(i,N) scanf("%d",&P[i]); FOR(i,N) IndexFromValue[P[i]] = i; for(int i=N;i>=1 && K > 0;i--){ int bestPos = N - i; if(bestPos == IndexFromValue[i]) continue; int p = IndexFromValue[i]; swap(IndexFromValue[i], IndexFromValue[P[bestPos]]); swap(P[bestPos], P[p]); K--; } FOR(i,N) printf("%s%d", i?" ":"", P[i]); return 0; }
Problem solution in C.
#include <stdio.h> #include <string.h> #include <math.h> #include <stdlib.h> int main() { long long int n,k,i,a[100000],temp,j,l; scanf("%lld%lld",&n,&k); for(i=0;i<n;i++) { scanf("%lld",&a[i]); } l=n; for(i=0;i<k;i++) { if(a[i]==l) { k++; } else { for(j=i;j<n;j++) { if(a[j]==l) { temp=a[j]; a[j]=a[i]; a[i]=temp; } } } l--; } for(i=0;i<n;i++) printf("%lld ",a[i]); return 0; }