RoUge's blog

Minimum no of swaps to be done in an array such that, no two adjacent elements are same.
By RoUge, history, 7 years ago, In English

n = 6 a[] = {1, 1, 5, 2, 5, 5} answer = 1 ( swap a[0] with a[4] or a[5] )

n = 8 a[] = {1, 5, 5, 1, 4, 6, 1, 1} answer = 2 (swap a[0] with a[1] and a[5] with a[6] )

n = 8 a[] = {3, 1, 1, 5, 3, 3, 5, 5} answer = 2 (swap a[0] with a[1] and a[5] with a[6] )

indexing from zero in above examples.

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

Comments Comments (18)
| Write comment?
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone answer this?

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

    I need also to know answer of this problem

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

You can solve it using brute force if the limit is smaller than 1e5

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

    What if n up to 1e9 ?

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

      Do you know dp ? I think you can solve it using dp , but I'm not sure . I will think about it, nice problem : ).

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

        I know DP , But DP Work if limit is short , It won't work

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

          Sad :') if n is 1e5 will it work ? right?

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

            I Think Also no , It won't work with dp

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

            Do you know dp better than n^2?

            Most things better than n^2 will work for 1e5

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

              right? , I didn't solve problems using dp.

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

                I don't Know dp will solve this problem better than n^2

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

                If You solve it using DP

                using memoization you need to loop to all who is adjacent is same element as them then Swap it and make answer will be minimum of all recurrences.

                In Worst Case it will be O(n^2)

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

                First make boolean array its name is vis after that ,We Can make Memoization Function Starting From First Element that its Adjacent element has same value and inside Function we will loop to adjacent elements that have same value and if we found element then increase answer by one and vis[i] = true , and swap element and make recursion on it.

                The Complexity of This in worst Case is O(n^2)

                → Reply
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  3 years ago, # ^ |
                  ← Rev. 2   Vote: I like it -8 Vote: I do not like it

                  Bakry Hi, I am not able to understand how memoization is working here, could you please explain it in a little more detail please? Thank You in advance :)

                  Btw, this question was asked on an onsight google interview recently.

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

                  my comment is from 3 years, I don't remember any details and I think my solution was wrong.

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

                Your Welcome :)

                I will ask also Tomorrow about solution that will work well if n equal 10 ^ 9

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

                I didn't Find Solution For This Problem.

                Did you find any solution ?

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

              No I can't answer it with dp better than n^2

              → Reply