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.
My solution: I did it a bit differently, first i sorted the array while preserving indexes. then i traversed through the sorted array while comparing each two adjacent values, checking whether if it's a profit or a loss transaction. if it's a loss transaction and lower than previously encountered loss transaction then i store that as the minloss. At the end of the traversal I have my minloss value.
(Since it's given that a solution exists and it is being sold at loss. So for opimizing the code whenever I encounter a loss transaction of 1, which is the absolute minimum loss possible I straightaway return that value and don;t check any further.)
I proved to myself using simple inequations that a minloss will not occur at an index distance of greater than 1. I proved it by negation, I assumed first that it can exist at an index distance of 2, and then proved that a minimum loss must be at an index distance of 1. Then by induction I can prove that a minloss cant exist fro index distance of 3,4,5......
It's very simple, I can elaborate the proof if anybody needs it.
defminimumLoss(price):# Write your code hereflag_setLoss=FalseminLoss=-1# indexed price list, indexed by yearprice_indexed=[[price[i],i]foriinrange(0,len(price))]# sort the listprice_indexed.sort(key=price_val)'''Sincethelistinsorted,allpricesarearrangeinasc-order,weneedtoselectaadjacentpairwhichhastheleastdifferenceandgivesaloss,butneedtocheckifit'svalidpairornot.iebuyingyearshouldbelessthansellingyear.'''foriinrange(0,len(price_indexed)-1):# if trasaction valid(buy year is less than sell year)if(price_indexed[i][1]>price_indexed[i+1][1]):# loss is Sell priceloss=price_indexed[i+1][0]-price_indexed[i][0]'''Theminimumpossiblelosseverinthisproblemis1.Sowhenlossvalueforanytransaction1isthenthatisminimumpossible.sojustreturnit.(assuming0lossisnotconsideredasloss)'''if(loss==1):return1if(flag_setLoss==False):#ifminLossvaluenotsetthensetitandsettheflagminLoss=lossflag_setLoss=Trueelif(loss<minLoss):minLoss=lossreturnminLoss# function that returns the price value in the indexed price listdefprice_val(a):returna[0]
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Minimum Loss
You are viewing a single comment's thread. Return to all comments →
My solution: I did it a bit differently, first i sorted the array while preserving indexes. then i traversed through the sorted array while comparing each two adjacent values, checking whether if it's a profit or a loss transaction. if it's a loss transaction and lower than previously encountered loss transaction then i store that as the minloss. At the end of the traversal I have my minloss value. (Since it's given that a solution exists and it is being sold at loss. So for opimizing the code whenever I encounter a loss transaction of 1, which is the absolute minimum loss possible I straightaway return that value and don;t check any further.)
I proved to myself using simple inequations that a minloss will not occur at an index distance of greater than 1. I proved it by negation, I assumed first that it can exist at an index distance of 2, and then proved that a minimum loss must be at an index distance of 1. Then by induction I can prove that a minloss cant exist fro index distance of 3,4,5......
It's very simple, I can elaborate the proof if anybody needs it.