leetcode

commit 548b278c47a844fa8d443ba36fcfecdc89a37bc7
parent 17e0983e0611bf4636f8e1d9e8ad0a0a6d973e7f
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Wed, 11 Jan 2023 20:31:00 +0100

Daily Problem and few randoms

Diffstat:
A
Problems/0231.cpp
 | 
4
++++
A
Problems/0326.cpp
 | 
7
+++++++
A
Problems/0342.cpp
 | 
6
++++++
A
Problems/1443.cpp
 | 
43
+++++++++++++++++++++++++++++++++++++++++++
M
README.md
 | 
4
++++

5 files changed, 64 insertions(+), 0 deletions(-)
diff --git a/Problems/0231.cpp b/Problems/0231.cpp
@@ -0,0 +1,4 @@
+class Solution {
+public:
+  bool isPowerOfTwo(int n) { return n > 0 && !(n & (n - 1)); }
+};
diff --git a/Problems/0326.cpp b/Problems/0326.cpp
@@ -0,0 +1,7 @@
+class Solution {
+public:
+  bool isPowerOfThree(int n) {
+    double x = log10(n) / log10(3);
+    return n > 0 && x == round(x);
+  }
+};
diff --git a/Problems/0342.cpp b/Problems/0342.cpp
@@ -0,0 +1,6 @@
+class Solution {
+public:
+  bool isPowerOfFour(int n) {
+    return n > 0 && (n & (n - 1)) == 0 && (n - 1) % 3 == 0;
+  }
+};
diff --git a/Problems/1443.cpp b/Problems/1443.cpp
@@ -0,0 +1,43 @@
+class Solution {
+public:
+  int minTime(int n, vector<vector<int>> &edges, vector<bool> &hasApple) {
+    vector<vector<int>> adj(n, vector<int>());
+    for (auto &e : edges) {
+      adj[e[0]].push_back(e[1]);
+      adj[e[1]].push_back(e[0]);
+    }
+
+    stack<pair<int, int>> st;
+    int res = 0;
+
+    st.push({0, -1});
+    while (!st.empty()) {
+      if (st.top().first == -1) {
+        st.pop();
+
+        auto [crnt, par] = st.top();
+        st.pop();
+        int count = 0;
+
+        for (int c : adj[crnt]) {
+          if (c == par) continue;
+          count += hasApple[c];
+        }
+
+        res += count;
+        hasApple[crnt] = hasApple[crnt] || count;
+        continue;
+      }
+
+      auto [crnt, par] = st.top();
+      st.push({-1, -1});
+
+      for (int c : adj[crnt]) {
+        if (c == par) continue;
+        st.push({c, crnt});
+      }
+    }
+
+    return res * 2;
+  }
+};
diff --git a/README.md b/README.md
@@ -108,6 +108,7 @@ for solving problems.
 |  0222  |   Medium   | [Count Complete Tree Nodes](Problems/0222.cpp)                                                   |
 |  0223  |   Medium   | [Rectangle Area](Problems/0223.cpp)                                                              |
 |  0226  |    Easy    | [Invert Binary Tree](Problems/0226.cpp)                                                          |
+|  0231  |    Easy    | [Power of Two](Problems/0231.cpp)                                                                |
 |  0234  |    Easy    | [Palindrome Linked List](Problems/0234.cpp)                                                      |
 |  0235  |   Medium   | [Lowest Common Ancestor of a Binary Search Tree](Problems/0235.cpp)                              |
 |  0236  |   Medium   | [Lowest Common Ancestor of a Binary Tree](Problems/0236.cpp)                                     |
@@ -123,8 +124,10 @@ for solving problems.
 |  0290  |    Easy    | [Word Pattern](Problems/0290.cpp)                                                                |
 |  0295  |    Hard    | [Find Median from Data Stream](Problems/0295.cpp)                                                |
 |  0310  |   Medium   | [Minimum Height Trees](Problems/0310.cpp)                                                        |
+|  0326  |    Easy    | [Power of Three](Problems/0326.cpp)                                                              |
 |  0328  |   Medium   | [Odd Even Linked List](Problems/0328.cpp)                                                        |
 |  0338  |    Easy    | [Counting Bits](Problems/0338.cpp)                                                               |
+|  0342  |    Easy    | [Power of Four](Problems/0342.cpp)                                                               |
 |  0344  |    Easy    | [Reverse String](Problems/0344.cpp)                                                              |
 |  0345  |    Easy    | [Reverse Vowels of a String](Problems/0345.cpp)                                                  |
 |  0347  |   Medium   | [Top K Frequent Elements](Problems/0347.cpp)                                                     |
@@ -251,6 +254,7 @@ for solving problems.
 |  1382  |   Medium   | [Balance a Binary Search Tree](Problems/1382.cpp)                                                |
 |  1425  |    Hard    | [Constrained Subsequence Sum](Problems/1425.cpp)                                                 |
 |  1438  |   Medium   | [Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit](Problems/0143.cpp)  |
+|  1443  |   Medium   | [Minimum Time to Collect All Apples in a Tree](Problems/1443.cpp)                                |
 |  1462  |   Medium   | [Course Schedule IV](Problems/1462.cpp)                                                          |
 |  1466  |   Medium   | [Reorder Routes to Make All Paths Lead to the City Zero](Problems/1466.cpp)                      |
 |  1472  |   Medium   | [Design Browser History ](Problems/1472.cpp)                                                     |