_aditya's blog

someone help me with question?
By _aditya, history, 6 years ago, In English

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.

  • Vote: I like it
  • +2
  • Vote: I do not like it

Comments Comments (8)
| Write comment?
»
6 years ago, # |
← Rev. 4   Vote: I like it 0 Vote: I do not like it

Removed

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    help me with this case. array=3,4,1,1,5,6,1,1,7,8,9 k=3

    now 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 4

    for second it will be two.

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I thought we could swap only consecutive elements...

      → Reply
»
6 years ago, # |
  Vote: I like it +4 Vote: I do not like it

Please, clarify your swapping mechanism. Can I sawp any i , j (1 <= i,j <= n) . or I can swap two consecutive elements :\ ?

→ Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

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.

→ Reply
»
6 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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) .

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    thanks a lot man.

    How long did it take you to come up with this solution.

    → Reply