How to prove the transitivity of the comparator?

  • 2

    The solution can't be correct without the transitivity:

    If AB > BA and BC > CB, then we have AC > CA.

    But how to prove it?

  • -1

    What I have is:

    1)   AB > BA
    2)   BC > CB

    from 2) we have

    3)   BAC > CAB

    from 1) we have

    4)  BAC > CAB > CBA

    from 1) we also have

    5) ABC > BAC > CAB > CBA

    from 5 and "take out" the B we have

    6) AC > CA

    Glad you asked this, even after showing this property, I'm still not sure why this "sorting" solution works.

    EDIT: Just realized I didn't prove that AB > BA => ACB > BCA. I believe that inequality is true. Don't want to prove it at the moment.

    EDIT2 : Realized what I said above is wrong too. My intuition is really not helping me for this problem.

  • 0

    that's my concern too, I don't know why someone just take it for granted, although it seems correct, but I can't prove it

  • 0

  • 0
    1. BAC > CAB let's take A 999, B70078, C7007, this assertion is not correct

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.