leetcode

commit a036c2e1f7609b9e25609f60c5bd419ee69f9ff8
parent 4defcd7bc2eb7e6bb690e0a09da357fd3e45a075
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Mon, 25 Mar 2024 18:27:45 +0000

1 Random Problem

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

2 files changed, 22 insertions(+), 0 deletions(-)
diff --git a/Problems/0945.cpp b/Problems/0945.cpp
@@ -0,0 +1,21 @@
+class Solution {
+  public:
+    int minIncrementForUnique(const vector<int> &nums) const {
+        static int count[100001];
+        memset(count, 0x00, sizeof(count));
+
+        for (const int n : nums)
+            count[n]++;
+
+        int res = 0, carry = 0;
+        for (int i = 0; i < 100001; i++) {
+            if (count[i] >= 1)
+                carry += count[i] - 1;
+            else if (carry)
+                carry--;
+            res += carry;
+        }
+
+        return res + carry * (carry - 1) / 2;
+    }
+};
diff --git a/README.md b/README.md
@@ -556,6 +556,7 @@ for solving problems.
 |  0939  |   Medium   | [Minimum Area Rectangle](Problems/0939.cpp)                                                        |
 |  0941  |    Easy    | [Valid Mountain Array](Problems/0941.cpp)                                                          |
 |  0944  |    Easy    | [Delete Columns to Make Sorted](Problems/0944.cpp)                                                 |
+|  0945  |   Medium   | [Minimum Increment to Make Array Unique](Problems/0945.cpp)                                        |
 |  0946  |   Medium   | [Validate Stack Sequences](Problems/0946.cpp)                                                      |
 |  0947  |   Medium   | [Most Stones Removed with Same Row or Column](Problems/0947.cpp)                                   |
 |  0948  |   Medium   | [Bag of Tokens](Problems/0948.cpp)                                                                 |