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.
  1. Prepare
  2. Algorithms
  3. Search
  4. Minimum Loss
  5. Discussions

Minimum Loss

Sort 324 Discussions, By:

  • Coder_AMiT
     + 34 comments

    This must be an easy problem actually. all you have to do is sort the array, and then check the difference of adjacent pairs, if its less than ur last min value, update it only if the index of those pairs are in same way in original array.

    n =  int(input().strip())
numbers = list(map(int,input().strip().split()))

nums = list(numbers)
nums.sort()
minCost = 10**10
for i in range(1,n):
    if (nums[i]-nums[i-1] < minCost)  and (numbers.index(nums[i]) < numbers.index(nums[i-1])):
        minCost = nums[i]-nums[i-1]
print(minCost)

    ''' Improved version using Hash.'''

n =  int(input().strip())
numbers = list(map(int,input().strip().split()))
myDict = {}
for i in range(n):
    myDict[numbers[i]]=i
minCost = 10**10
nums = sorted(myDict)
for i in range(1,n):
    if (nums[i]-nums[i-1] < minCost)  and (myDict[nums[i]] < myDict[nums[i-1]]):
        minCost = nums[i]-nums[i-1]
print(minCost)

  • Bobthebuilder24
     + 2 comments

    Used Java's treeset, which can efficiently find the next smallest/largest element in a set:

    import java.util.Scanner;
import java.util.TreeSet;

public class MinimumLoss {
	public static void main(String[] args) {
		Scanner scn = new Scanner(System.in);
		int cases = scn.nextInt();
		TreeSet<Long> values = new TreeSet<>();
		values.add(scn.nextLong());
		long min = Long.MAX_VALUE;
		for (int i = 1; i < cases; i++) {
			long value = scn.nextLong();
			Long higher = values.higher(value);
			if (higher != null) {
				min = Math.min(min, Math.abs(higher - value));
			}
			values.add(value);
		}
		System.out.println(min);
		scn.close();
	}
}

  • prashanth
     + 2 comments

    I used a BST to solve this. I did a inorder walk, for every node I would do difference = (node - right most node of the left sub tree).

  • ameya_shanbhag
     + 0 comments

    Passed all the test cases.

    Approach:

    1. Make a dictionary for storing the index value of the element 2.Sort the original array(As the minimum would be diff in consecutive ones)
    2. Calculate the difference between consecutive elements and push it on the heap with tuple (Difference,original index of first element,original index of second element). You can get the original index by looking at the dictionary you created previously
    3. Keep popping elements from the heap and stop once you find first element's index>second element's index

    Note: I am a begineer in competitive coding. This might not be the optimal solution but if anyone is looking out for a easy to understand solution then this might be.

    Python2:

    from heapq import *
n = int(raw_input())
a = map(int,raw_input().split())
index = {}

#Keep track of the index
for i in range(n):
    index[a[i]] = i

a.sort()
table = [] #Heap table
for i in range(1,n):
    heappush(table,(a[i]-a[i-1],index[a[i-1]],index[a[i]]))
    
for i in range(n-1):
    element = heappop(table)
    if element[1]>element[2]:
        print element[0]
        break

  • jackwoodwardspa1
     + 1 comment

    9 Lines in python

    n = int(input())
price = list(map(int, input().rstrip().split()))
sortedprice = sorted(price, reverse = True)
minloss = sortedprice[0]
for x in range(len(sortedprice)-1):
    if (sortedprice[x] - sortedprice[x+1]) < minloss:
        if price.index(sortedprice[x]) < price.index(sortedprice[x+1]):
            minloss = (sortedprice[x] - sortedprice[x+1])
print(minloss)
Load more conversations