We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Practice
  2. Algorithms
  3. Sorting
  4. Lily's Homework
  5. Discussions

Lily's Homework

  • nikhil_gupta3591 + 1 comment

    Problem could be intresting if you try to solve it for array having duplicate elements.

    • ayushr2 + 0 comments

      my solution handles duplicates elements its not really challenging.

      n = int(input())
l = list(map(int, input().split()))

sort = sorted(l)
rev = list(reversed(l))

d = {}
for i in range(n):
    if sort[i] not in d:
        d[sort[i]] = i

swaps = 0
i = 0
while i < n:
    if sort[i] == l[i]:
        i += 1
        continue
    swaps += 1
    l[d[l[i]]], l[i] = l[i], l[d[l[i]]]
    d[sort[i]] += 1

d = {}
for i in range(n):
    if sort[i] not in d:
        d[sort[i]] = i

swaps_rev = 0
i = 0
while i < n:
    if sort[i] == rev[i]:
        i += 1
        continue
    swaps_rev += 1
    rev[d[rev[i]]], rev[i] = rev[i], rev[d[rev[i]]]
    d[sort[i]] += 1

print(min(swaps, swaps_rev))