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.
- Prepare
- Algorithms
- Search
- Minimum Loss
- Discussions
Minimum Loss
Minimum Loss
Sort by
recency
|
369 Discussions
|
Please Login in order to post a comment
C# Solution
public static int minimumLoss(List price) { long minimum = long.MaxValue;
Can anyone helps me to take a look why the code below encountered three failed test cases? Thank you so much!
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.
It take me some time to find the solution and why the solution is correct.
The solution is very simple, just sort the array with index and then compare the element in the sorted array with its previous neighbors. The time complexity is nlog(n) governed by the sort.
Why it works?
You first sort the array, and each element has one big brother that is bigger than you(except for the last of course). Imagine you back to the original price array and you are the min price. Your next bigger brother may be on your left and may be on your right.
If on the left, then you can update the minCost, which is the silly investment want. You are wasted and now only need to care about your brothers. Because all your brother is bigger than you, no other brother can skip a brother and minus you to update the minCost.
If on the right, what should we do? Do you need to remember the two prices for further check? You don't know. Ok, let's check the third element.
* It could be like in front of all: [C,.. A,..., B], but C-A>C-B, you don't need to care about A. So check C-B only
* it could be in the middle [A,...C,...,B] you only need to check C-B vs minCost, nothing to do with A.
* it also could be at the back[A...,B...,C]. You can do nothing.
For each case, you find comparing the B,C is the only valid way to generate the minCost.
Hope you can prove that using math induction.
Also,hope that make sense.