leetcode

commit ff457c055a4581529630fda689766f915900843f
parent a4868eb2e020dacfffda0b45b4605ed2c425dcea
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Mon, 16 Jan 2023 13:36:27 +0100

Random Problem because Daily was done

Diffstat:
A
Problems/1722.cpp
 | 
51
+++++++++++++++++++++++++++++++++++++++++++++++++++
M
README.md
 | 
1
+

2 files changed, 52 insertions(+), 0 deletions(-)
diff --git a/Problems/1722.cpp b/Problems/1722.cpp
@@ -0,0 +1,51 @@
+class UnionFind {
+  int n, cnt = n;
+  vector<int> root, size;
+
+public:
+  UnionFind(int n) : n(n), root(n), size(n, 1) {
+    iota(root.begin(), root.end(), 0);
+  }
+
+  int find(int x) {
+    while (x != root[x]) x = root[x] = root[root[x]];
+    return x;
+  }
+
+  void join(int x, int y) {
+    x = find(x), y = find(y);
+    if (x != y) {
+      if (size[x] > size[y]) swap(x, y);
+      root[x] = y;
+      size[y] += size[x];
+      cnt--;
+    }
+  }
+
+  int count() { return cnt; }
+  bool connected(int x, int y) { return find(x) == find(y); }
+};
+
+class Solution {
+public:
+  int minimumHammingDistance(vector<int> &source, vector<int> &target,
+                             vector<vector<int>> &allowedSwaps) {
+    int n = source.size();
+    UnionFind uf(n);
+
+    for (auto &s : allowedSwaps) uf.join(s[0], s[1]);
+
+    vector<unordered_map<int, int>> vus(n);
+    for (int i = 0; i < n; i++) {
+      int pos = uf.find(i);
+      vus[pos][target[i]]++;
+      vus[pos][source[i]]--;
+    }
+
+    int res = 0;
+    for (int i = 0; i < n; i++)
+      for (auto [_, val] : vus[i]) res += abs(val);
+
+    return res / 2;
+  }
+};
diff --git a/README.md b/README.md
@@ -276,6 +276,7 @@ for solving problems.
 |  1700  |    Easy    | [Number of Students Unable to Eat Lunch](Problems/1700.cpp)                                      |
 |  1704  |    Easy    | [Determine if String Halves Are Alike](Problems/1704.cpp)                                        |
 |  1706  |   Medium   | [Where Will the Ball Fall](Problems/1706.cpp)                                                    |
+|  1722  |   Medium   | [Minimize Hamming Distance After Swap Operations](Problems/1722.cpp)                             |
 |  1786  |   Medium   | [Number of Restricted Paths From First to Last Node](Problems/1786.cpp)                          |
 |  1791  |    Easy    | [Find Center of Star Graph](Problems/1791.cpp)                                                   |
 |  1823  |   Medium   | [Find the Winner of the Circular Game](Problems/1823.cpp)                                        |