Algorithm

HackerRank/Algorithm/Search/Minimum Loss

Problem Summary

Given prices of a house in N years, find the minimum loss if we first buy it and then sell it at a lower price.

Solution 1

Suppose we sell the house on day i, then we only need to find the price just above price[i], from price[1],price[2],…,price[i-1].
If we use C++’s set container, we can keep prices in order, then we can use binary search to find the one we need.

Solution 2

This problem can also be solved using greedy.

First, we sort all years according to the prices.

Code for Solution 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <set>
using namespace std;
const int maxn = 200002;
int n;
long long p[maxn];
set<long long> prices;
int main() {
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%lld",&p[i]);
	long long ans = ((long long) 1) << 50;
	prices.insert(p[1]);
	for (int i = 2; i <= n; ++i)
	{
		set<long long>::iterator it = prices.upper_bound(p[i]);
		if (it != prices.end())
			if (*it - p[i] < ans)
				ans = *it - p[i];
		prices.insert(p[i]);
	}
	printf("%lld\n",ans);
    return 0;
}

Code for Solution 2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 200002;
int n,idx[maxn];
long long p[maxn];
bool cmp(int a,int b)
{
	if(p[a]>p[b]) return true;
	return false;
}
int main() {
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		idx[i]=i;
		scanf("%lld",&p[i]);
	}
	
	sort(idx+1,idx+n+1,cmp);
	int a,b;
	long long ans = ((long long)1)<<50;
	for(int i=1;i<n;i++)
	{
		a=idx[i];
		b=idx[i+1];
		if(a<b && p[a]>p[b])
			ans=min(ans,p[a]-p[b]);
	}
	printf("%lld\n",ans);
    return 0;
}