Skip to content
  • Home
  • Contact Us
  • About Us
  • Privacy Policy
  • DMCA
  • Linkedin
  • Pinterest
  • Facebook
thecscience

TheCScience

TheCScience is a blog that publishes daily tutorials and guides on engineering subjects and everything that related to computer science and technology

  • Home
  • Human values
  • Microprocessor
  • Digital communication
  • Linux
  • outsystems guide
  • Toggle search form
HackerRank Largest Permutation Problem Solution

HackerRank Largest Permutation Problem Solution

Posted on June 5, 2023June 5, 2023 By Yashwant Parihar No Comments on 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
HackerRank Largest Permutation Problem Solution

Table of Contents

  • Largest Permutation C Solution
  • Largest Permutation C++ Solution
  • Largest Permutation C Sharp Solution
  • Largest Permutation Java Solution
  • Largest Permutation JavaScript Solution
  • Largest Permutation Python Solution

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 = " ")
c, C#, C++, HackerRank Solutions, java, javascript, python Tags:C, cpp, CSharp, Hackerrank Solutions, java, javascript, python

Post navigation

Previous Post: HackerRank Priyanka and Toys Problem Solution
Next Post: HackerRank Mark and Toys Problem Solution

Related Posts

HackerRank Cards Permutation Problem Solution HackerRank Cards Permutation Problem Solution c
HackerRank New Year Chaos Problem Solution HackerRank New Year Chaos Problem Solution c
HackerRank Points in a Plane Problem Solution HackerRank Points in a Plane Problem Solution c
HackerRank Beautiful Pairs Problem Solution HackerRank Beautiful Pairs Problem Solution c
HackerRank Sherlock and Anagrams Problem Solution HackerRank Sherlock and Anagrams Solution c
HackerRank Candles Counting Problem Solution HackerRank Candles Counting Problem Solution c

Leave a Reply Cancel reply

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

Pick Your Subject
Human Values

Copyright © 2023 TheCScience.

Powered by PressBook Grid Blogs theme