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.
Proof of correctness of looking at min diff of only consecutive numbers (when their positions satisfy the requirement) in a sorted price list: suppose that we have prices p1<p2<p3 where we assume that p1,p3 is the optimal pair. In the original list p1 must appear after p3, and since p1,p2 is not chosen as the optimal pair despite p2-p1<p3-p1, p2 must appear after p1. Then we know that p2 appears after p3 and p3-p2<p3-p1, and we should've chosen p2,p3 instead, contradiction.
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Minimum Loss 1
You are viewing a single comment's thread. Return to all comments →
Proof of correctness of looking at min diff of only consecutive numbers (when their positions satisfy the requirement) in a sorted price list: suppose that we have prices
p1<p2<p3where we assume thatp1,p3is the optimal pair. In the original listp1must appear afterp3, and sincep1,p2is not chosen as the optimal pair despitep2-p1<p3-p1,p2must appear afterp1. Then we know thatp2appears afterp3andp3-p2<p3-p1, and we should've chosenp2,p3instead, contradiction.