leetcode

commit 472a1ca2bbf5e26c5a2db5e5bc71135e7280fc94
parent efd0bf974830c5fa091956c3ba96ff9e4d4b65db
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Fri, 24 Feb 2023 15:14:46 +0100

Daily Problem

Diffstat:
A
Problems/1675.cpp
 | 
21
+++++++++++++++++++++
M
README.md
 | 
1
+

2 files changed, 22 insertions(+), 0 deletions(-)
diff --git a/Problems/1675.cpp b/Problems/1675.cpp
@@ -0,0 +1,21 @@
+class Solution {
+public:
+  int minimumDeviation(vector<int> &nums) {
+    int res = INT_MAX, mini = INT_MAX;
+    for (auto &num : nums) {
+      num = num % 2 ? num * 2 : num;
+      mini = min(mini, num);
+    }
+
+    make_heap(begin(nums), end(nums));
+    while (nums.front() % 2 == 0) {
+      res = min(res, nums.front() - mini);
+      mini = min(mini, nums.front() / 2);
+      pop_heap(begin(nums), end(nums));
+      nums.back() /= 2;
+      push_heap(begin(nums), end(nums));
+    }
+
+    return min(res, nums.front() - mini);
+  }
+};
diff --git a/README.md b/README.md
@@ -411,6 +411,7 @@ for solving problems.
 |  1646  |    Easy    | [Get Maximum in Generated Array](Problems/1646.cpp)                                              |
 |  1669  |   Medium   | [Merge In Between Linked Lists](Problems/1669.cpp)                                               |
 |  1672  |    Easy    | [Richest Customer Wealth](Problems/1672.cpp)                                                     |
+|  1675  |    Hard    | [Minimize Deviation in Array](Problems/1675.cpp)                                                 |
 |  1696  |   Medium   | [Jump Game VI](Problems/1696.cpp)                                                                |
 |  1700  |    Easy    | [Number of Students Unable to Eat Lunch](Problems/1700.cpp)                                      |
 |  1704  |    Easy    | [Determine if String Halves Are Alike](Problems/1704.cpp)                                        |