Leetcode-Solutions/Buy Two Chocolates.cpp at main · Hk0509/Leetcode-Solutions · GitHub

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
44
45
46
47
//O(n) Solution
class Solution {
public:
    int buyChoco(vector<int>& prices, int money) {
        int mini = 1e9, mini2 = 1e9;
        for(auto it: prices){
            if(it < mini){
                mini2 = mini;
                mini = it;
            }
            else if(it < mini2){
                mini2 = it;
            }
        }
        int left = money - mini - mini2;
        return left < 0 ? money : left;
    }
};

//O(logn) Solution
// class Solution {
// public:
//     int buyChoco(vector<int>& prices, int money) {
//         sort(prices.begin(), prices.end());
//         int leftover = money - (prices[0] + prices[1]);
//         return leftover < 0 ? money : leftover;
//     }
// };

//O(logn) during Contest Solution
// class Solution {
// public:
//     int buyChoco(vector<int>& prices, int money) {
//         sort(prices.begin(), prices.end()); //Sort the array
//         int count = 2;
//         int mon = money;
//         //Iterate over prices vector
//         for(auto it: prices)
//         {
//                 if(count == 0) return money;
//                 if(it>money) return mon;
//                 money -= it;
//                 count --;
//         }
//         return money;
//     }
// };