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 →

  • goodengineer 4 years ago+ 0 comments

    Hey, counter example here:

    5
    3 4 2 1 5
    

    the expected output is 3, but with your logic:

    3 4 2 1 5
    1 2 3 4 5
    ---------
    1 1 1 1 0
    
    &&
    
    3 4 2 1 5
    5 4 3 2 1
    ---------
    1 0 1 1 1
    

    the output is ceil(4/2) = 2

    The flaw in your logic is that you assume that two different positions between the input array and the sorted input array are fixed with only 1 swap, when in reality it's a bit more complex than that.

    26|
    ParentPermalink
  • Contest Calendar
  • Blog
  • Scoring
  • Environment
  • FAQ
  • About Us
  • Support
  • Careers
  • Terms Of Service
  • Privacy Policy
  • Request a Feature