Unable to implement an approach in O(n)

#1

What is the efficient algorithm or STL to use in it?

#2

Mention problem link

#3

Hey Anubhav, the problem is “Unlock” you can refer Run : COOL19P2.

#4

Hi Ankit, For Unlock Problem
you can see that you need to make the largest permutation.
it means you need to permutate in such a way that a0>a1>a2… after k swaps
So greedy.
In first swap, place largest on first place
In second swap, place second largest on second place and so on.
Hit like if u get it

#5

It sounds like selection sort with k swaps If I am getting it right and that will be O(K*N)

#6

Hint- > you can use extra array to store which element is present on which index.
You can use it to get the exact position of largest element in O(1).
and overall O(n)

Example:

int pos[n+1];
for (int i = 0; i < n; i++)
pos[arr[i]] = i;

Hit like if u get it

#7

what if the numbers are taken as string and are repeating? I have generated the largest possible number using custom sort function(stl) of all strings(numbers) that can be formed but unable to use a map in it for above condition

#8

Read the problem statement.
It is mentioned that Numbers are first N natural numbers.It means they are not repeating .so u can use approach as discussed above .
If numbers are repeating then definately we have to use some modification of Map.
Hit like if u get it.

1 Like
#9

Can you provide some test cases I am getting Wrong Answer in all
https://ide.codingblocks.com/s/62261

#10

hi Ankit,
This problem has simple code and you are using complex code.
Refer my code
This code is according to the above discussed approach.
https://ide.codingblocks.com/s/62354

1 Like
#11

Oh I just realized that I already know the largest number will be n-1. I was taking arbitrary number that is why thank you

1 Like
#12

Can u mark it resolved . If all the queries are completed.