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.
  • Practice
  • Certification
  • Compete
  • Career Fair
  • Hiring developers?
  1. Practice
  2. Algorithms
  3. Sorting
  4. Lily's Homework
  5. Discussions

Lily's Homework

Problem
Submissions
Leaderboard
Discussions
Editorial

    You are viewing a single comment's thread. Return to all comments →

  • ayushr2 4 years ago+ 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))
    
    -7|
    ParentPermalink
  • Contest Calendar
  • Blog
  • Scoring
  • Environment
  • FAQ
  • About Us
  • Support
  • Careers
  • Terms Of Service
  • Privacy Policy
  • Request a Feature