commit f3dd448170fbc76bf48655c58dc9f0d75551ea75
parent 24b2545d0e401fa33425998e771929ee34bc5a63
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date: Wed, 13 Sep 2023 20:00:24 +0200
5 Random Problems
Diffstat:
6 files changed, 101 insertions(+), 0 deletions(-)
diff --git a/Problems/1414.cpp b/Problems/1414.cpp
@@ -0,0 +1,19 @@
+class Solution {
+ typedef array<int, 45> cache_t;
+ static inline constexpr const cache_t cache = []() constexpr -> cache_t {
+ cache_t cache;
+ cache[0] = cache[1] = 1;
+ for (int i = 2; i < cache.size(); i++)
+ cache[i] = cache[i - 1] + cache[i - 2];
+ return cache;
+ }();
+
+ public:
+ int findMinFibonacciNumbers(int k) {
+ int res = 0;
+ for (auto it = upper_bound(begin(cache), end(cache), k); k > 0; it--)
+ while (k >= *it)
+ k -= *it, res++;
+ return res;
+ }
+};
diff --git a/Problems/1492.cpp b/Problems/1492.cpp
@@ -0,0 +1,16 @@
+class Solution {
+ public:
+ int kthFactor(int n, int k) {
+ int d = 1;
+ for (; d * d <= n; d++) {
+ if (n % d == 0 && --k == 0) return d;
+ }
+
+ d--;
+ if (d * d == n) d--;
+ for (; d >= 1; d--) {
+ if (n % d == 0 && --k == 0) return n / d;
+ }
+ return -1;
+ }
+};
diff --git a/Problems/1899.cpp b/Problems/1899.cpp
@@ -0,0 +1,13 @@
+class Solution {
+ public:
+ bool mergeTriplets(const vector<vector<int>> &triplets, const vector<int> &tgt) {
+ bool a = false, b = false, c = false;
+ for (const auto &tp : triplets) {
+ if (tp[0] > tgt[0] || tp[1] > tgt[1] || tp[2] > tgt[2]) continue;
+ if (tp[0] == tgt[0]) a = true;
+ if (tp[1] == tgt[1]) b = true;
+ if (tp[2] == tgt[2]) c = true;
+ }
+ return a && b && c;
+ }
+};
diff --git a/Problems/2043.cpp b/Problems/2043.cpp
@@ -0,0 +1,38 @@
+#pragma GCC optimize("fast")
+static int _ = []() {
+ ios_base::sync_with_stdio(false);
+ cout.tie(NULL);
+ cin.tie(NULL);
+ return 0;
+}();
+
+class Bank {
+ const int n;
+ vector<long long> balance;
+
+ inline bool valid(int acc) const { return acc >= 1 && acc <= n; }
+
+ public:
+ Bank(const vector<long long> &balance) : n(balance.size()), balance(balance) {}
+
+ inline bool transfer(int account1, int account2, long long money) {
+ if (!valid(account1) || !valid(account2)) return false;
+ if (!withdraw(account1, money)) return false;
+ if (!deposit(account2, money)) return false;
+ ;
+ return true;
+ }
+
+ inline bool deposit(int account, long long money) {
+ if (!valid(account)) return false;
+ balance[account - 1] += money;
+ return true;
+ }
+
+ inline bool withdraw(int account, long long money) {
+ if (!valid(account)) return false;
+ if (money > balance[account - 1]) return false;
+ balance[account - 1] -= money;
+ return true;
+ }
+};
diff --git a/Problems/2740.cpp b/Problems/2740.cpp
@@ -0,0 +1,10 @@
+class Solution {
+ public:
+ int findValueOfPartition(vector<int> &nums) {
+ sort(begin(nums), end(nums));
+ int res = INT_MAX;
+ for (int i = 1; i < nums.size(); i++)
+ res = min(res, nums[i] - nums[i - 1]);
+ return res;
+ }
+};
diff --git a/README.md b/README.md
@@ -554,6 +554,7 @@ for solving problems.
| 1402 | Hard | [Reducing Dishes](Problems/1402.cpp) |
| 1406 | Hard | [Stone Game III](Problems/1406.cpp) |
| 1409 | Medium | [Queries on a Permutation With Key](Problems/1409.cpp) |
+| 1414 | Medium | [Find the Minimum Number of Fibonacci Numbers Whose Sum Is K](Problems/1414.cpp) |
| 1415 | Medium | [The k-th Lexicographical String of All Happy Strings of Length n](Problems/1415.cpp) |
| 1416 | Hard | [Restore The Array](Problems/1416.cpp) |
| 1418 | Medium | [Display Table of Food Orders in a Restaurant](Problems/1418.cpp) |
@@ -578,6 +579,7 @@ for solving problems.
| 1480 | Easy | [Running Sum of 1d Array](Problems/1480.cpp) |
| 1489 | Hard | [Find Critical and Pseudo-Critical Edges in Minimum Spanning Tree](Problems/1489.cpp) |
| 1491 | Easy | [Average Salary Excluding the Minimum and Maximum Salary](Problems/1491.cpp) |
+| 1492 | Medium | [The kth Factor of n](Problems/1492.cpp) |
| 1493 | Medium | [Longest Subarray of 1's After Deleting One Element](Problems/1493.cpp) |
| 1498 | Medium | [Number of Subsequences That Satisfy the Given Sum Condition](Problems/1498.cpp) |
| 1502 | Easy | [Can Make Arithmetic Progression From Sequence](Problems/1502.cpp) |
@@ -652,6 +654,7 @@ for solving problems.
| 1870 | Medium | [Minimum Speed to Arrive on Time](Problems/1870.cpp) |
| 1877 | Medium | [Minimize Maximum Pair Sum in Array](Problems/1877.cpp) |
| 1884 | Medium | [Egg Drop With 2 Eggs and N Floors](Problems/1884.cpp) |
+| 1899 | Medium | [Merge Triplets to Form Target Triplet](Problems/1899.cpp) |
| 1905 | Medium | [Count Sub Islands](Problems/1905.cpp) |
| 1910 | Medium | [Remove All Occurrences of a Substring](Problems/1910.cpp) |
| 1926 | Medium | [Nearest Exit from Entrance in Maze](Problems/1926.cpp) |
@@ -667,6 +670,7 @@ for solving problems.
| 2023 | Medium | [Number of Pairs of Strings With Concatenation Equal to Target](Problems/2023.cpp) |
| 2024 | Medium | [Maximize the Confusion of an Exam](Problems/2024.cpp) |
| 2039 | Medium | [The Time When the Network Becomes Idle](Problems/2039.cpp) |
+| 2043 | Medium | [Simple Bank System](Problems/2043.cpp) |
| 2044 | Medium | [Count Number of Maximum Bitwise-OR Subsets](Problems/2044.cpp) |
| 2073 | Easy | [Time Needed to Buy Tickets](Problems/2073.cpp) |
| 2079 | Medium | [Watering Plants](Problems/2079.cpp) |
@@ -777,5 +781,6 @@ for solving problems.
| 2685 | Medium | [Count the Number of Complete Components](Problems/2685.cpp) |
| 2707 | Medium | [Extra Characters in a String](Problems/2707.cpp) |
| 2711 | Medium | [Difference of Number of Distinct Values on Diagonals](Problems/2711.cpp) |
+| 2740 | Medium | [Find the Value of the Partition](Problems/2740.cpp) |
| 2785 | Medium | [Sort Vowels in a String](Problems/2785.cpp) |
| 2807 | Medium | [Insert Greatest Common Divisors in Linked List](Problems/2807.cpp) |
