Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official. ×

By _aditya, history, 10 months ago, ,

i encountered this problem on a hiring contest and dont think its editorial will be provided. It goes like there's an array of n numbers and a number k is given. both n,k<=10^5 arr[i]<=10^5 we have to find minimum number of swaps so that all numbers greater than k are clubber together.

•
• +2
•

 » 10 months ago, # | ← Rev. 4 →   0 Removed
•  » » 10 months ago, # ^ |   0 help me with this case. array=3,4,1,1,5,6,1,1,7,8,9 k=3now we fix 6. no we have to bring 3,4 closer to 6 that can be done by either swapping them with first pair of 1 or second pair.if we do with first pair ,no of swaps resulting will be 4for second it will be two.
•  » » » 10 months ago, # ^ |   0 I thought we could swap only consecutive elements...
 » 10 months ago, # |   +4 Please, clarify your swapping mechanism. Can I sawp any i , j (1 <= i,j <= n) . or I can swap two consecutive elements :\ ?
•  » » 10 months ago, # ^ |   0 sorry for that, any i,j can be swapped.
 » 10 months ago, # | ← Rev. 2 →   +3 I think challage is still live on hackerearth, almost after every hiring they provide solution after some time.So please wait for challange to Complete.
•  » » 10 months ago, # ^ |   0 very rare
 » 10 months ago, # |   +1 Let's say there are p numbers greater than k in the given array. Then we have to find subarray of size p that contains maximum numbers greater than k. Answer will be numbers that are less than k in that subarray . You can do it in O(n) .
•  » » 10 months ago, # ^ |   0 thanks a lot man.How long did it take you to come up with this solution.
•  » » » 10 months ago, # ^ |   0 Welcome . Not much.