Create 1774.Closest-Dessert-Cost.cpp

wisdompeak · web-flow · commit b8a2960d9b0d · 2021-02-28T00:06:37.000-08:00
diff --git a/Bit_Manipulation/1774.Closest-Dessert-Cost/1774.Closest-Dessert-Cost.cpp b/Bit_Manipulation/1774.Closest-Dessert-Cost/1774.Closest-Dessert-Cost.cpp
@@ -0,0 +1,30 @@
+class Solution {
+public:
+    int closestCost(vector<int>& baseCosts, vector<int>& toppingCosts, int target) 
+    {
+        int cost;
+        int diff = INT_MAX;
+        int m = toppingCosts.size();
+        
+        for (int baseCost: baseCosts)
+        {            
+            for (int state = 0; state < (1<<(2*m)); state++)
+            {
+                int sum = baseCost;
+                for (int i=0; i<m; i++)
+                {
+                    if ((state>>(i*2))&1)
+                        sum += toppingCosts[i];
+                    if ((state>>(i*2+1))&1)
+                        sum += toppingCosts[i];
+                }
+                if (abs(sum-target)<diff || abs(sum-target)==diff && sum<cost)
+                {
+                    diff = abs(sum-target);
+                    cost = sum;
+                }
+            }            
+        }        
+        return cost;        
+    }
+};
