Header Ad

HackerRank Largest Permutation problem solution

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.

HackerRank Largest Permutation problem solution

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]+" ");

    }
}

{"mode":"full","isActive":false}


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;
}

{"mode":"full","isActive":false}


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;
}

{"mode":"full","isActive":false}


Post a Comment

0 Comments