leetcode

commit f54c6230f9feaa77f3ec7fe545aca527bc0ebd28
parent 4335e1da28fdac35c6b1fb26cc7738fdcbd4311c
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Tue, 31 Oct 2023 22:49:11 +0000

1 Random Problem

Diffstat:
A
Problems/0462.cpp
 | 
24
++++++++++++++++++++++++
M
README.md
 | 
1
+

2 files changed, 25 insertions(+), 0 deletions(-)
diff --git a/Problems/0462.cpp b/Problems/0462.cpp
@@ -0,0 +1,24 @@
+class Solution {
+  public:
+    int minMoves2(vector<int> &nums) const {
+        int res = 0, i = 0, j = nums.size() - 1;
+        sort(begin(nums), end(nums));
+        while (i < j)
+            res += nums[j--] - nums[i++];
+        return res;
+    }
+};
+
+// Optimized solution
+class Solution {
+  public:
+    int minMoves2(vector<int> &nums) const {
+        const int n = nums.size(), mid = n / 2;
+        nth_element(begin(nums), begin(nums) + mid, end(nums));
+        const int median = nums[mid];
+        int res = 0;
+        for (int i = 0; i < n; i++)
+            res += abs(nums[i] - median);
+        return res;
+    }
+};
diff --git a/README.md b/README.md
@@ -307,6 +307,7 @@ for solving problems.
 |  0458  |    Hard    | [Poor Pigs](Problems/0458.cpp)                                                                     |
 |  0459  |    Easy    | [Repeated Substring Pattern](Problems/0459.cpp)                                                    |
 |  0460  |    Hard    | [LFU Cache](Problems/0460.cpp)                                                                     |
+|  0462  |   Medium   | [Minimum Moves to Equal Array Elements II](Problems/0462.cpp)                                      |
 |  0472  |    Hard    | [Concatenated Words](Problems/0472.cpp)                                                            |
 |  0485  |    Easy    | [Max Consecutive Ones](Problems/0485.cpp)                                                          |
 |  0486  |   Medium   | [Reachable Nodes With Restrictions](Problems/0486.cpp)                                             |