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
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 = " ")
