![HackerRank Largest Permutation Problem Solution](https://thecscience.com/wp-content/uploads/2023/06/HackerRank-Largest-Permutation-Problem-Solution.jpg)
HackerRank Largest Permutation Problem Solution
In this post, we will solve 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.
Example
arr = [1,2,3,4]
k=1
The following arrays can be formed by swapping the 1 with the other elements:
[2,1,3,4]
[3,2,1,4]
[4,2,3,1]
The highest value of the four (including the original) is [4, 2, 3, 1]. If k> 2, we can swap to the highest possible value: [4, 3, 2, 1].
Function Description
Complete the largestPermutation function in the editor below. It must return an array that represents the highest value permutation that can be formed.
largestPermutation has the following parameter(s):
- int k: the maximum number of swaps
- int arr[n]: an array of integers
Output Format
Print the lexicographically largest permutation you can make with at most K swaps.
Sample Input 0
STDIN Function ----- -------- 5 1 n = 5, k = 1 4 2 3 5 1 arr = [4, 2, 3, 5, 1]
Sample Output 0
5 2 3 4 1
![HackerRank Largest Permutation Problem Solution](https://thecscience.com/wp-content/uploads/2023/06/HackerRank-Largest-Permutation-Problem-Solution-1024x576.jpg)
Largest Permutation C Solution
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
void quicksort(int x[100000],int first,int last)
{
int i,j,temp,pivot;
if(first<last)
{
i=first;
j=last;
pivot=first;
while(i<j)
{
while(x[i]>=x[pivot]&&i<last)
{
i++;
}
while(x[j]<x[pivot])
{
j--;
}
if(i<j)
{
temp=x[i];
x[i]=x[j];
x[j]=temp;
}
}
temp=x[pivot];
x[pivot]=x[j];
x[j]=temp;
quicksort(x,first,j-1);
quicksort(x,j+1,last);
}
}
main() {
int i,j,k,l,m,n,p;
scanf("%d %d\n",&n,&k);
int a[n],b[n],d[n];
for(i=0;i<n;i++)
{
scanf("%d ",&a[i]);
b[i]=a[i];
d[i]=a[i];
}
quicksort(b,0,n-1);
int c[n];
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
if(b[i]==d[j])
{
c[i]=j;
d[j]=-1;
}
}
}
i=0;
m=0;
while((m<k)&&i<n)
{
if(a[i]<b[i])
{
for(j=i+1;j<n;j++)
{
if(b[i]==a[j])
{
l=j;
j=n+5;
}
}
p=a[l];
a[l]=a[i];
a[i]=p;
m++;
i++;
}
else
{
i++;
}
}
for(i=0;i<n;i++)
{
printf("%d ",a[i]);
}
}
Largest Permutation C++ Solution
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
int n, k;
int k2 = 0;
cin >> n >> k;
vector<int> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
if (i < k && a[i] == n - i){
//cout << "correct position" << endl;
k++;
}
}
for (int i = 0; i < n; i++){
//cout << "value: " << a[i] << endl;
while (a[i] > n - k && a[i] != n - i){
//cout << "swapping " << a[i] << " with " << a[n-a[i]] << endl;
swap(a[i], a[n - a[i]]);
k += i < k && a[i] == n - i;
}
//cout << "element " << i << " is " << a[i] << endl;
}
for (auto x : a) cout << x << " ";
cout << endl;
return 0;
}
Largest Permutation C Sharp Solution
using System;
using System.Collections.Generic;
using System.IO;
using System.Text;
class Solution {
static void Main(String[] args) {
string[] temp = Console.ReadLine().Split(' ');
int N = Convert.ToInt32(temp[0]);
int K = Convert.ToInt32(temp[1]);
int[] input = new int[N];
temp = Console.ReadLine().Split(' ');
for (int i = 0; i < N; ++i) {
input[i] = Convert.ToInt32(temp[i]);
}
Process(input, K);
StringBuilder sb = new StringBuilder();
for (int i = 0; i < N; ++i) {
sb.Append(input[i] + " ");
}
Console.WriteLine(sb.ToString());
}
static void Write(int[] input)
{
StringBuilder sb = new StringBuilder();
for (int i = 0; i < input.Length; ++i)
{
sb.Append(input[i] + " ");
}
Console.WriteLine(sb.ToString());
}
static void Process(int[] input, int K)
{
int current = 0;
for (int i = 0; i < input.Length; ++i)
{
for (int j = i + 1; j < input.Length; ++j)
{
if (input[j] > input[i])
{
int maxIndex = j;
for (int k = j; k < input.Length; ++k)
{
if (input[k] > input[maxIndex])
{
maxIndex = k;
}
}
Exchange(input, i, maxIndex);
current++;
if (current == K)
{
return;
}
}
}
}
}
static void Exchange(int[] input, int i, int j)
{
int temp = input[i];
input[i] = input[j];
input[j] = temp;
}
}
Largest Permutation Java Solution
import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.function.*;
import java.util.regex.*;
import java.util.stream.*;
import static java.util.stream.Collectors.joining;
import static java.util.stream.Collectors.toList;
class Result {
/*
* Complete the 'largestPermutation' function below.
*
* The function is expected to return an INTEGER_ARRAY.
* The function accepts following parameters:
* 1. INTEGER k
* 2. INTEGER_ARRAY arr
*/
public static List<Integer> largestPermutation(int k, List<Integer> arr) {
// **** initialization ****
var n = arr.size();
// **** sanity checks ****
if (n == 1) return arr;
if (k >= n) {
Collections.sort(arr, Collections.reverseOrder());
return arr;
}
// **** position of numbers in list ****
int[] position = new int[n + 1];
for (var i = 0; i < arr.size(); i++)
position[arr.get(i)] = i;
// **** ****
for (int i = n, swaps = k; i > 0; --i) {
// **** ****
var actualPos = position[i];
// **** ****
var expectedPos = n - i;
// **** check if i'th value is in the expected place ****
if (actualPos != expectedPos) {
// **** swap list elements ****
Collections.swap(arr, actualPos, expectedPos);
// **** update positions ****
position[arr.get(actualPos)] = actualPos;
position[arr.get(expectedPos)] = expectedPos;
// **** check if we are done ****
if (--swaps < 1) break;
}
}
// **** return modified list ****
return arr;
}
}
public class Solution {
public static void main(String[] args) throws IOException {
BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));
String[] firstMultipleInput = bufferedReader.readLine().replaceAll("\\s+$", "").split(" ");
int n = Integer.parseInt(firstMultipleInput[0]);
int k = Integer.parseInt(firstMultipleInput[1]);
List<Integer> arr = Stream.of(bufferedReader.readLine().replaceAll("\\s+$", "").split(" "))
.map(Integer::parseInt)
.collect(toList());
List<Integer> result = Result.largestPermutation(k, arr);
bufferedWriter.write(
result.stream()
.map(Object::toString)
.collect(joining(" "))
+ "\n"
);
bufferedReader.close();
bufferedWriter.close();
}
}
Largest Permutation JavaScript Solution
function processData(input) {
var lines = input.split("\n");
var params = lines[0].split(' ').map(Number);
var n = params[0];
var k = params[1];
var arr = lines[1].trim().split(' ').map(Number);
var pos = new Array(n + 1);
var numSwaps = 0;
var i, smaller, larger;
for (i = 0; i < n; i++) {
pos[arr[i]] = i;
}
for (i = 0; i < n; i++) {
if (n - i > arr[i]) {
smaller = arr[i];
larger = n - i;
swap(arr, i, pos[larger]);
swap(pos, smaller, larger);
numSwaps++;
if (numSwaps === k) {
break;
}
}
}
console.log(arr.join(' '));
}
function swap(arr, i, j) {
var temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
process.stdin.resume();
process.stdin.setEncoding("ascii");
_input = "";
process.stdin.on("data", function (input) {
_input += input;
});
process.stdin.on("end", function () {
processData(_input);
});
Largest Permutation Python Solution
n, k = input().split()
n = int(n)
k = int(k)
a = n * [0]
a = input().split()
a = [int(i) for i in a]
b = n * [0]
for i in range(0, n):
b[a[i] - 1] = i
count = 0
j = 0
while count < k and j < n:
if a[j] != n - j:
a[j], a[b[n - j - 1]] = a[b[n - j - 1]], a[j]
b[a[b[n - j - 1]] - 1], b[a[j] - 1] = b[a[j] - 1], b[a[b[n - j - 1]] - 1]
count += 1
j += 1
for i in range(0, n):
print(a[i], end = " ")