aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--apply_operations_max_score.c92
-rw-r--r--apply_operations_max_score.py72
-rw-r--r--beautiful_arrangement.c23
-rw-r--r--beautiful_arrangement.py34
-rw-r--r--brainpower.c28
-rw-r--r--brainpower.py30
-rw-r--r--check_grid_cut_section.c80
-rw-r--r--check_grid_cut_section.py60
-rw-r--r--convert_num_hex.c35
-rw-r--r--convert_num_hex.py29
-rw-r--r--count_days_without_meeting.c47
-rw-r--r--count_days_without_meeting.py37
-rw-r--r--count_num_complete_component.c73
-rw-r--r--count_num_complete_component.py48
-rw-r--r--decode_string.c114
-rw-r--r--decode_string.py43
-rw-r--r--divide_array_equal_pair.c24
-rw-r--r--divide_array_equal_pair.py26
-rw-r--r--find_kth_char_str_game2.c28
-rw-r--r--find_kth_char_str_game2.py29
-rw-r--r--house_robber4.c36
-rw-r--r--house_robber4.py45
-rw-r--r--largest_divisible_subset.c28
-rw-r--r--long_nice_subarr.c53
-rw-r--r--long_nice_subarr.py31
-rw-r--r--low_common_ancestor_leaf.c49
-rw-r--r--low_common_ancestor_leaf.py48
-rw-r--r--marbles_in_bags.c28
-rw-r--r--marbles_in_bags.py33
-rw-r--r--max_candies_allocated_k_children.c32
-rw-r--r--max_candies_allocated_k_children.py34
-rw-r--r--max_num_point_grid_query.c122
-rw-r--r--max_num_point_grid_query.py49
-rw-r--r--max_value_ordered_triplet1.c28
-rw-r--r--max_value_ordered_triplet1.py32
-rw-r--r--max_value_ordered_triplet2.c28
-rw-r--r--max_value_ordered_triplet2.py32
-rw-r--r--min_cost_walk_weight_graph.py72
-rw-r--r--min_idx_valid_split.c43
-rw-r--r--min_idx_valid_split.py35
-rw-r--r--min_num_work_session.c58
-rw-r--r--min_num_work_session.py41
-rw-r--r--min_ops_bin_arr_1.c29
-rw-r--r--min_ops_bin_arr_1.py32
-rw-r--r--min_ops_uni_val_grid.c49
-rw-r--r--min_ops_uni_val_grid.py32
-rw-r--r--min_time_repair_car.c31
-rw-r--r--min_time_repair_car.py36
-rw-r--r--min_xor_sum_two_arr.c35
-rw-r--r--min_xor_sum_two_arr.py35
-rw-r--r--num_ways_arrive_dest.py69
-rw-r--r--other/min_cost_walk_weight_graph.cpp72
-rw-r--r--other/num_ways_arrive_dest.cpp62
-rw-r--r--partition_labels.c42
-rw-r--r--partition_labels.py34
-rw-r--r--shopping_offers.c122
-rw-r--r--shopping_offers.py49
-rw-r--r--sum_subset_xor.c23
-rw-r--r--sum_subset_xor.py22
-rw-r--r--total_hamming_distance.c25
-rw-r--r--total_hamming_distance.py27
-rw-r--r--zero_array_transformation2.c71
-rw-r--r--zero_array_transformation2.py41
63 files changed, 2727 insertions, 120 deletions
diff --git a/apply_operations_max_score.c b/apply_operations_max_score.c
new file mode 100644
index 0000000..166c756
--- /dev/null
+++ b/apply_operations_max_score.c
@@ -0,0 +1,92 @@
+// 2818. Apply Operations to Maximize Score
+#include "leetcode.h"
+
+/*
+ * you are given an array 'nums' of 'n' positive integers and an integer 'k'.
+ * initially, you start with a score of 1. you have to maxmise your score by
+ * applying the following operation at most 'k' times: chose any non-empty
+ * element 'x' of 'nums[l .. r]' with the highest prime score. if multiple such
+ * elements exist, choose the one with the smallest index. multiple your score
+ * 'x'. return the maximum possible score after applying at most 'k' operations.
+ * since the answer may be very large, return it module '10e9+7'
+ */
+
+static int mod = 1e9 + 7, *vals;
+
+void prime_score(int *score, int upper) {
+ memset(score, 0, upper * sizeof(int));
+ for (int i = 2; i < upper; i++)
+ if (!score[i])
+ for (int j = i; j < upper; j += i)
+ score[j] += 1;
+}
+
+long long mod_pow(long long base, long long exp, long long mod) {
+ long long res = 1;
+ while (exp) {
+ if (exp % 2 == 1)
+ res = (res * base) % mod;
+ base = (base * base) % mod;
+ exp /= 2;
+ }
+ return res;
+}
+
+int cmp(const void *a, const void *b) {
+ return vals[*(int *)b] - vals[*(int *)a];
+}
+
+int maximumScore(int *nums, int n, int k) {
+ int upper = 0;
+ for (int i = 0; i < n; i++) {
+ if (nums[i] > upper)
+ upper = nums[i];
+ }
+ upper++;
+ int *score = (int *)malloc(upper * sizeof(int));
+ int *next = (int *)malloc(n * sizeof(int));
+ int *prev = (int *)malloc(n * sizeof(int));
+ int *stack = (int *)malloc(n * sizeof(int));
+ prime_score(score, upper);
+ int top = -1, ans = 1;
+ for (int i = 0; i < n; i++) {
+ while (top >= 0 && score[nums[i]] > score[nums[stack[top]]])
+ top--;
+ prev[i] = (top >= 0) ? stack[top] : -1;
+ stack[++top] = i;
+ }
+ top = -1;
+ for (int i = n - 1; i >= 0; i--) {
+ while (top >= 0 && score[nums[i]] >= score[nums[stack[top]]])
+ top--;
+ next[i] = (top >= 0) ? stack[top] : n;
+ stack[++top] = i;
+ }
+ int *indices = (int *)malloc(n * sizeof(int));
+ for (int i = 0; i < n; i++)
+ indices[i] = i;
+ vals = nums;
+ qsort(indices, n, sizeof(int), cmp);
+ for (int i = 0; i < n && k > 0; i++) {
+ int idx = indices[i], num = nums[idx];
+ long long operations = (long long)(idx - prev[idx]) * (next[idx] - idx);
+ if (operations > k)
+ operations = k;
+ ans = (ans * mod_pow(num, operations, mod)) % mod;
+ k -= operations;
+ if (!k)
+ break;
+ }
+ free(score);
+ free(next);
+ free(prev);
+ free(stack);
+ free(indices);
+ return ans;
+}
+
+int main() {
+ int n1[] = {8, 3, 9, 3, 8}, n2[] = {19, 12, 14, 6, 10, 18};
+ printf("%d\n", maximumScore(n1, ARRAY_SIZE(n1), 2)); // expect: 81
+ printf("%d\n", maximumScore(n2, ARRAY_SIZE(n2), 3)); // expect: 4788
+}
diff --git a/apply_operations_max_score.py b/apply_operations_max_score.py
new file mode 100644
index 0000000..d0834de
--- /dev/null
+++ b/apply_operations_max_score.py
@@ -0,0 +1,72 @@
+# 2818. Apply Operations to Maximize Score
+
+"""
+you are given an array 'nums' of 'n' positive integers and an integer 'k'.
+initially, you start with a score of 1. you have to maxmise your score by
+applying the following operation at most 'k' times: chose any non-empty
+element 'x' of 'nums[l .. r]' with the highest prime score. if multiple such
+elements exist, choose the one with the smallest index. multiple your score
+'x'. return the maximum possible score after applying at most 'k' operations.
+since the answer may be very large, return it module '10e9+7'
+"""
+
+
+class Solution(object):
+ mod = 10**9 + 7
+
+ def mod_pow(self, x, n):
+ res = 1
+ while n > 0:
+ if n % 2 == 1:
+ res = (res * x) % self.mod
+ x = (x * x) % self.mod
+ n //= 2
+ return res
+
+ def maximumScore(self, nums, k):
+ """
+ :type nums: List[int]
+ :type k: int
+ :rtype: int
+ """
+ n = len(nums)
+ upper = max(nums) + 1
+ prime = [True] * upper
+ prime[0] = prime[1] = False
+ score = [0] * upper
+ for i in range(2, upper):
+ if prime[i]:
+ for j in range(i, upper, i):
+ score[j] += 1
+ prime[j] = False
+ next, stk = [n] * n, []
+ for i in range(n - 1, -1, -1):
+ while stk and score[nums[i]] >= score[nums[stk[-1]]]:
+ stk.pop()
+ next[i] = stk[-1] if stk else n
+ stk.append(i)
+ prev, stk = [-1] * n, []
+ for i in range(n):
+ while stk and score[nums[i]] > score[nums[stk[-1]]]:
+ stk.pop()
+ prev[i] = stk[-1] if stk else -1
+ stk.append(i)
+ ans = 1
+ tuples = [[nums[i], i] for i in range(n)]
+ tuples.sort(reverse=True)
+ for num, idx in tuples:
+ operations = min(
+ (idx - prev[idx]) * (next[idx] - idx),
+ k,
+ )
+ ans = (ans * self.mod_pow(num, operations)) % self.mod
+ k -= operations
+ if k == 0:
+ return ans
+ return ans
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.maximumScore(nums=[8, 3, 9, 3, 8], k=2))
+ print(obj.maximumScore(nums=[19, 12, 14, 6, 10, 18], k=3))
diff --git a/beautiful_arrangement.c b/beautiful_arrangement.c
new file mode 100644
index 0000000..bc341da
--- /dev/null
+++ b/beautiful_arrangement.c
@@ -0,0 +1,23 @@
+// 526. Beautiful Arrangement
+#include "leetcode.h"
+
+/*
+ * suppose you have 'n' integers labeled 1 through 'n'. a permutation of those
+ * 'n' integers 'perm' (1-indexed) is considered a beautiful arrangement if for
+ * every 'i' ('1 <= i <= n') either of the following is true: 'perm[i]' is
+ * divisible by 'i', and 'i' is divisible by 'perm[i]'. given an integer 'n',
+ * return the number of the beautiful arrangements that you can construct.
+ */
+
+int countArrangement(int n) {
+ static int ans[12] = {8, 10, 36, 41, 132, 250,
+ 700, 750, 4010, 4237, 10680, 24679};
+ if (n < 4)
+ return n;
+ return ans[n - 4];
+}
+
+int main() {
+ printf("%d\n", countArrangement(2)); // expect: 2
+ printf("%d\n", countArrangement(1)); // expect: 1
+}
diff --git a/beautiful_arrangement.py b/beautiful_arrangement.py
new file mode 100644
index 0000000..2a10829
--- /dev/null
+++ b/beautiful_arrangement.py
@@ -0,0 +1,34 @@
+# 526. Beautiful Arrangement
+
+"""
+suppose you have 'n' integers labeled 1 through 'n'. a permutation of those
+'n' integers 'perm' (1-indexed) is considered a beautiful arrangement if for
+every 'i' ('1 <= i <= n') either of the following is true: 'perm[i]' is
+divisible by 'i', and 'i' is divisible by 'perm[i]'. given an integer 'n',
+return the number of the beautiful arrangements that you can construct.
+"""
+
+
+class Solution(object):
+ def countArrangement(self, n):
+ """
+ :type n: int
+ :rtype: int
+ """
+
+ def dfs(mask, place):
+ if place == 0:
+ return 1
+ res = 0
+ for i in range(n):
+ if not mask & 1 << i and ((i + 1) % place == 0 or place % (i + 1) == 0):
+ res += dfs(mask ^ 1 << i, place - 1)
+ return res
+
+ return dfs(0, n)
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.countArrangement(n=2))
+ print(obj.countArrangement(n=1))
diff --git a/brainpower.c b/brainpower.c
index dc414bb..5bff250 100644
--- a/brainpower.c
+++ b/brainpower.c
@@ -1,7 +1,5 @@
// 2140. Solving Questions With Brainpower
-#include <math.h>
-#include <stdio.h>
-#include <stdlib.h>
+#include "leetcode.h"
/*
* given a 0-indexed 2d integer array 'questions' where 'questions[i] =
@@ -11,15 +9,14 @@
* will earn you 'pointsi' points, but you will be unable to solve each of the
* next 'brainpoweri' questions. if you skip question 'i', yo get to make the
* decision on the next question. return maximum points you can score.
- *
*/
-long long mostPoints(int **questions, int questions_size,
- int *questions_col_size) {
- long long *dp = malloc((questions_size + 1) * sizeof(long long));
- dp[questions_size] = 0;
- for (int i = questions_size - 1; i >= 0; i--) {
- int k = fmin(i + questions[i][1] + 1, questions_size);
+long long mostPoints(int **questions, int questionsSize,
+ int *questionsColSize) {
+ long long *dp = (long long *)malloc((questionsSize + 1) * sizeof(long long));
+ dp[questionsSize] = 0;
+ for (int i = questionsSize - 1; i >= 0; i--) {
+ int k = fmin(i + questions[i][1] + 1, questionsSize);
dp[i] = fmax(questions[i][0] + dp[k], dp[i + 1]);
}
long long ans = dp[0];
@@ -28,8 +25,11 @@ long long mostPoints(int **questions, int questions_size,
}
int main() {
- int q1[4][2] = {{3, 2}, {4, 3}, {4, 4}, {2, 5}}, qs1 = 4, qcs1[] = {};
- int q2[5][2] = {{1, 1}, {2, 2}, {3, 3}, {4, 4}, {5, 5}}, qs2 = 5, qcs2[] = {};
- printf("%lld\n", mostPoints(q1, qs1, qcs1)); // expect: 5
- printf("%lld\n", mostPoints(q2, qs2, qcs2)); // expect: 7
+ int q1i[4][2] = {{3, 2}, {4, 3}, {4, 4}, {2, 5}},
+ q2i[5][2] = {{1, 1}, {2, 2}, {3, 3}, {4, 4}, {5, 5}};
+ struct two_d_arr q1, q2;
+ two_d_arr_init(&q1, ARRAY_SIZE(q1i), ARRAY_SIZE(q1i[0]), q1i);
+ two_d_arr_init(&q2, ARRAY_SIZE(q2i), ARRAY_SIZE(q2i[0]), q2i);
+ printf("%lld\n", mostPoints(q1.arr, q1.row_size, q1.col_size)); // expect: 5
+ printf("%lld\n", mostPoints(q2.arr, q2.row_size, q2.col_size)); // expect: 7
}
diff --git a/brainpower.py b/brainpower.py
new file mode 100644
index 0000000..24c149c
--- /dev/null
+++ b/brainpower.py
@@ -0,0 +1,30 @@
+# 2140. Solving Questions With Brainpower
+
+"""
+given a 0-indexed 2d integer array 'questions' where 'questions[i] =
+[pointsi, brainpoweri]'. the array describes the questions of an exam, where
+you have to process the questions in order (ie starting from question 0) and
+make a decision whether to solve or skip each question. solving question 'i'
+will earn you 'pointsi' points, but you will be unable to solve each of the
+next 'brainpoweri' questions. if you skip question 'i', yo get to make the
+decision on the next question. return maximum points you can score.
+"""
+
+
+class Solution(object):
+ def mostPoints(self, questions):
+ """
+ :type questions: List[List[int]]
+ :rtype: int
+ """
+ dp = [0] * (len(questions) + 1)
+ for i in range(len(questions) - 1, -1, -1):
+ points, jump = questions[i][0], questions[i][1]
+ dp[i] = max(points + dp[min(jump + i + 1, len(questions))], dp[i + 1])
+ return dp[0]
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.mostPoints(questions=[[3, 2], [4, 3], [4, 4], [2, 5]]))
+ print(obj.mostPoints(questions=[[1, 1], [2, 2], [3, 3], [4, 4], [5, 5]]))
diff --git a/check_grid_cut_section.c b/check_grid_cut_section.c
new file mode 100644
index 0000000..2884222
--- /dev/null
+++ b/check_grid_cut_section.c
@@ -0,0 +1,80 @@
+// 3394. Check if Grid can be Cut into Sections
+#include "leetcode.h"
+
+/*
+ * you are given an integer 'n' representing the dimensions of an 'n * n' grid
+ * with the origin at the bottom-left corner of the grid. you are also given a
+ * 2d array of coordinates 'rectangles', where 'rectangles[i]' is in the form
+ * '[start_x, start_y, end_x, end_y]' representing a rectangle on the grid. note
+ * that the rectangles do not overlap. your task is to determine if it is
+ * possible to make either two horizontal or two vertical cuts on the grid such
+ * that each of the three resulting formed by the cuts contains at least one
+ * rectangle. every rectangle belongs to exactly one section. return 'true' if
+ * such cuts can be made. otherwise, return 'false'.
+ */
+
+int cmp_y(const void *a, const void *b) {
+ int *aa = *(int **)a, *bb = *(int **)b;
+ return aa[1] - bb[1];
+}
+
+int cmp_x(const void *a, const void *b) {
+ int *aa = *(int **)a, *bb = *(int **)b;
+ return aa[0] - bb[0];
+}
+
+bool check_x(int n, int **rectangles, int rectanglesSize) {
+ qsort(rectangles, rectanglesSize, sizeof(int *), cmp_y);
+ int intervals = 1, curr[2] = {rectangles[0][1], rectangles[0][3]};
+ for (int i = 1; i < rectanglesSize; i++) {
+ if (rectangles[i][1] >= curr[1]) {
+ if (++intervals == 3)
+ return true;
+ curr[0] = rectangles[i][1];
+ curr[1] = rectangles[i][3];
+ } else if (rectangles[i][3] > curr[1])
+ curr[1] = rectangles[i][3];
+ }
+ return false;
+}
+
+bool check_y(int n, int **rectangles, int rectanglesSize) {
+ qsort(rectangles, rectanglesSize, sizeof(int *), cmp_x);
+ int intervals = 1, curr[2] = {rectangles[0][0], rectangles[0][2]};
+ for (int i = 1; i < rectanglesSize; i++) {
+ if (rectangles[i][0] >= curr[1]) {
+ if (++intervals == 3)
+ return true;
+ curr[0] = rectangles[i][0];
+ curr[1] = rectangles[i][2];
+ } else if (rectangles[i][2] > curr[1])
+ curr[1] = rectangles[i][2];
+ }
+ return false;
+}
+
+bool checkValidCuts(int n, int **rectangles, int rectanglesSize,
+ int *rectanglesColSize) {
+ return check_y(n, rectangles, rectanglesSize) ||
+ check_x(n, rectangles, rectanglesSize);
+}
+
+int main() {
+ int r1i[4][4] = {{1, 0, 5, 2}, {0, 2, 2, 4}, {3, 2, 5, 3}, {0, 4, 4, 5}};
+ int r2i[4][4] = {{0, 0, 1, 1}, {2, 0, 3, 4}, {0, 2, 2, 3}, {3, 0, 4, 3}};
+ int r3i[5][4] = {
+ {0, 2, 2, 4}, {1, 0, 3, 2}, {2, 2, 3, 4}, {3, 0, 4, 2}, {3, 2, 4, 4}};
+ struct two_d_arr r1, r2, r3;
+ two_d_arr_init(&r1, ARRAY_SIZE(r1i), ARRAY_SIZE(r1i[0]), r1i);
+ two_d_arr_init(&r2, ARRAY_SIZE(r2i), ARRAY_SIZE(r2i[0]), r2i);
+ two_d_arr_init(&r3, ARRAY_SIZE(r3i), ARRAY_SIZE(r3i[0]), r3i);
+ printf("%d\n",
+ checkValidCuts(5, r1.arr, r1.row_size, r1.col_size)); // expect: 1
+ printf("%d\n",
+ checkValidCuts(4, r2.arr, r2.row_size, r2.col_size)); // expect: 1
+ printf("%d\n",
+ checkValidCuts(4, r3.arr, r3.row_size, r3.col_size)); // expect: 0
+ two_d_arr_free(&r1);
+ two_d_arr_free(&r2);
+ two_d_arr_free(&r3);
+}
diff --git a/check_grid_cut_section.py b/check_grid_cut_section.py
new file mode 100644
index 0000000..b2869f7
--- /dev/null
+++ b/check_grid_cut_section.py
@@ -0,0 +1,60 @@
+# 3394. Check if Grid can be Cut into Sections
+
+"""
+you are given an integer 'n' representing the dimensions of an 'n n' grid
+with the origin at the bottom-left corner of the grid. you are also given a
+2d array of coordinates 'rectangles', where 'rectangles[i]' is in the form
+'[start_x, start_y, end_x, end_y]' representing a rectangle on the grid. note
+that the rectangles do not overlap. your task is to determine if it is
+possible to make either two horizontal or two vertical cuts on the grid such
+that each of the three resulting formed by the cuts contains at least one
+rectangle. every rectangle belongs to exactly one section. return 'true' if
+such cuts can be made. otherwise, return 'false'.
+"""
+
+
+class Solution(object):
+ def checkValidCuts(self, n, rectangles):
+ """
+ :type n: int
+ :type rectangles: List[List[int]]
+ :rtype: bool
+ """
+
+ def check(rectangles):
+ rectangles.sort()
+ res, pre = 0, rectangles[0][1]
+ for i, j in rectangles:
+ res += pre <= i
+ pre = max(pre, j)
+ return res > 1
+
+ return check([i[::2] for i in rectangles]) or check(
+ [i[1::2] for i in rectangles]
+ )
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(
+ obj.checkValidCuts(
+ n=5, rectangles=[[1, 0, 5, 2], [0, 2, 2, 4], [3, 2, 5, 3], [0, 4, 4, 5]]
+ )
+ )
+ print(
+ obj.checkValidCuts(
+ n=4, rectangles=[[0, 0, 1, 1], [2, 0, 3, 4], [0, 2, 2, 3], [3, 0, 4, 3]]
+ )
+ )
+ print(
+ obj.checkValidCuts(
+ n=4,
+ rectangles=[
+ [0, 2, 2, 4],
+ [1, 0, 3, 2],
+ [2, 2, 3, 4],
+ [3, 0, 4, 2],
+ [3, 2, 4, 4],
+ ],
+ )
+ )
diff --git a/convert_num_hex.c b/convert_num_hex.c
new file mode 100644
index 0000000..421706b
--- /dev/null
+++ b/convert_num_hex.c
@@ -0,0 +1,35 @@
+// 405. Convert a Number to Hexadecimal
+#include "leetcode.h"
+
+/*
+ * given a 32 bit integer 'num', return a string representing its hexadecimal
+ * representation. for negative integers, two's complement method is used. all
+ * the letters in the answer string should be lowercase characters, nd there not
+ * be any leading zeros in the answer except for the zero itself. note: you are
+ * not allowed to use any built-in library method to directly solve this
+ * problem.
+ */
+
+char *toHex(int num) {
+ char *ans = (char *)malloc(sizeof(char) * 10), step;
+ uint x = num, i = 0;
+ ans[9] = '\0';
+ while (1) {
+ step = x & 0xF;
+ ans[8 - i] = step > 9 ? 'a' + step - 10 : '0' + step;
+ x >>= 4;
+ if (!x)
+ break;
+ i++;
+ }
+ return &ans[8 - i];
+}
+
+int main() {
+ char *th1 = toHex(26);
+ char *th2 = toHex(-1);
+ printf("%s\n", th1); // expect: 1a
+ printf("%s\n", th2); // expect: ffffffff
+ free(th1);
+ free(th2);
+}
diff --git a/convert_num_hex.py b/convert_num_hex.py
new file mode 100644
index 0000000..65ca796
--- /dev/null
+++ b/convert_num_hex.py
@@ -0,0 +1,29 @@
+# 405. Convert a Number to Hexadecimal
+
+"""
+given a 32 bit integer 'num', return a string representing its hexadecimal
+representation. for negative integers, two's complement method is used. all
+the letters in the answer string should be lowercase characters, nd there not
+be any leading zeros in the answer except for the zero itself. note: you are
+not allowed to use any built-in library method to directly solve this
+problem.
+"""
+
+
+class Solution(object):
+ def toHex(self, num):
+ """
+ :type num: int
+ :rtype: str
+ """
+ map, ans, num = "0123456789abcdef", "", num & 0xFFFFFFFF
+ while num:
+ ans += map[num % 16]
+ num >>= 4
+ return ans[::-1] or "0"
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.toHex(num=26))
+ print(obj.toHex(num=-1))
diff --git a/count_days_without_meeting.c b/count_days_without_meeting.c
new file mode 100644
index 0000000..9e1ff35
--- /dev/null
+++ b/count_days_without_meeting.c
@@ -0,0 +1,47 @@
+// 3169. Count Days Without Meetings
+#include "leetcode.h"
+
+/*
+ * you are given a positive integer 'days' representing the total number of days
+ * an employee is available for work (starting from day 1). you are given a 2d
+ * integer array 'meetings' of size 'n' where 'meetings[i] = [start_i, end_i]'
+ * represents the starting and ending days of meeting 'i' (inclusive). return
+ * the count of days when the employee is available for work, but no meetings
+ * are scheduled.
+ */
+
+int cmp(const void *a, const void *b) {
+ int *aa = *(int **)a, *bb = *(int **)b;
+ return aa[0] == bb[0] ? aa[1] - bb[1] : aa[0] - bb[0];
+}
+
+int countDays(int days, int **meetings, int meetingsSize,
+ int *meetingsColSize) {
+ qsort(meetings, meetingsSize, sizeof(int *), cmp);
+ int idx = 0, start = meetings[idx][0], end = meetings[idx++][1];
+ while (idx < meetingsSize) {
+ if (meetings[idx][0] > end) {
+ days -= (end - start + 1);
+ start = meetings[idx][0];
+ end = meetings[idx][1];
+ } else
+ end = end > meetings[idx][1] ? end : meetings[idx][1];
+ ++idx;
+ }
+ return days - (end - start + 1);
+}
+
+int main() {
+ int m1i[3][2] = {{5, 7}, {1, 3}, {9, 10}}, m2i[2][2] = {{2, 4}, {1, 3}},
+ m3i[1][2] = {{1, 6}};
+ struct two_d_arr m1, m2, m3;
+ two_d_arr_init(&m1, ARRAY_SIZE(m1i), ARRAY_SIZE(m1i[0]), m1i);
+ two_d_arr_init(&m2, ARRAY_SIZE(m2i), ARRAY_SIZE(m2i[0]), m2i);
+ two_d_arr_init(&m3, ARRAY_SIZE(m3i), ARRAY_SIZE(m3i[0]), m3i);
+ printf("%d\n", countDays(10, m1.arr, m1.row_size, m1.col_size)); // expect: 2
+ printf("%d\n", countDays(5, m2.arr, m2.row_size, m2.col_size)); // expect: 1
+ printf("%d\n", countDays(6, m3.arr, m3.row_size, m3.col_size)); // expect: 0
+ two_d_arr_free(&m1);
+ two_d_arr_free(&m2);
+ two_d_arr_free(&m3);
+}
diff --git a/count_days_without_meeting.py b/count_days_without_meeting.py
new file mode 100644
index 0000000..c1cee7d
--- /dev/null
+++ b/count_days_without_meeting.py
@@ -0,0 +1,37 @@
+# 3169. Count Days Without Meetings
+
+"""
+you are given a positive integer 'days' representing the total number of days
+an employee is available for work (starting from day 1). you are given a 2d
+integer array 'meetings' of size 'n' where 'meetings[i] = [start_i, end_i]'
+represents the starting and ending days of meeting 'i' (inclusive). return
+the count of days when the employee is available for work, but no meetings
+are scheduled.
+"""
+
+
+class Solution(object):
+ def countDays(self, days, meetings):
+ """
+ :type days: int
+ :type meetings: List[List[int]]
+ :rtype: int
+ """
+ meetings.sort(key=lambda x: x[0])
+ cnt, n = abs(meetings[0][0] - 1), len(meetings)
+ for i in range(1, n):
+ if meetings[i][0] <= meetings[i - 1][1]:
+ if meetings[i][1] < meetings[i - 1][1]:
+ meetings[i][1] = meetings[i - 1][1]
+ else:
+ day = meetings[i][0] - meetings[i - 1][1]
+ cnt += day - 1
+ cnt += abs(meetings[n - 1][1] - days)
+ return cnt
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.countDays(days=10, meetings=[[5, 7], [1, 3], [9, 10]]))
+ print(obj.countDays(days=5, meetings=[[2, 4], [1, 3]]))
+ print(obj.countDays(days=6, meetings=[[1, 6]]))
diff --git a/count_num_complete_component.c b/count_num_complete_component.c
new file mode 100644
index 0000000..a6ede23
--- /dev/null
+++ b/count_num_complete_component.c
@@ -0,0 +1,73 @@
+// 2685. Count the Number of Complete Components
+#include "leetcode.h"
+
+/*
+ * you are given an integer 'n'. there is an undirected graph with 'n' vertices,
+ * numbered from 0 to 'n - 1'. you are given a 2d integer array 'edges' where
+ * 'edges[i] = [a_i, b_i]' denotes that there exists an undirected edge
+ * connecting vertices 'a_i' and 'b_i'. return the number of complete connected
+ * components of the graph. a connected component is a subgraph of a graph in
+ * which there exists a path between any two vertices and no vertex of the
+ * subgraph shares an edge with a vertex outside of the subgraph. a connected
+ * component is said to be complete if there exists an edge between every pair
+ * of its vertices
+ */
+
+int countCompleteComponents(int n, int **edges, int edgesSize,
+ int *edgesColSize) {
+ int *vertices = (int *)calloc(n, sizeof(int));
+ int *edge_cnt = (int *)calloc(n, sizeof(int));
+ int *vert_cnt = (int *)calloc(n, sizeof(int));
+ int group = 1, ans = 0;
+ for (int i = 0; i < edgesSize; i++) {
+ int v1 = edges[i][0];
+ int v2 = edges[i][1];
+ if (!(vertices[v1] + vertices[v2])) {
+ vertices[v1] = vertices[v2] = group;
+ edge_cnt[group] = 2;
+ vert_cnt[group++] = 1;
+ } else if (!vertices[v1]) {
+ vertices[v1] = vertices[v2];
+ ++edge_cnt[vertices[v2]];
+ ++vert_cnt[vertices[v2]];
+ } else if (!vertices[v2]) {
+ vertices[v2] = vertices[v1];
+ ++edge_cnt[vertices[v1]];
+ ++vert_cnt[vertices[v1]];
+ } else if (vertices[v1] == vertices[v2])
+ ++vert_cnt[vertices[v1]];
+ else {
+ vert_cnt[vertices[v1]] += vert_cnt[vertices[v2]] + 1;
+ edge_cnt[vertices[v1]] += edge_cnt[vertices[v2]];
+ edge_cnt[vertices[v2]] = vert_cnt[vertices[v2]] = 0;
+ for (int i = 0; i < n; i++)
+ if (vertices[i] == vertices[v2])
+ vertices[i] = vertices[v1];
+ }
+ }
+ int connect_cnt = 0;
+ for (int i = 1; i < group; i++) {
+ int edges = edge_cnt[i], verts = vert_cnt[i];
+ if (edges && (edges * (edges - 1) / 2 == verts))
+ ++ans;
+ connect_cnt += edges;
+ }
+ free(vert_cnt);
+ free(edge_cnt);
+ free(vertices);
+ return ans + (n - connect_cnt);
+}
+
+int main() {
+ int e1i[4][2] = {{0, 1}, {0, 2}, {1, 2}, {3, 4}},
+ e2i[5][2] = {{0, 1}, {0, 2}, {1, 2}, {3, 4}, {3, 5}};
+ struct two_d_arr e1, e2;
+ two_d_arr_init(&e1, ARRAY_SIZE(e1i), ARRAY_SIZE(e1i[0]), e1i);
+ two_d_arr_init(&e2, ARRAY_SIZE(e2i), ARRAY_SIZE(e2i[0]), e2i);
+ printf("%d\n", countCompleteComponents(6, e1.arr, e1.row_size,
+ e1.col_size)); // expect: 3
+ printf("%d\n", countCompleteComponents(6, e2.arr, e2.row_size,
+ e2.col_size)); // expect: 1
+ two_d_arr_free(&e1);
+ two_d_arr_free(&e2);
+}
diff --git a/count_num_complete_component.py b/count_num_complete_component.py
new file mode 100644
index 0000000..6b8a592
--- /dev/null
+++ b/count_num_complete_component.py
@@ -0,0 +1,48 @@
+# 2685. Count the Number of Complete Components
+
+"""
+you are given an integer 'n'. there is an undirected graph with 'n' vertices,
+numbered from 0 to 'n - 1'. you are given a 2d integer array 'edges' where
+'edges[i] = [a_i, b_i]' denotes that there exists an undirected edge
+connecting vertices 'a_i' and 'b_i'. return the number of complete connected
+components of the graph. a connected component is a subgraph of a graph in
+which there exists a path between any two vertices and no vertex of the
+subgraph shares an edge with a vertex outside of the subgraph. a connected
+component is said to be complete if there exists an edge between every pair
+of its vertices
+"""
+
+
+class Solution(object):
+ def countCompleteComponents(self, n, edges):
+ """
+ :type n: int
+ :type edges: List[List[int]]
+ :rtype: int
+ """
+ graph = [[] for _ in range(n)]
+ for i, j in edges:
+ graph[i].append(j)
+ graph[j].append(i)
+ vis, ans = [False] * n, 0
+ for i in range(n):
+ if vis[i]:
+ continue
+ bfs = [i]
+ vis[i] = True
+ for j in bfs:
+ for k in graph[j]:
+ if not vis[k]:
+ bfs.append(k)
+ vis[k] = True
+ if all(len(graph[j]) == len(bfs) - 1 for j in bfs):
+ ans += 1
+ return ans
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.countCompleteComponents(n=6, edges=[[0, 1], [0, 2], [1, 2], [3, 4]]))
+ print(
+ obj.countCompleteComponents(n=6, edges=[[0, 1], [0, 2], [1, 2], [3, 4], [3, 5]])
+ )
diff --git a/decode_string.c b/decode_string.c
new file mode 100644
index 0000000..c476cb9
--- /dev/null
+++ b/decode_string.c
@@ -0,0 +1,114 @@
+// 394. Decode String
+#include "leetcode.h"
+
+/*
+ * given an encoded string, return its decoded string. the encoding rule is
+ * 'k[encoded_string]' where the 'encoded_string' inside the square brackets is
+ * being repeated exactly 'k' times. note that 'k' is guaranteed to be a
+ * positive integer. you may assume that the input string is always valid; there
+ * are no extra white spaces, square brackets are well-formed, etc. furthermore,
+ * you may assume that the original data does not contain any digits, and that
+ * digits are only for those repeat numbers, 'k'. the test cases are generated
+ * such that the output will never exceed '10^5'.
+ */
+
+struct node_time {
+ int times;
+ struct node_time *next;
+};
+
+struct node_char {
+ char c;
+ struct node_char *next;
+};
+
+void push_int(struct node_time **head, int val) {
+ struct node_time *new = (struct node_time *)malloc(sizeof(struct node_time));
+ new->times = val;
+ new->next = *head;
+ *head = new;
+}
+
+void push_char(struct node_char **head, char c) {
+ struct node_char *new = (struct node_char *)malloc(sizeof(struct node_char));
+ new->c = c;
+ new->next = *head;
+ *head = new;
+}
+
+int pop_int(struct node_time **head) {
+ struct node_time *tmp = *head;
+ int res = tmp->times;
+ *head = (*head)->next;
+ free(tmp);
+ return res;
+}
+
+char pop_char(struct node_char **head) {
+ struct node_char *tmp = *head;
+ char res = tmp->c;
+ *head = (*head)->next;
+ free(tmp);
+ return res;
+}
+
+int word_size(struct node_char *head) {
+ int n = 0;
+ while (head) {
+ if (head->c == '[')
+ break;
+ n++;
+ head = head->next;
+ }
+ return n;
+}
+
+char *decodeString(char *s) {
+ struct node_time *int_stk = NULL;
+ struct node_char *char_stk = NULL;
+ int i = 0, n, k;
+ while (s[i]) {
+ if (s[i] >= '0' && s[i] <= '9') {
+ int num = atoi(&s[i]);
+ while (s[i] >= '0' && s[i] <= '9')
+ i++;
+ push_int(&int_stk, num);
+ } else if (s[i] > '9' && s[i] != ']') {
+ push_char(&char_stk, s[i]);
+ i++;
+ } else if (s[i] == '[') {
+ push_char(&char_stk, '[');
+ i++;
+ } else if (s[i] == ']') {
+ n = word_size(char_stk);
+ int times = pop_int(&int_stk);
+ char *word = (char *)malloc(n * sizeof(char));
+ for (k = 0; k < n; k++)
+ word[k] = pop_char(&char_stk);
+ pop_char(&char_stk);
+ for (; times; times--)
+ for (k = n - 1; k >= 0; k--)
+ push_char(&char_stk, word[k]);
+ free(word);
+ i++;
+ }
+ }
+ n = word_size(char_stk);
+ char *ans = (char *)calloc(n + 1, sizeof(char));
+ for (k = n - 1; k >= 0; k--)
+ ans[k] = pop_char(&char_stk);
+ return ans;
+}
+
+int main() {
+ char *s1 = "3[a]2[bc]", *s2 = "3[a2[c]]", *s3 = "2[abc]3[cd]ef";
+ char *ds1 = decodeString(s1);
+ char *ds2 = decodeString(s2);
+ char *ds3 = decodeString(s3);
+ printf("%s\n", ds1); // expect: aaabcbc
+ printf("%s\n", ds2); // expect: accaccacc
+ printf("%s\n", ds2); // expect: abcabccdcdcdef
+ free(ds1);
+ free(ds2);
+ free(ds3);
+}
diff --git a/decode_string.py b/decode_string.py
new file mode 100644
index 0000000..e62c5b0
--- /dev/null
+++ b/decode_string.py
@@ -0,0 +1,43 @@
+# 394. Decode String
+
+"""
+given an encoded string, return its decoded string. the encoding rule is
+'k[encoded_string]' where the 'encoded_string' inside the square brackets is
+being repeated exactly 'k' times. note that 'k' is guaranteed to be a
+positive integer. you may assume that the input string is always valid; there
+are no extra white spaces, square brackets are well-formed, etc. furthermore,
+you may assume that the original data does not contain any digits, and that
+digits are only for those repeat numbers, 'k'. the test cases are generated
+such that the output will never exceed '10^5'.
+"""
+
+
+class Solution(object):
+ def decodeString(self, s):
+ """
+ :type s: str
+ :rtype: str
+ """
+ stk, curr_int, curr_str = [], 0, ""
+ for c in s:
+ if c == "[":
+ stk.append(curr_str)
+ stk.append(curr_int)
+ curr_str = ""
+ curr_int = 0
+ elif c == "]":
+ num = stk.pop()
+ prev_str = stk.pop()
+ curr_str = prev_str + num * curr_str
+ elif c.isdigit():
+ curr_int = curr_int * 10 + int(c)
+ else:
+ curr_str += c
+ return curr_str
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.decodeString(s="3[a]2[bc]"))
+ print(obj.decodeString(s="3[a2[c]]"))
+ print(obj.decodeString(s="2[abc]3[cd]ef"))
diff --git a/divide_array_equal_pair.c b/divide_array_equal_pair.c
new file mode 100644
index 0000000..cc98130
--- /dev/null
+++ b/divide_array_equal_pair.c
@@ -0,0 +1,24 @@
+// 2206. Divide Array Into Equal Pairs
+#include "leetcode.h"
+
+/*
+ * you are given an integer array 'nums' consisting of '2 * n' integers. you
+ * need to divide 'nums' into 'n' pairs such that: each element belongs to
+ * exactly one pair, and the elements present in a pair are equal. return true
+ * if 'nums' can be divided into 'n' pairs, otherwise return false.
+ */
+
+bool divideArray(int *nums, int numsSize) {
+ int x1 = 0, x2 = 0;
+ for (int i = 0; i < numsSize; i++) {
+ x1 ^= nums[i];
+ x2 ^= nums[i] + 1;
+ }
+ return !x1 && !x2;
+}
+
+int main() {
+ int n1[] = {3, 2, 3, 2, 2, 2}, n2[] = {1, 2, 3, 4};
+ printf("%d\n", divideArray(n1, ARRAY_SIZE(n1))); // expect: 1
+ printf("%d\n", divideArray(n2, ARRAY_SIZE(n2))); // expect: 0
+}
diff --git a/divide_array_equal_pair.py b/divide_array_equal_pair.py
new file mode 100644
index 0000000..7555627
--- /dev/null
+++ b/divide_array_equal_pair.py
@@ -0,0 +1,26 @@
+# 2206. Divide Array Into Equal Pairs
+
+"""
+you are given an integer array 'nums' consisting of '2 n' integers. you
+need to divide 'nums' into 'n' pairs such that: each element belongs to
+exactly one pair, and the elements present in a pair are equal. return true
+if 'nums' can be divided into 'n' pairs, otherwise return false.
+"""
+
+
+class Solution(object):
+ def divideArray(self, nums):
+ """
+ :type nums: List[int]
+ :rtype: bool
+ """
+ vis = set()
+ for i in nums:
+ vis ^= {i}
+ return not vis
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.divideArray(nums=[3, 2, 3, 2, 2, 2]))
+ print(obj.divideArray(nums=[1, 2, 3, 4]))
diff --git a/find_kth_char_str_game2.c b/find_kth_char_str_game2.c
new file mode 100644
index 0000000..08202e6
--- /dev/null
+++ b/find_kth_char_str_game2.c
@@ -0,0 +1,28 @@
+// 3307. Find the K-th Character in String Game II
+#include "leetcode.h"
+
+/*
+ * alice and bob are playing a game. initially, alice has a string 'word = "a"'.
+ * you are given a positive integer 'k'. you are also given an integer array
+ * 'operations' where 'operations[i]' represents the type of i'th operation. now
+ * bob will ask alice to perform all operations in sequence: if 'operations[i]
+ * == 0', append a copy of 'word' to itself. if 'operations[i] == 1', generate a
+ * new string by changing each character in 'word' to its next character in the
+ * english alphabet, and append it to the origin 'word'. return the value of the
+ * k'th character in 'word' after performing all the operations.
+ */
+
+char kthCharacter(long long k, int *operations, int operationsSize) {
+ int ans = 0;
+ k--;
+ for (int i = 0; i < operationsSize && i < 60; ++i)
+ if ((k >> i) % 2)
+ ans += operations[i];
+ return (char)('a' + ans % 26);
+}
+
+int main() {
+ int o1[] = {0, 0, 0}, o2[] = {0, 1, 0, 1};
+ printf("%c\n", kthCharacter(5, o1, ARRAY_SIZE(o1))); // expect: a
+ printf("%c\n", kthCharacter(10, o2, ARRAY_SIZE(o2))); // expect: b
+}
diff --git a/find_kth_char_str_game2.py b/find_kth_char_str_game2.py
new file mode 100644
index 0000000..118641e
--- /dev/null
+++ b/find_kth_char_str_game2.py
@@ -0,0 +1,29 @@
+# 3307. Find the K-th Character in String Game II
+
+"""
+alice and bob are playing a game. initially, alice has a string 'word = "a"'.
+you are given a positive integer 'k'. you are also given an integer array
+'operations' where 'operations[i]' represents the type of i'th operation. now
+bob will ask alice to perform all operations in sequence: if 'operations[i]
+== 0', append a copy of 'word' to itself. if 'operations[i] == 1', generate a
+new string by changing each character in 'word' to its next character in the
+english alphabet, and append it to the origin 'word'. return the value of the
+k'th character in 'word' after performing all the operations.
+"""
+
+
+class Solution(object):
+ def kthCharacter(self, k, operations):
+ """
+ :type k: int
+ :type operations: List[int]
+ :rtype: str
+ """
+ ans = (k - 1) & sum(v << i for i, v in enumerate(operations))
+ return chr(ord("a") + ans.bit_count() % 26)
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.kthCharacter(k=5, operations=[0, 0, 0]))
+ print(obj.kthCharacter(k=10, operations=[0, 1, 0, 1]))
diff --git a/house_robber4.c b/house_robber4.c
new file mode 100644
index 0000000..2e1c6e3
--- /dev/null
+++ b/house_robber4.c
@@ -0,0 +1,36 @@
+// 2560. House Robber IV
+#include "leetcode.h"
+
+/*
+ * there are several consecutive houses along a street, each of which has some
+ * money inside. there is also a robber, who wants to steal money from the
+ * homes, but he refuses to steal from adjacent homes. the capability of the
+ * robber is the maximum amount of money he steals from one house of all the
+ * houses he robbed. you are given an integer array 'nums' representing how much
+ * money is stahsed in each house. more formally, the i'th house from the left
+ * has 'nums[i]' dollars. you are also given an integer 'k', representing the
+ * minimum number of houses the robber will steal from. it is always possible to
+ * steal at least 'k' houses. return the minimum possible capability of the
+ * robber out of all the possible ways to steal at least 'k' houses.
+ */
+
+int minCapability(int *nums, int numsSize, int k) {
+ int left = 1, right = 1e9;
+ while (left < right) {
+ int mid = (left + right) / 2, take = 0;
+ for (int i = 0; i < numsSize; i++)
+ if (nums[i] <= mid)
+ take++, i++;
+ if (take >= k)
+ right = mid;
+ else
+ left = mid + 1;
+ }
+ return left;
+}
+
+int main() {
+ int n1[] = {2, 3, 5, 9}, n2[] = {2, 7, 9, 3, 1};
+ printf("%d\n", minCapability(n1, ARRAY_SIZE(n1), 2)); // expect: 5
+ printf("%d\n", minCapability(n2, ARRAY_SIZE(n2), 2)); // expect: 2
+}
diff --git a/house_robber4.py b/house_robber4.py
new file mode 100644
index 0000000..a8fb361
--- /dev/null
+++ b/house_robber4.py
@@ -0,0 +1,45 @@
+# 2560. House Robber IV
+
+"""
+there are several consecutive houses along a street, each of which has some
+money inside. there is also a robber, who wants to steal money from the
+homes, but he refuses to steal from adjacent homes. the capability of the
+robber is the maximum amount of money he steals from one house of all the
+houses he robbed. you are given an integer array 'nums' representing how much
+money is stahsed in each house. more formally, the i'th house from the left
+has 'nums[i]' dollars. you are also given an integer 'k', representing the
+minimum number of houses the robber will steal from. it is always possible to
+steal at least 'k' houses. return the minimum possible capability of the
+robber out of all the possible ways to steal at least 'k' houses.
+"""
+
+
+class Solution(object):
+ def minCapability(self, nums, k):
+ """
+ :type nums: List[int]
+ :type k: int
+ :rtype: int
+ """
+ left, right = min(nums), max(nums)
+ while left < right:
+ mid = (left + right) // 2
+ prev, take = 0, False
+ for i in nums:
+ if prev:
+ prev = False
+ continue
+ if i <= mid:
+ take += 1
+ prev = True
+ if take >= k:
+ right = mid
+ else:
+ left = mid + 1
+ return left
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.minCapability(nums=[2, 3, 5, 9], k=2))
+ print(obj.minCapability(nums=[2, 7, 9, 3, 1], k=2))
diff --git a/largest_divisible_subset.c b/largest_divisible_subset.c
index f540528..6d36c45 100644
--- a/largest_divisible_subset.c
+++ b/largest_divisible_subset.c
@@ -10,14 +10,14 @@
int cmp(const void *a, const void *b) { return *(int *)a - *(int *)b; }
-int *largestDivisibleSubset(int *nums, int nums_size, int *return_size) {
- qsort(nums, nums_size, sizeof(int), cmp);
- int *idx = malloc(nums_size * sizeof(int));
- int *cnt = malloc(nums_size * sizeof(int));
+int *largestDivisibleSubset(int *nums, int numsSize, int *returnSize) {
+ qsort(nums, numsSize, sizeof(int), cmp);
+ int *idx = (int *)malloc(numsSize * sizeof(int));
+ int *cnt = (int *)malloc(numsSize * sizeof(int));
int max = 1, max_idx = 0, tmp;
idx[0] = -1;
cnt[0] = 1;
- for (int i = 1; i < nums_size; i++) {
+ for (int i = 1; i < numsSize; i++) {
idx[i] = -1;
cnt[i] = 1;
for (int j = i - 1; j >= 0; j--)
@@ -33,25 +33,25 @@ int *largestDivisibleSubset(int *nums, int nums_size, int *return_size) {
max_idx = i;
}
}
- *return_size = max;
- int *ans = malloc(max * sizeof(int));
+ *returnSize = max;
+ int *ans = (int *)malloc(max * sizeof(int));
for (int i = max - 1; i >= 0; i--) {
ans[i] = nums[max_idx];
max_idx = idx[max_idx];
}
- free(idx), free(cnt);
+ free(idx);
+ free(cnt);
return ans;
}
int main() {
- int n1[] = {1, 2, 3}, n2[] = {1, 2, 4, 8};
- int rs1[] = {}, rs2[] = {};
- int *lds1 = largestDivisibleSubset(n1, ARRAY_SIZE(n1), rs1);
- int *lds2 = largestDivisibleSubset(n2, ARRAY_SIZE(n2), rs2);
- for (int i = 0; i < 2; i++)
+ int n1[] = {1, 2, 3}, n2[] = {1, 2, 4, 8}, rs1, rs2;
+ int *lds1 = largestDivisibleSubset(n1, ARRAY_SIZE(n1), &rs1);
+ int *lds2 = largestDivisibleSubset(n2, ARRAY_SIZE(n2), &rs2);
+ for (int i = 0; i < rs1; i++)
printf("%d ", lds1[i]); // expect: 1 2
printf("\n");
- for (int i = 0; i < 4; i++)
+ for (int i = 0; i < rs2; i++)
printf("%d ", lds2[i]); // expect: 1 2 4 8
printf("\n");
free(lds1), free(lds2);
diff --git a/long_nice_subarr.c b/long_nice_subarr.c
index cfa50f3..a655bbf 100644
--- a/long_nice_subarr.c
+++ b/long_nice_subarr.c
@@ -1,53 +1,28 @@
// 2401. Longest Nice Subarray
-#include <stdbool.h>
-#include <stdio.h>
-#include <stdlib.h>
+#include "leetcode.h"
/*
* given an array 'nums' consisting of positive integers. we call a subarray of
- * 'nums' nice if the bitwise AND of every pair of elements that are in
+ * 'nums' nice if the bitwise cnt of every pair of elements that are in
* different positions in the subarray is equal to 0. return the length of the
* longest nice subarray. a subarray is contiguous part of an array. note that
* subarrays of length 1 are always considered nice.
*/
-bool check(int *bit, int n) {
- for (int i = 0; i < n; i++)
- if (bit[i] > 1)
- return false;
- return true;
-}
-
-int longestNiceSubarray(int *nums, int nums_size) {
- int *bit = calloc(32, sizeof(int));
- int left = 0, right = 0;
- while (right < nums_size) {
- int k = nums[right], pos = 0;
- while (k) {
- if (k % 2 == 1)
- bit[pos]++;
- k /= 2;
- pos++;
- }
- right++;
- if (!check(bit, 32)) {
- k = nums[left];
- pos = 0;
- while (k) {
- if (k % 2 == 1)
- bit[pos]--;
- k /= 2;
- pos++;
- }
- left++;
- }
+int longestNiceSubarray(int *nums, int numsSize) {
+ int cnt = 0, i = 0, ans = 0;
+ for (int j = 0; j < numsSize; ++j) {
+ while (cnt & nums[j])
+ cnt ^= nums[i++];
+ cnt |= nums[j];
+ ans = fmax(ans, j - i + 1);
}
- return right - left;
+ return ans;
}
int main() {
- int n1[] = {1, 3, 8, 48, 10}, ns1 = 5;
- int n2[] = {3, 1, 5, 11, 13}, ns2 = 5;
- printf("%d\n", longestNiceSubarray(n1, ns1)); // expect: 3
- printf("%d\n", longestNiceSubarray(n2, ns2)); // expect: 1
+ int n1[] = {1, 3, 8, 48, 10};
+ int n2[] = {3, 1, 5, 11, 13};
+ printf("%d\n", longestNiceSubarray(n1, ARRAY_SIZE(n1))); // expect: 3
+ printf("%d\n", longestNiceSubarray(n2, ARRAY_SIZE(n2))); // expect: 1
}
diff --git a/long_nice_subarr.py b/long_nice_subarr.py
new file mode 100644
index 0000000..037743e
--- /dev/null
+++ b/long_nice_subarr.py
@@ -0,0 +1,31 @@
+# 2401. Longest Nice Subarray
+
+"""
+given an array 'nums' consisting of positive integers. we call a subarray of
+'nums' nice if the bitwise cnt of every pair of elements that are in
+different positions in the subarray is equal to 0. return the length of the
+longest nice subarray. a subarray is contiguous part of an array. note that
+subarrays of length 1 are always considered nice.
+"""
+
+
+class Solution(object):
+ def longestNiceSubarray(self, nums):
+ """
+ :type nums: List[int]
+ :rtype: int
+ """
+ cnt, i, ans = 0, 0, 0
+ for j in range(len(nums)):
+ while cnt & nums[j]:
+ cnt ^= nums[i]
+ i += 1
+ cnt |= nums[j]
+ ans = max(ans, j - i + 1)
+ return ans
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.longestNiceSubarray(nums=[1, 3, 8, 48, 10]))
+ print(obj.longestNiceSubarray(nums=[3, 1, 5, 11, 13]))
diff --git a/low_common_ancestor_leaf.c b/low_common_ancestor_leaf.c
new file mode 100644
index 0000000..87b5bf4
--- /dev/null
+++ b/low_common_ancestor_leaf.c
@@ -0,0 +1,49 @@
+// 1123. Lowest Common Ancestor of Deepest Leaves
+#include "leetcode.h"
+
+/*
+ * given the 'root' of a binary tree, return the lowest common ancestor of its
+ * deepest leaves. recall that the node of a binary tree is a leaf if and only
+ * if it has no children, the depth of the root of the tree is 0. if the depth
+ * of a node is 'd', the depth of each of its children is 'd + 1'. and the
+ * lowest common ancestor of a set 's' is the node 'a' with the largest depth
+ * such that every node in 's' is in the subtree with root 'a'.
+ */
+
+int depth(struct TreeNode *root) {
+ if (!root)
+ return 0;
+ int l = depth(root->left);
+ int r = depth(root->right);
+ return l > r ? l + 1 : r + 1;
+}
+
+struct TreeNode *lcaDeepestLeaves(struct TreeNode *root) {
+ if (!root)
+ return NULL;
+ int l = depth(root->left);
+ int r = depth(root->right);
+ if (l == r)
+ return root;
+ return l > r ? lcaDeepestLeaves(root->left) : lcaDeepestLeaves(root->right);
+}
+
+int main() {
+ int r1i[] = {3, 5, 1, 6, 2, 0, 8, -1, -1, 7, 4}, r2i[] = {1},
+ r3i[] = {0, 1, 3, -1, 2};
+ struct TreeNode *r1 = treenode_build(r1i, ARRAY_SIZE(r1i));
+ struct TreeNode *r2 = treenode_build(r2i, ARRAY_SIZE(r2i));
+ struct TreeNode *r3 = treenode_build(r3i, ARRAY_SIZE(r3i));
+ struct TreeNode *lcadl1 = lcaDeepestLeaves(r1);
+ struct TreeNode *lcadl2 = lcaDeepestLeaves(r2);
+ struct TreeNode *lcadl3 = lcaDeepestLeaves(r3);
+ treenode_print(lcadl1); // expect: 2 7 4
+ printf("\n");
+ treenode_print(lcadl2); // expect: 1
+ printf("\n");
+ treenode_print(lcadl3); // expect: 2
+ printf("\n");
+ treenode_free(r1);
+ treenode_free(r2);
+ treenode_free(r3);
+}
diff --git a/low_common_ancestor_leaf.py b/low_common_ancestor_leaf.py
new file mode 100644
index 0000000..4b0036f
--- /dev/null
+++ b/low_common_ancestor_leaf.py
@@ -0,0 +1,48 @@
+# 1123. Lowest Common Ancestor of Deepest Leaves
+import leetcode
+
+"""
+given the 'root' of a binary tree, return the lowest common ancestor of its
+deepest leaves. recall that the node of a binary tree is a leaf if and only
+if it has no children, the depth of the root of the tree is 0. if the depth
+of a node is 'd', the depth of each of its children is 'd + 1'. and the
+lowest common ancestor of a set 's' is the node 'a' with the largest depth
+such that every node in 's' is in the subtree with root 'a'.
+"""
+
+
+class Solution(object):
+ def lcaDeepestLeaves(self, root):
+ """
+ :type root: Optional[TreeNode]
+ :rtype: Optional[TreeNode]
+ """
+
+ def depth(node):
+ if not node:
+ return 0
+ return max(depth(node.left), depth(node.right)) + 1
+
+ def dfs(node, m, n):
+ if not node:
+ return None
+ if m - 1 == n:
+ return node
+ l = dfs(node.left, m, n + 1)
+ r = dfs(node.right, m, n + 1)
+ if l and r:
+ return node
+ return l if l else r
+
+ m = depth(root)
+ return dfs(root, m, 0)
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ r1 = leetcode.treenode_build(root=[3, 5, 1, 6, 2, 0, 8, None, None, 7, 4])
+ r2 = leetcode.treenode_build(root=[1])
+ r3 = leetcode.treenode_build(root=[0, 1, 3, None, 2])
+ print(obj.lcaDeepestLeaves(r1))
+ print(obj.lcaDeepestLeaves(r2))
+ print(obj.lcaDeepestLeaves(r3))
diff --git a/marbles_in_bags.c b/marbles_in_bags.c
index 71c2560..95c1ee1 100644
--- a/marbles_in_bags.c
+++ b/marbles_in_bags.c
@@ -1,6 +1,5 @@
// 2551. Put Marbles in Bags
-#include <stdio.h>
-#include <stdlib.h>
+#include "leetcode.h"
/*
* you have 'k' bags. you are given a 0-indexed integer array 'weights' where
@@ -19,25 +18,24 @@
int cmp(const void *a, const void *b) { return *(int *)a - *(int *)b; }
-long long putMarbles(int *weights, int weights_size, int k) {
- int n = weights_size;
- if (n == k || k == 1)
+long long putMarbles(int *weights, int weightsSize, int k) {
+ if (weightsSize == k || k == 1)
return 0;
- int *data = malloc((n - 1) * sizeof(int));
- for (int i = 0; i < n - 1; i++)
- data[i] = weights[i] + weights[i + 1];
- qsort(data, n - 1, sizeof(int), cmp);
- long long min = weights[0] + weights[n - 1];
- long long max = weights[0] + weights[n - 1];
+ int *pairs = (int *)malloc((weightsSize - 1) * sizeof(int));
+ for (int i = 0; i < weightsSize - 1; i++)
+ pairs[i] = weights[i] + weights[i + 1];
+ qsort(pairs, weightsSize - 1, sizeof(int), cmp);
+ long long min, max;
+ min = max = weights[0] + weights[weightsSize - 1];
for (int i = 0; i < k - 1; i++) {
- min += data[i];
- max += data[n - 2 - i];
+ min += pairs[i];
+ max += pairs[weightsSize - 2 - i];
}
return max - min;
}
int main() {
int w1[] = {1, 3, 5, 1}, w2[] = {1, 3};
- printf("%lld\n", putMarbles(w1, 4, 2)); // expect: 4
- printf("%lld\n", putMarbles(w2, 2, 2)); // expect: 0
+ printf("%lld\n", putMarbles(w1, ARRAY_SIZE(w1), 2)); // expect: 4
+ printf("%lld\n", putMarbles(w2, ARRAY_SIZE(w2), 2)); // expect: 0
}
diff --git a/marbles_in_bags.py b/marbles_in_bags.py
new file mode 100644
index 0000000..0cb520c
--- /dev/null
+++ b/marbles_in_bags.py
@@ -0,0 +1,33 @@
+# 2551. Put Marbles in Bags
+
+"""
+you have 'k' bags. you are given a 0-indexed integer array 'weights' where
+'weights[i]' is the weight of the i'th marble. you are also given the integer
+'k'. divide the marbles into the 'k' bags according to the following rules
+- no bag is empty
+- if the i'th marble and the j'th marble are in a bag, then all the marbles
+with an index between the i'th and j'th indices should also be in that same
+bag.
+- if a bag onsists of all the marbles with an index from 'i' to 'j'
+inclusively, then the cost of the bag is 'weights[i] + weights[j]' the score
+after distributing the marbles is the sum of the costs of all the 'k' bags.
+return the difference between the maximum and minimum scores among marble
+distributions
+"""
+
+
+class Solution(object):
+ def putMarbles(self, weights, k):
+ """
+ :type weights: List[int]
+ :type k: int
+ :rtype: int
+ """
+ pairs = sorted([weights[i] + weights[i + 1] for i in range(len(weights) - 1)])
+ return sum(pairs[len(pairs) - k + 1 :]) - sum(pairs[: k - 1])
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.putMarbles(weights=[1, 3, 5, 1], k=2))
+ print(obj.putMarbles(weights=[1, 3], k=2))
diff --git a/max_candies_allocated_k_children.c b/max_candies_allocated_k_children.c
new file mode 100644
index 0000000..45f105c
--- /dev/null
+++ b/max_candies_allocated_k_children.c
@@ -0,0 +1,32 @@
+// 2226. Maximum Candies Allocated to K Children
+#include "leetcode.h"
+
+/*
+ * you are given a 0-indexed integer array 'candies'. each element in the array
+ * denotes a pile of candies of size 'candies[i]'. you can divide each pile into
+ * any number of sub piles, but you cannot merge two piles together. you are
+ * also given an integer 'k'. you should allocate piles of candies to 'k'
+ * children such that each child gets the same number of candies. each child can
+ * be allocated candies from only one pile of candies, and some piles of candies
+ * may go unused. return the maximum number of candies each child can get
+ */
+
+int maximumCandies(int *candies, int candiesSize, long long k) {
+ int l = 0, r = 1e7;
+ while (l < r) {
+ long long mid = (l + r + 1) / 2, cnt = 0;
+ for (int i = 0; i < candiesSize && cnt < k; ++i)
+ cnt += candies[i] / mid;
+ if (cnt >= k)
+ l = mid;
+ else
+ r = mid - 1;
+ }
+ return l;
+}
+
+int main() {
+ int c1[] = {5, 8, 6}, c2[] = {2, 5};
+ printf("%d\n", maximumCandies(c1, ARRAY_SIZE(c1), 3)); // expect: 5
+ printf("%d\n", maximumCandies(c2, ARRAY_SIZE(c2), 11)); // expect: 0
+}
diff --git a/max_candies_allocated_k_children.py b/max_candies_allocated_k_children.py
new file mode 100644
index 0000000..139ab80
--- /dev/null
+++ b/max_candies_allocated_k_children.py
@@ -0,0 +1,34 @@
+# 2226. Maximum Candies Allocated to K Children
+
+"""
+you are given a 0-indexed integer array 'candies'. each element in the array
+denotes a pile of candies of size 'candies[i]'. you can divide each pile into
+any number of sub piles, but you cannot merge two piles together. you are
+also given an integer 'k'. you should allocate piles of candies to 'k'
+children such that each child gets the same number of candies. each child can
+be allocated candies from only one pile of candies, and some piles of candies
+may go unused. return the maximum number of candies each child can get
+"""
+
+
+class Solution(object):
+ def maximumCandies(self, candies, k):
+ """
+ :type candies: List[int]
+ :type k: int
+ :rtype: int
+ """
+ l, r = 0, sum(candies) / k
+ while l < r:
+ mid = (l + r + 1) / 2
+ if k > sum(i / mid for i in candies):
+ r = mid - 1
+ else:
+ l = mid
+ return l
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.maximumCandies(candies=[5, 8, 6], k=3))
+ print(obj.maximumCandies(candies=[2, 5], k=11))
diff --git a/max_num_point_grid_query.c b/max_num_point_grid_query.c
new file mode 100644
index 0000000..1fbe18a
--- /dev/null
+++ b/max_num_point_grid_query.c
@@ -0,0 +1,122 @@
+// 2503. Maximum Number of Points From Grid Queries
+#include "leetcode.h"
+
+/*
+ * you are given an 'm x n' integer matrix 'grid' and an array 'queries' of size
+ * 'k'. find an array 'answer' of size 'k' such that for each integer
+ * 'queries[i]' start in the top left cell of the matrix and repeat the
+ * following process: if 'queries[i]' is strictly greater than the value of the
+ * current cell that you are in, then you get one point if it is your first time
+ * visiting that cell, and you can move to any adjacent cell in all 4
+ * directions, otherwise you do not get any points, and you end this process.
+ * after the process 'answer[i]' is the maximum number of ponts you can get.
+ * note that for each query, yu are allowed to visit the same cell multiple
+ * times.
+ */
+
+struct list {
+ int val;
+ int x;
+ int y;
+};
+
+struct pp {
+ int val;
+ int place;
+};
+
+int cmp(const void *a, const void *b) {
+ return (*(struct pp *)a).val - (*(struct pp *)b).val;
+}
+
+void input(int **grid, int gridSize, int gridColSize, int i, int j,
+ struct list *helper, int *cnt, bool **used, int *curr_point,
+ int curr_val) {
+ used[i][j] = true;
+ if (curr_val > grid[i][j]) {
+ *curr_point += 1;
+ if (i - 1 >= 0 && !used[i - 1][j])
+ input(grid, gridSize, gridColSize, i - 1, j, helper, cnt, used,
+ curr_point, curr_val);
+ if (i + 1 < gridSize && !used[i + 1][j])
+ input(grid, gridSize, gridColSize, i + 1, j, helper, cnt, used,
+ curr_point, curr_val);
+ if (j - 1 >= 0 && !used[i][j - 1])
+ input(grid, gridSize, gridColSize, i, j - 1, helper, cnt, used,
+ curr_point, curr_val);
+ if (j + 1 < gridColSize && !used[i][j + 1])
+ input(grid, gridSize, gridColSize, i, j + 1, helper, cnt, used,
+ curr_point, curr_val);
+ } else {
+ helper[*cnt].val = grid[i][j];
+ helper[*cnt].x = i;
+ helper[*cnt].y = j;
+ (*cnt)++;
+ }
+}
+
+int *maxPoints(int **grid, int gridSize, int *gridColSize, int *queries,
+ int queriesSize, int *returnSize) {
+ int curr_point = 0, c1 = 0, c2 = 0;
+ struct list *h1 = (struct list *)malloc((gridSize * (*gridColSize)) *
+ sizeof(struct list *));
+ struct list *h2 = (struct list *)malloc((gridSize * (*gridColSize)) *
+ sizeof(struct list *));
+ struct pp *revis = (struct pp *)malloc(queriesSize * sizeof(struct pp));
+ for (int i = 0; i < queriesSize; i++) {
+ revis[i].val = queries[i];
+ revis[i].place = i;
+ }
+ qsort(revis, queriesSize, sizeof(struct pp), cmp);
+ *returnSize = queriesSize;
+ int *ans = (int *)malloc(queriesSize * sizeof(int));
+ bool **used = (bool **)malloc(queriesSize * sizeof(bool *));
+ for (int i = 0; i < gridSize; i++)
+ used[i] = (bool *)calloc(*gridColSize, sizeof(bool));
+ input(grid, gridSize, *gridColSize, 0, 0, h1, &c1, used, &curr_point,
+ revis[0].val);
+ ans[revis[0].place] = curr_point;
+ for (int i = 1; i < queriesSize; i++) {
+ if ((i & 1) == 1) {
+ c2 = 0;
+ for (int j = 0; j < c1; j++)
+ input(grid, gridSize, *gridColSize, h1[j].x, h1[j].y, h2, &c2, used,
+ &curr_point, revis[i].val);
+ } else {
+ c1 = 0;
+ for (int j = 0; j < c2; j++)
+ input(grid, gridSize, *gridColSize, h2[j].x, h2[j].y, h1, &c1, used,
+ &curr_point, revis[i].val);
+ }
+ ans[revis[i].place] = curr_point;
+ }
+ free(revis);
+ free(h1);
+ free(h2);
+ for (int i = 0; i < gridSize; i++)
+ free(used[i]);
+ free(used);
+ return ans;
+}
+
+int main() {
+ int g1i[3][3] = {{1, 2, 3}, {2, 5, 7}, {3, 5, 1}}, q1[] = {5, 6, 2}, rs1;
+ int g2i[2][3] = {{5, 2, 1}, {1, 1, 2}}, q2[] = {3}, rs2;
+ struct two_d_arr g1, g2;
+ two_d_arr_init(&g1, ARRAY_SIZE(g1i), ARRAY_SIZE(g1i[0]), g1i);
+ two_d_arr_init(&g2, ARRAY_SIZE(g2i), ARRAY_SIZE(g2i[0]), g2i);
+ int *mp1 =
+ maxPoints(g1.arr, g1.row_size, g1.col_size, q1, ARRAY_SIZE(q1), &rs1);
+ int *mp2 =
+ maxPoints(g2.arr, g2.row_size, g2.col_size, q2, ARRAY_SIZE(q2), &rs2);
+ for (int i = 0; i < rs1; i++)
+ printf("%d ", mp1[i]); // expect: 5 8 1
+ printf("\n");
+ for (int i = 0; i < rs2; i++)
+ printf("%d ", mp2[i]); // expect: 0
+ printf("\n");
+ free(mp1);
+ free(mp2);
+ two_d_arr_free(&g1);
+ two_d_arr_free(&g2);
+}
diff --git a/max_num_point_grid_query.py b/max_num_point_grid_query.py
new file mode 100644
index 0000000..642a2ec
--- /dev/null
+++ b/max_num_point_grid_query.py
@@ -0,0 +1,49 @@
+# 2503. Maximum Number of Points From Grid Queries
+import heapq
+from bisect import bisect_left
+
+"""
+you are given an 'm x n' integer matrix 'grid' and an array 'queries' of size
+'k'. find an array 'answer' of size 'k' such that for each integer
+'queries[i]' start in the top left cell of the matrix and repeat the
+following process: if 'queries[i]' is strictly greater than the value of the
+current cell that you are in, then you get one point if it is your first time
+visiting that cell, and you can move to any adjacent cell in all 4
+directions, otherwise you do not get any points, and you end this process.
+after the process 'answer[i]' is the maximum number of ponts you can get.
+note that for each query, yu are allowed to visit the same cell multiple
+times.
+"""
+
+
+class Solution(object):
+ def maxPoints(self, grid, queries):
+ """
+ :type grid: List[List[int]]
+ :type queries: List[int]
+ :rtype: List[int]
+ """
+ n, m = len(grid), len(grid[0])
+ heap = [(grid[0][0], 0, 0)]
+ v, order = {(0, 0)}, []
+ while len(heap) > 0:
+ curr, i, j = heapq.heappop(heap)
+ order.append(curr)
+ for x, y in [(i - 1, j), (i, j - 1), (i + 1, j), (i, j + 1)]:
+ if 0 <= x < n and 0 <= y < m and (x, y) not in v:
+ v.add((x, y))
+ heapq.heappush(heap, (grid[x][y], x, y))
+ high = -1
+ for i in range(len(order)):
+ high = max(high, order[i])
+ order[i] = high
+ ans = []
+ for i in queries:
+ ans.append(bisect_left(order, i))
+ return ans
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.maxPoints(grid=[[1, 2, 3], [2, 5, 7], [3, 5, 1]], queries=[5, 6, 2]))
+ print(obj.maxPoints(grid=[[5, 2, 1], [1, 1, 2]], queries=[3]))
diff --git a/max_value_ordered_triplet1.c b/max_value_ordered_triplet1.c
new file mode 100644
index 0000000..9a62e4a
--- /dev/null
+++ b/max_value_ordered_triplet1.c
@@ -0,0 +1,28 @@
+// 2873. Maximum Value of an Ordered Triplet I
+#include "leetcode.h"
+
+/*
+ * you are given a 0-indexed integer array 'nums'. return the maximum value over
+ * all triplets of indices '(i, j, k)' such that 'i < j < k'. if all such
+ * triplets have a negative value, return 0. the value of a triplet of indices
+ * '(i, j, k)' is equal to '(nums[i] - nums[j]) * nums[k]'
+ */
+
+long long maximumTripletValue(int *nums, int numsSize) {
+ if (numsSize < 3)
+ return 0;
+ long long ans = 0, curr = nums[0], diff = 0;
+ for (int i = 1; i < numsSize; i++) {
+ ans = fmax(ans, (long long)diff * nums[i]);
+ diff = fmax(diff, curr - nums[i]);
+ curr = fmax(curr, nums[i]);
+ }
+ return ans;
+}
+
+int main() {
+ int n1[] = {12, 6, 1, 2, 7}, n2[] = {1, 10, 3, 4, 19}, n3[] = {1, 2, 3};
+ printf("%lld\n", maximumTripletValue(n1, ARRAY_SIZE(n1))); // expect: 77
+ printf("%lld\n", maximumTripletValue(n2, ARRAY_SIZE(n2))); // expect: 133
+ printf("%lld\n", maximumTripletValue(n3, ARRAY_SIZE(n3))); // expect: 0
+}
diff --git a/max_value_ordered_triplet1.py b/max_value_ordered_triplet1.py
new file mode 100644
index 0000000..e91c340
--- /dev/null
+++ b/max_value_ordered_triplet1.py
@@ -0,0 +1,32 @@
+# 2873. Maximum Value of an Ordered Triplet I
+
+"""
+you are given a 0-indexed integer array 'nums'. return the maximum value over
+all triplets of indices '(i, j, k)' such that 'i < j < k'. if all such
+triplets have a negative value, return 0. the value of a triplet of indices
+'(i, j, k)' is equal to '(nums[i] - nums[j]) nums[k]'
+"""
+
+
+class Solution(object):
+ def maximumTripletValue(self, nums):
+ """
+ :type nums: List[int]
+ :rtype: int
+ """
+ n = len(nums)
+ if n < 3:
+ return 0
+ ans, curr, diff = 0, nums[0], 0
+ for i in range(1, n):
+ ans = max(ans, diff * nums[i])
+ diff = max(diff, curr - nums[i])
+ curr = max(curr, nums[i])
+ return ans
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.maximumTripletValue(nums=[12, 6, 1, 2, 7]))
+ print(obj.maximumTripletValue(nums=[1, 10, 3, 4, 19]))
+ print(obj.maximumTripletValue(nums=[1, 2, 3]))
diff --git a/max_value_ordered_triplet2.c b/max_value_ordered_triplet2.c
new file mode 100644
index 0000000..d8151bd
--- /dev/null
+++ b/max_value_ordered_triplet2.c
@@ -0,0 +1,28 @@
+// 2874. Maximum Value of an Ordered Triplet II
+#include "leetcode.h"
+
+/*
+ * you are given a 0-indexed integer array 'nums'. return the maximum value over
+ * all triplets of indices '(i, j, k)' such that 'i < j < k'. if all such
+ * triplets have a negative value, return 0. the value of a triplet of indices
+ * '(i, j, k)' is equal to '(nums[i] - nums[j]) * nums[k]'
+ */
+
+long long maximumTripletValue(int *nums, int numsSize) {
+ if (numsSize < 3)
+ return 0;
+ long long ans = 0, curr = nums[0], diff = 0;
+ for (int i = 1; i < numsSize; i++) {
+ ans = fmax(ans, (long long)diff * nums[i]);
+ diff = fmax(diff, curr - nums[i]);
+ curr = fmax(curr, nums[i]);
+ }
+ return ans;
+}
+
+int main() {
+ int n1[] = {12, 6, 1, 2, 7}, n2[] = {1, 10, 3, 4, 19}, n3[] = {1, 2, 3};
+ printf("%lld\n", maximumTripletValue(n1, ARRAY_SIZE(n1))); // expect: 77
+ printf("%lld\n", maximumTripletValue(n2, ARRAY_SIZE(n2))); // expect: 133
+ printf("%lld\n", maximumTripletValue(n3, ARRAY_SIZE(n3))); // expect: 0
+}
diff --git a/max_value_ordered_triplet2.py b/max_value_ordered_triplet2.py
new file mode 100644
index 0000000..5673d61
--- /dev/null
+++ b/max_value_ordered_triplet2.py
@@ -0,0 +1,32 @@
+# 2874. Maximum Value of an Ordered Triplet II
+
+"""
+you are given a 0-indexed integer array 'nums'. return the maximum value over
+all triplets of indices '(i, j, k)' such that 'i < j < k'. if all such
+triplets have a negative value, return 0. the value of a triplet of indices
+'(i, j, k)' is equal to '(nums[i] - nums[j]) nums[k]'
+"""
+
+
+class Solution(object):
+ def maximumTripletValue(self, nums):
+ """
+ :type nums: List[int]
+ :rtype: int
+ """
+ n = len(nums)
+ if n < 3:
+ return 0
+ ans, curr, diff = 0, nums[0], 0
+ for i in range(1, n):
+ ans = max(ans, diff * nums[i])
+ diff = max(diff, curr - nums[i])
+ curr = max(curr, nums[i])
+ return ans
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.maximumTripletValue(nums=[12, 6, 1, 2, 7]))
+ print(obj.maximumTripletValue(nums=[1, 10, 3, 4, 19]))
+ print(obj.maximumTripletValue(nums=[1, 2, 3]))
diff --git a/min_cost_walk_weight_graph.py b/min_cost_walk_weight_graph.py
new file mode 100644
index 0000000..b1d2415
--- /dev/null
+++ b/min_cost_walk_weight_graph.py
@@ -0,0 +1,72 @@
+# 3108. Minimum Cost Walk in Weighted Graph
+
+"""
+there is an undirected weighted graph with 'n' vertices labeled from 0 to 'n
+- 1'. you are given the integer 'n' and an array 'edges', where 'edges[i] =
+[u_i, v_i, w_i]' indicates that there is an edge between vertices 'u_i' and
+'v_i' with a weight of 'w_i'. a walk on the graph is a sequence of vertices
+and edges. the walk starts and ends with a vertex, and each edge connects the
+vertex that comes before it and the vertex that comes after it. it's
+important to note that a walk may visit the same edge or vertex more than
+once. return the array 'answer' where 'answer[i]' denotes the minimum cost of
+a walk for query 'i'.
+"""
+
+
+class UnionFind:
+ def __init__(self, size):
+ self.parent = [i for i in range(size)]
+ self.rank = [0 for _ in range(size)]
+ self.d = [~0 for _ in range(size)]
+
+ def find(self, node):
+ if self.parent[node] != node:
+ self.parent[node] = self.find(self.parent[node])
+ return self.parent[node]
+
+ def union(self, a, b, val):
+ p1, p2 = self.find(a), self.find(b)
+ if self.rank[p1] > self.rank[p2]:
+ self.parent[p2] = p1
+ self.d[p1] &= self.d[p2] & val
+ elif self.rank[p1] < self.rank[p2]:
+ self.parent[p1] = p2
+ self.d[p2] &= self.d[p1] & val
+ else:
+ self.parent[p1] = p2
+ self.d[p2] &= self.d[p1] & val
+ self.rank[p2] += 1
+
+
+class Solution(object):
+ def minimumCost(self, n, edges, query):
+ """
+ :type n: int
+ :type edges: List[List[int]]
+ :type query: List[List[int]]
+ :rtype: List[int]
+ """
+ uf = UnionFind(n)
+ for u, v, w in edges:
+ uf.union(u, v, w)
+ ans = []
+ for u, v in query:
+ if uf.find(u) != uf.find(v):
+ ans.append(-1)
+ else:
+ ans.append(uf.d[uf.find(u)])
+ return ans
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(
+ obj.minimumCost(
+ n=5, edges=[[0, 1, 7], [1, 3, 7], [1, 2, 1]], query=[[0, 3], [3, 4]]
+ )
+ )
+ print(
+ obj.minimumCost(
+ n=3, edges=[[0, 2, 7], [0, 1, 15], [1, 2, 6], [1, 2, 1]], query=[[1, 2]]
+ )
+ )
diff --git a/min_idx_valid_split.c b/min_idx_valid_split.c
new file mode 100644
index 0000000..fbb2b98
--- /dev/null
+++ b/min_idx_valid_split.c
@@ -0,0 +1,43 @@
+// 2780. Minimum Index of a Valid Split
+#include "leetcode.h"
+
+/*
+ * an element 'x' of an integer array 'arr' of length 'm' is dominant if more
+ * than half the elements of 'arr' have a value of 'x'. you are given a
+ * 0-indexed integer array 'nums' of length 'n' with one dominant element. you
+ * can split 'nums' at an index 'i' into two arrays 'nums[0, ..., i]' and
+ * 'nums[i + 1, ..., n - 1]', but the split is only valid if '0 <= i < - 1' and
+ * the two arrays have the same dominant element. return the minimum index of a
+ * valid split. if no split exists, return -1.
+ */
+
+int minimumIndex(int *nums, int numsSize) {
+ int dominant = nums[0], cnt = 0;
+ for (int i = 0; i < numsSize; i++) {
+ cnt = nums[i] == dominant ? cnt + 1 : cnt - 1;
+ if (!cnt) {
+ dominant = nums[i];
+ cnt = 1;
+ }
+ }
+ int left = 0;
+ for (int i = 0; i < numsSize; i++)
+ if (nums[i] == dominant)
+ left++;
+ cnt = 0;
+ for (int i = 0; i < numsSize; i++) {
+ if (nums[i] == dominant)
+ cnt++;
+ if (cnt * 2 > (i + 1) && (left - cnt) * 2 > (numsSize - i - 1))
+ return i;
+ }
+ return -1;
+}
+
+int main() {
+ int n1[] = {1, 2, 2, 2}, n2[] = {2, 1, 3, 1, 1, 1, 7, 1, 2, 1},
+ n3[] = {3, 3, 3, 3, 7, 2, 2};
+ printf("%d\n", minimumIndex(n1, ARRAY_SIZE(n1))); // expect: 2
+ printf("%d\n", minimumIndex(n2, ARRAY_SIZE(n2))); // expect: 4
+ printf("%d\n", minimumIndex(n3, ARRAY_SIZE(n3))); // expect: -1
+}
diff --git a/min_idx_valid_split.py b/min_idx_valid_split.py
new file mode 100644
index 0000000..a03a65c
--- /dev/null
+++ b/min_idx_valid_split.py
@@ -0,0 +1,35 @@
+# 2780. Minimum Index of a Valid Split
+from collections import Counter
+
+"""
+an element 'x' of an integer array 'arr' of length 'm' is dominant if more
+than half the elements of 'arr' have a value of 'x'. you are given a
+0-indexed integer array 'nums' of length 'n' with one dominant element. you
+can split 'nums' at an index 'i' into two arrays 'nums[0, ..., i]' and
+'nums[i + 1, ..., n - 1]', but the split is only valid if '0 <= i < - 1' and
+the two arrays have the same dominant element. return the minimum index of a
+valid split. if no split exists, return -1.
+"""
+
+
+class Solution(object):
+ def minimumIndex(self, nums):
+ """
+ :type nums: List[int]
+ :rtype: int
+ """
+ dominant, cnt = max(Counter(nums).items(), key=lambda x: x[1])
+ left, split = 0, 2 * cnt - len(nums)
+ if split < 2:
+ return -1
+ for i, j in enumerate(nums):
+ left += 2 * (j == dominant)
+ if 1 < left - i <= split:
+ return i
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.minimumIndex(nums=[1, 2, 2, 2]))
+ print(obj.minimumIndex(nums=[2, 1, 3, 1, 1, 1, 7, 1, 2, 1]))
+ print(obj.minimumIndex(nums=[3, 3, 3, 3, 7, 2, 2]))
diff --git a/min_num_work_session.c b/min_num_work_session.c
new file mode 100644
index 0000000..54f4190
--- /dev/null
+++ b/min_num_work_session.c
@@ -0,0 +1,58 @@
+// 1986. Minimum Number of Work Sessions to Finish the Tasks
+#include "leetcode.h"
+
+/*
+ * there are 'n' tasks assigned to you. the task times are represented as an
+ * integer array 'tasks' of length 'n' where the i'th task takes 'tasks[i]'
+ * hours to finish. a work session is when you work for at most 'sessionTime'
+ * consecutive hours, and then take a break. given 'tasks' and 'sessionTime',
+ * return the minimum number of work sessions needed to finish all the tasks
+ * following the conditions. the tests are generated such that 'sessionTime' is
+ * greater or equal to the maximum element in 'tasks[i]'.
+ */
+
+int work(int *tasks, int tasksSize, int completed, int sessionTime,
+ int time_remaining, int **dp) {
+ int cnt, min = INT_MAX;
+ if (completed == (1 << tasksSize) - 1)
+ return 0;
+ if (dp[completed][time_remaining] != -1)
+ return dp[completed][time_remaining];
+ for (int i = 0; i < tasksSize; i++) {
+ if (!(completed & (1 << i))) {
+ completed |= (1 << i);
+ if (time_remaining - tasks[i] < 0)
+ cnt = work(tasks, tasksSize, completed, sessionTime,
+ sessionTime - tasks[i], dp) +
+ 1;
+ else
+ cnt = work(tasks, tasksSize, completed, sessionTime,
+ time_remaining - tasks[i], dp);
+ min = fmin(min, cnt);
+ completed &= ~(1 << i);
+ }
+ }
+ dp[completed][time_remaining] = min;
+ return min;
+}
+
+int minSessions(int *tasks, int tasksSize, int sessionTime) {
+ int **dp = (int **)malloc((1 << tasksSize) * sizeof(int *));
+ for (int i = 0; i < (1 << tasksSize); i++) {
+ dp[i] = (int *)malloc((sessionTime + 1) * sizeof(int));
+ for (int j = 0; j <= sessionTime; j++)
+ dp[i][j] = -1;
+ }
+ int ans = work(tasks, tasksSize, 0, sessionTime, 0, dp);
+ for (int i = 0; i < (1 << tasksSize); i++)
+ free(dp[i]);
+ free(dp);
+ return ans;
+}
+
+int main() {
+ int t1[] = {1, 2, 3}, t2[] = {3, 1, 3, 1, 1}, t3[] = {1, 2, 3, 4, 5};
+ printf("%d\n", minSessions(t1, ARRAY_SIZE(t1), 3)); // expect: 2
+ printf("%d\n", minSessions(t2, ARRAY_SIZE(t2), 8)); // expect: 2
+ printf("%d\n", minSessions(t3, ARRAY_SIZE(t3), 15)); // expect: 1
+}
diff --git a/min_num_work_session.py b/min_num_work_session.py
new file mode 100644
index 0000000..9c0ca12
--- /dev/null
+++ b/min_num_work_session.py
@@ -0,0 +1,41 @@
+# 1986. Minimum Number of Work Sessions to Finish the Tasks
+
+"""
+there are 'n' tasks assigned to you. the task times are represented as an
+integer array 'tasks' of length 'n' where the i'th task takes 'tasks[i]'
+hours to finish. a work session is when you work for at most 'sessionTime'
+consecutive hours, and then take a break. given 'tasks' and 'sessionTime',
+return the minimum number of work sessions needed to finish all the tasks
+following the conditions. the tests are generated such that 'sessionTime' is
+greater or equal to the maximum element in 'tasks[i]'.
+"""
+
+
+class Solution(object):
+ def minSessions(self, tasks, sessionTime):
+ """
+ :type tasks: List[int]
+ :type sessionTime: int
+ :rtype: int
+ """
+ n = len(tasks)
+
+ def dp(mask):
+ if mask == 0:
+ return (1, 0)
+ res = (float("inf"), float("inf"))
+ for i in range(n):
+ if mask & (1 << i):
+ pieces, prev = dp(mask - (1 << i))
+ full = prev + tasks[i] > sessionTime
+ res = min(res, (pieces + full, tasks[i] + (1 - full) * prev))
+ return res
+
+ return dp((1 << n) - 1)[0]
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.minSessions(tasks=[1, 2, 3], sessionTime=3))
+ print(obj.minSessions(tasks=[3, 1, 3, 1, 1], sessionTime=8))
+ print(obj.minSessions(tasks=[1, 2, 3, 4, 5], sessionTime=15))
diff --git a/min_ops_bin_arr_1.c b/min_ops_bin_arr_1.c
new file mode 100644
index 0000000..c589165
--- /dev/null
+++ b/min_ops_bin_arr_1.c
@@ -0,0 +1,29 @@
+// 3191. Minimum Operations to Make Binary Array Elements Equal to One I
+#include "leetcode.h"
+
+/*
+ * you are given a binary array 'nums'. you can do the following operation on
+ * the array any number of times (possibly zero): choose any three consecutive
+ * elements from the array and flip all of them. flipping an element means
+ * changing its value from 0 to 1, and from 1 to 0. return the minimum number of
+ * operations required needed to make all elements in 'nums' equal to 1. if it
+ * is impossible, return -1.
+ */
+
+int minOperations(int *nums, int numsSize) {
+ int cnt = 0;
+ for (int i = 0; i < numsSize - 2; i++)
+ if (!nums[i]) {
+ nums[i] ^= 1;
+ nums[i + 1] ^= 1;
+ nums[i + 2] ^= 1;
+ cnt++;
+ }
+ return nums[numsSize - 2] && nums[numsSize - 1] ? cnt : -1;
+}
+
+int main() {
+ int n1[] = {0, 1, 1, 1, 0, 0}, n2[] = {0, 1, 1, 1};
+ printf("%d\n", minOperations(n1, ARRAY_SIZE(n1))); // expect: 3
+ printf("%d\n", minOperations(n2, ARRAY_SIZE(n2))); // expect: -1
+}
diff --git a/min_ops_bin_arr_1.py b/min_ops_bin_arr_1.py
new file mode 100644
index 0000000..eed3fea
--- /dev/null
+++ b/min_ops_bin_arr_1.py
@@ -0,0 +1,32 @@
+# 3191. Minimum Operations to Make Binary Array Elements Equal to One I
+
+"""
+you are given a binary array 'nums'. you can do the following operation on
+the array any number of times (possibly zero): choose any three consecutive
+elements from the array and flip all of them. flipping an element means
+changing its value from 0 to 1, and from 1 to 0. return the minimum number of
+operations required needed to make all elements in 'nums' equal to 1. if it
+is impossible, return -1.
+"""
+
+
+class Solution(object):
+ def minOperations(self, nums):
+ """
+ :type nums: List[int]
+ :rtype: int
+ """
+ cnt, n = 0, len(nums)
+ for i in range(n - 2):
+ if nums[i] == 0:
+ nums[i] ^= 1
+ nums[i + 1] ^= 1
+ nums[i + 2] ^= 1
+ cnt += 1
+ return cnt if nums[n - 2] == 1 and nums[n - 1] == 1 else -1
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.minOperations(nums=[0, 1, 1, 1, 0, 0]))
+ print(obj.minOperations(nums=[0, 1, 1, 1]))
diff --git a/min_ops_uni_val_grid.c b/min_ops_uni_val_grid.c
new file mode 100644
index 0000000..aa2f025
--- /dev/null
+++ b/min_ops_uni_val_grid.c
@@ -0,0 +1,49 @@
+// 2033. Minimum Operations to Make a Uni-Value Grid
+#include "leetcode.h"
+
+/*
+ * you are given a 2d integer 'grid' of size 'm x n' and an integer 'x'. in one
+ * operation, you can add 'x' to or subtract 'x' from any element in the 'grid'.
+ * a uni-value grid is a grid where all the elements of it are equal. return the
+ * minimum number of operations to make the grid uni-valued. if it is not
+ * possible, return -1.
+ */
+
+int cmp(const void *a, const void *b) { return *(int *)a - *(int *)b; }
+
+int minOperations(int **grid, int gridSize, int *gridColSize, int x) {
+ int n = gridSize * (*gridColSize), idx = 0, mod = grid[0][0] % x;
+ int *vals = (int *)malloc(n * sizeof(int));
+ for (int i = 0; i < gridSize; ++i)
+ for (int j = 0; j < *gridColSize; ++j) {
+ vals[idx] = grid[i][j];
+ if (vals[idx++] % x != mod) {
+ free(vals);
+ return -1;
+ }
+ }
+ qsort(vals, n, sizeof(int), cmp);
+ int med = vals[n / 2], ans = 0;
+ for (int i = 0; i < n; i++)
+ ans += abs(med - vals[i]) / x;
+ free(vals);
+ return ans;
+}
+
+int main() {
+ int g1i[2][2] = {{2, 4}, {6, 8}}, g2i[2][2] = {{1, 5}, {2, 3}},
+ g3i[2][2] = {{1, 2}, {3, 4}};
+ struct two_d_arr g1, g2, g3;
+ two_d_arr_init(&g1, ARRAY_SIZE(g1i), ARRAY_SIZE(g1i[0]), g1i);
+ two_d_arr_init(&g2, ARRAY_SIZE(g2i), ARRAY_SIZE(g2i[0]), g2i);
+ two_d_arr_init(&g3, ARRAY_SIZE(g3i), ARRAY_SIZE(g3i[0]), g3i);
+ printf("%d\n",
+ minOperations(g1.arr, g1.row_size, g1.col_size, 2)); // expect: 4
+ printf("%d\n",
+ minOperations(g2.arr, g2.row_size, g2.col_size, 1)); // expect: 5
+ printf("%d\n",
+ minOperations(g3.arr, g3.row_size, g3.col_size, 2)); // expect: -1
+ two_d_arr_free(&g1);
+ two_d_arr_free(&g2);
+ two_d_arr_free(&g3);
+}
diff --git a/min_ops_uni_val_grid.py b/min_ops_uni_val_grid.py
new file mode 100644
index 0000000..b417eb2
--- /dev/null
+++ b/min_ops_uni_val_grid.py
@@ -0,0 +1,32 @@
+# 2033. Minimum Operations to Make a Uni-Value Grid
+
+"""
+you are given a 2d integer 'grid' of size 'm x n' and an integer 'x'. in one
+operation, you can add 'x' to or subtract 'x' from any element in the 'grid'.
+a uni-value grid is a grid where all the elements of it are equal. return the
+minimum number of operations to make the grid uni-valued. if it is not
+possible, return -1.
+"""
+
+
+class Solution(object):
+ def minOperations(self, grid, x):
+ """
+ :type grid: List[List[int]]
+ :type x: int
+ :rtype: int
+ """
+ vals = sorted([i for j in grid for i in j])
+ diff = [abs(i - vals[0]) % x for i in vals]
+ if any(i != 0 for i in diff):
+ return -1
+ med = vals[len(vals) // 2]
+ ans = sum(abs(i - med) // x for i in vals)
+ return ans
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.minOperations(grid=[[2, 4], [6, 8]], x=2))
+ print(obj.minOperations(grid=[[1, 5], [2, 3]], x=1))
+ print(obj.minOperations(grid=[[1, 2], [3, 4]], x=2))
diff --git a/min_time_repair_car.c b/min_time_repair_car.c
new file mode 100644
index 0000000..ddd9dce
--- /dev/null
+++ b/min_time_repair_car.c
@@ -0,0 +1,31 @@
+// 2594. Minimum Time to Repair Cars
+#include "leetcode.h"
+
+/*
+ * you are given an integer array 'ranks' representing the ranks of some
+ * mechanics. 'ranks[i]' is the rank of the i'th mechanic. a mechanic with a
+ * rank 'r' can repair 'n' cars in 'r * n^2' minutes. you are also given an
+ * integer 'cars' representing the total number of cars waiting in the garage to
+ * be repaired. return the minimum time taken to repair all the cars. note: all
+ * the mechanics can repair the cars simultaneously.
+ */
+
+long long repairCars(int *ranks, int ranksSize, int cars) {
+ long long left = 0, right = 1e14;
+ while (left < right) {
+ long long mid = left + (right - left) / 2, cnt = 0;
+ for (int i = 0; i < ranksSize; i++)
+ cnt += sqrt(mid / ranks[i]);
+ if (cnt < cars)
+ left = mid + 1;
+ else
+ right = mid;
+ }
+ return left;
+}
+
+int main() {
+ int r1[] = {4, 2, 3, 1}, r2[] = {5, 1, 8};
+ printf("%lld\n", repairCars(r1, ARRAY_SIZE(r1), 10)); // expect: 16
+ printf("%lld\n", repairCars(r2, ARRAY_SIZE(r2), 6)); // expect: 16
+}
diff --git a/min_time_repair_car.py b/min_time_repair_car.py
new file mode 100644
index 0000000..7f8db29
--- /dev/null
+++ b/min_time_repair_car.py
@@ -0,0 +1,36 @@
+# 2594. Minimum Time to Repair Cars
+import heapq
+from collections import Counter
+
+"""
+you are given an integer array 'ranks' representing the ranks of some
+mechanics. 'ranks[i]' is the rank of the i'th mechanic. a mechanic with a
+rank 'r' can repair 'n' cars in 'r n^2' minutes. you are also given an
+integer 'cars' representing the total number of cars waiting in the garage to
+be repaired. return the minimum time taken to repair all the cars. note: all
+the mechanics can repair the cars simultaneously.
+"""
+
+
+class Solution(object):
+ def repairCars(self, ranks, cars):
+ """
+ :type ranks: List[int]
+ :type cars: int
+ :rtype: int
+ """
+ cnt = Counter(ranks)
+ h = [[i, i, 1, cnt[i]] for i in cnt]
+ heapq.heapify(h)
+ while cars > 0:
+ time, rank, k, count = heapq.heappop(h)
+ cars -= count
+ k += 1
+ heapq.heappush(h, [rank * k * k, rank, k, count])
+ return time
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.repairCars(ranks=[4, 2, 3, 1], cars=10))
+ print(obj.repairCars(ranks=[5, 1, 8], cars=6))
diff --git a/min_xor_sum_two_arr.c b/min_xor_sum_two_arr.c
new file mode 100644
index 0000000..492a0f8
--- /dev/null
+++ b/min_xor_sum_two_arr.c
@@ -0,0 +1,35 @@
+// 1879. Minimum XOR Sum of Two Arrays
+#include "leetcode.h"
+
+/*
+ * you are given two integer arrays 'nums1' and 'nums2' of length 'n'. the xor
+ * sum of the two integer arrays is '(nums1[0] ^ nums2[0]) + (nums1[1] ^
+ * nums2[1]) + ...' (0-indexed). rearrange the elements of 'nums2' such that
+ * resulting xor sum is minimised. return the xor sum after the rearrangement.
+ */
+
+static int dp[1 << 14] = {[0 ... 16383] = INT_MAX};
+
+int dfs(int *nums1, int *nums2, int n, int i, int mask) {
+ if (i >= n)
+ return 0;
+ if (dp[mask] == -1)
+ for (int j = 0; j < n; ++j)
+ if (!(mask & (1 << j)))
+ dp[mask] =
+ fmin(dp[mask], (nums1[i] ^ nums2[j]) +
+ dfs(nums1, nums2, n, i + 1, mask + (1 << j)));
+ return dp[mask];
+}
+
+int minimumXORSum(int *nums1, int nums1Size, int *nums2, int nums2Size) {
+ return dfs(nums1, nums2, nums1Size, 0, 0);
+}
+
+int main() {
+ int n11[] = {1, 2}, n21[] = {2, 3}, n12[] = {1, 0, 3}, n22[] = {5, 3, 4};
+ printf("%d\n", minimumXORSum(n11, ARRAY_SIZE(n11), n21,
+ ARRAY_SIZE(n21))); // expect: 2
+ printf("%d\n", minimumXORSum(n12, ARRAY_SIZE(n12), n22,
+ ARRAY_SIZE(n22))); // expect: 8
+}
diff --git a/min_xor_sum_two_arr.py b/min_xor_sum_two_arr.py
new file mode 100644
index 0000000..f54d44b
--- /dev/null
+++ b/min_xor_sum_two_arr.py
@@ -0,0 +1,35 @@
+# 1879. Minimum XOR Sum of Two Arrays
+
+"""
+you are given two integer arrays 'nums1' and 'nums2' of length 'n'. the xor
+sum of the two integer arrays is '(nums1[0] ^ nums2[0]) + (nums1[1] ^
+nums2[1]) + ...' (0-indexed). rearrange the elements of 'nums2' such that
+resulting xor sum is minimised. return the xor sum after the rearrangement.
+"""
+
+
+class Solution(object):
+ def minimumXORSum(self, nums1, nums2):
+ """
+ :type nums1: List[int]
+ :type nums2: List[int]
+ :rtype: int
+ """
+
+ def dfs(mask):
+ i = bin(mask).count("1")
+ if i >= len(nums1):
+ return 0
+ return min(
+ (nums1[i] ^ nums2[j]) + dfs(mask + (1 << j))
+ for j in range(len(nums2))
+ if mask & (1 << j) == 0
+ )
+
+ return dfs(0)
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.minimumXORSum(nums1=[1, 2], nums2=[2, 3]))
+ print(obj.minimumXORSum(nums1=[1, 0, 3], nums2=[5, 3, 4]))
diff --git a/num_ways_arrive_dest.py b/num_ways_arrive_dest.py
new file mode 100644
index 0000000..ee7f23f
--- /dev/null
+++ b/num_ways_arrive_dest.py
@@ -0,0 +1,69 @@
+# 1976. Number of Ways to Arrive at Destination
+from collections import defaultdict
+import heapq
+
+"""
+you are in a city that consists of 'n' intersections numbered from 0 to 'n -
+1' with bi directional roads between some intersections. the inputs are
+generated such that you can reach any intersection from any other
+intersection and that there is at most one road between any two
+intersections. you are given an integer 'n' and a 2d integer array 'roads'
+where 'roads[i] = [u_i, v_i, t_i]' means that there is a road between
+intersections 'u' and 'v' that takes 't' minutes to travel. you want to know
+in how many ways you can travel from interseciton 0 to intersection 'n - 1'.
+"""
+
+
+class Solution(object):
+ def countPaths(self, n, roads):
+ """
+ :type n: int
+ :type roads: List[List[int]]
+ :rtype: int
+ """
+ graph = defaultdict(list)
+ for u, v, t in roads:
+ graph[u].append([v, t])
+ graph[v].append([u, t])
+
+ def dijkstra(src):
+ dist, ways = [float("inf")] * n, [0] * n
+ pq = [(0, src)]
+ ways[src] = 1
+ dist[src] = 0
+ while pq:
+ d, u = heapq.heappop(pq)
+ if dist[u] < d:
+ continue
+ for v, t in graph[u]:
+ if dist[v] > d + t:
+ dist[v] = d + t
+ ways[v] = ways[u]
+ heapq.heappush(pq, (dist[v], v))
+ elif dist[v] == d + t:
+ ways[v] = (ways[v] + ways[u]) % (10**9 + 7)
+ return ways[n - 1]
+
+ return dijkstra(0)
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(
+ obj.countPaths(
+ n=7,
+ roads=[
+ [0, 6, 7],
+ [0, 1, 2],
+ [1, 2, 3],
+ [1, 3, 3],
+ [6, 3, 3],
+ [3, 5, 1],
+ [6, 5, 1],
+ [2, 5, 1],
+ [0, 4, 5],
+ [4, 6, 2],
+ ],
+ )
+ )
+ print(obj.countPaths(n=2, roads=[[1, 0, 10]]))
diff --git a/other/min_cost_walk_weight_graph.cpp b/other/min_cost_walk_weight_graph.cpp
new file mode 100644
index 0000000..79f3a8b
--- /dev/null
+++ b/other/min_cost_walk_weight_graph.cpp
@@ -0,0 +1,72 @@
+// 3108. Minimum Cost Walk in Weighted Graph
+#include "leetcode.h"
+
+/*
+ * there is an undirected weighted graph with 'n' vertices labeled from 0 to 'n
+ * - 1'. you are given the integer 'n' and an array 'edges', where 'edges[i] =
+ * [u_i, v_i, w_i]' indicates that there is an edge between vertices 'u_i' and
+ * 'v_i' with a weight of 'w_i'. a walk on the graph is a sequence of vertices
+ * and edges. the walk starts and ends with a vertex, and each edge connects the
+ * vertex that comes before it and the vertex that comes after it. it's
+ * important to note that a walk may visit the same edge or vertex more than
+ * once. return the array 'answer' where 'answer[i]' denotes the minimum cost of
+ * a walk for query 'i'.
+ */
+
+class Solution {
+public:
+ vector<int> minimumCost(int n, vector<vector<int>> &edges,
+ vector<vector<int>> &query) {
+ vector<vector<int>> adj(n);
+ vector<int> cnt(n, (1 << 30) - 1);
+ for (vector<int> e : edges) {
+ int u = e[0], v = e[1], k = e[2];
+ adj[u].push_back(v);
+ adj[v].push_back(u);
+ cnt[u] &= k;
+ cnt[v] &= k;
+ }
+ queue<int> q;
+ vector<int> group(n, -1);
+ for (int i = 0; i < n; i++) {
+ if (group[i] == -1) {
+ group[i] = i;
+ q.push(i);
+ while (!q.empty()) {
+ int u = q.front();
+ q.pop();
+ cnt[i] &= cnt[u];
+ for (int v : adj[u]) {
+ if (group[v] == -1) {
+ group[v] = i;
+ q.push(v);
+ }
+ }
+ }
+ }
+ }
+ vector<int> ans;
+ for (vector<int> qs : query) {
+ int s = qs[0], t = qs[1];
+ if (s == t)
+ ans.push_back(0);
+ else
+ ans.push_back(group[s] == group[t] ? cnt[group[s]] : -1);
+ }
+ return ans;
+ }
+};
+
+int main() {
+ Solution obj;
+ vvd e1 = {{0, 1, 7}, {1, 3, 7}, {1, 2, 1}}, q1 = {{0, 3}, {3, 4}};
+ vvd e2 = {{0, 2, 7}, {0, 1, 15}, {1, 2, 6}, {1, 2, 1}}, q2 = {{1, 2}};
+ vector<int> mc1 = obj.minimumCost(5, e1, q1);
+ vector<int> mc2 = obj.minimumCost(3, e2, q2);
+ for (auto i : mc1)
+ printf("%d ", i); // expect: 1 -1
+ printf("\n");
+ for (auto i : mc2)
+ printf("%d ", i); // expect: 0
+ printf("\n");
+}
diff --git a/other/num_ways_arrive_dest.cpp b/other/num_ways_arrive_dest.cpp
new file mode 100644
index 0000000..416d811
--- /dev/null
+++ b/other/num_ways_arrive_dest.cpp
@@ -0,0 +1,62 @@
+// 1976. Number of Ways to Arrive at Destination
+#include "leetcode.h"
+
+/*
+ * you are in a city that consists of 'n' intersections numbered from 0 to 'n -
+ * 1' with bi directional roads between some intersections. the inputs are
+ * generated such that you can reach any intersection from any other
+ * intersection and that there is at most one road between any two
+ * intersections. you are given an integer 'n' and a 2d integer array 'roads'
+ * where 'roads[i] = [u_i, v_i, t_i]' means that there is a road between
+ * intersections 'u' and 'v' that takes 't' minutes to travel. you want to know
+ * in how many ways you can travel from interseciton 0 to intersection 'n - 1'.
+ */
+
+class Solution {
+public:
+ int countPaths(int n, vector<vector<int>> &roads) {
+ vector<vector<pair<long long, long long>>> graph(n);
+ for (auto &r : roads) {
+ long long u = r[0], v = r[1], t = r[2];
+ graph[u].push_back({v, t});
+ graph[v].push_back({u, t});
+ }
+ return dijkstra(graph, n, 0);
+ }
+
+private:
+ int mod = 1e9 + 7;
+ int dijkstra(const vector<vector<pair<long long, long long>>> &graph, int n,
+ int src) {
+ vector<long long> dist(n, LONG_MAX), ways(n);
+ ways[src] = 1;
+ dist[src] = 0;
+ priority_queue<pair<long long, long long>,
+ vector<pair<long long, long long>>, greater<>>
+ pq;
+ pq.push({0, 0});
+ while (!pq.empty()) {
+ auto [d, u] = pq.top();
+ pq.pop();
+ if (d > dist[u])
+ continue;
+ for (auto [v, t] : graph[u]) {
+ if (dist[v] > d + t) {
+ dist[v] = d + t;
+ ways[v] = ways[u];
+ } else if (dist[v] == d + t)
+ ways[v] = (ways[v] + ways[u]) % mod;
+ }
+ }
+ return ways[n - 1];
+ }
+};
+
+int main() {
+ Solution obj;
+ vvd r1 = {{0, 6, 7}, {0, 1, 2}, {1, 2, 3}, {1, 3, 3}, {6, 3, 3},
+ {3, 5, 1}, {6, 5, 1}, {2, 5, 1}, {0, 4, 5}, {4, 6, 2}};
+ vvd r2 = {{1, 0, 10}};
+ printf("%d\n", obj.countPaths(7, r1)); // expect: 4
+ printf("%d\n", obj.countPaths(2, r2)); // expect: 1
+}
diff --git a/partition_labels.c b/partition_labels.c
new file mode 100644
index 0000000..eb06b60
--- /dev/null
+++ b/partition_labels.c
@@ -0,0 +1,42 @@
+// 763. Partition Labels
+#include "leetcode.h"
+
+/*
+ * you are given a string 's'. we want to partition the string into as many
+ * parts as possible so that each letter appears in at most one part. for
+ * example, the string 'ababcc' can be partitioned into '["abab", "cc"]'. note
+ * that the partition is done so that after concatenating all the parts in
+ * order, the resultant string should be 's'. return a list of integers
+ * representing the size of these parts.
+ */
+
+int *partitionLabels(char *s, int *returnSize) {
+ int n = strlen(s), start = 0, end = 0, curr = 0;
+ int *ans = (int *)calloc(n, sizeof(int)), hash[26] = {0};
+ for (int i = 0; i < n; i++)
+ hash[s[i] - 'a'] = i;
+ for (int i = 0; i < n; i++) {
+ int prev = hash[s[i] - 'a'];
+ end = end > prev ? end : prev;
+ if (end == i) {
+ ans[curr++] = end - start + 1;
+ start = end + 1;
+ }
+ }
+ *returnSize = curr;
+ return ans;
+}
+
+int main() {
+ char *s1 = "ababcbacadefegdehijhklij", *s2 = "eccbbbbdec";
+ int rs1, *pl1 = partitionLabels(s1, &rs1);
+ int rs2, *pl2 = partitionLabels(s2, &rs2);
+ for (int i = 0; i < rs1; i++)
+ printf("%d ", pl1[i]); // expect: 9 7 8
+ printf("\n");
+ for (int i = 0; i < rs2; i++)
+ printf("%d ", pl2[i]); // expect: 10
+ printf("\n");
+ free(pl1);
+ free(pl2);
+}
diff --git a/partition_labels.py b/partition_labels.py
new file mode 100644
index 0000000..13556c5
--- /dev/null
+++ b/partition_labels.py
@@ -0,0 +1,34 @@
+# 763. Partition Labels
+
+"""
+you are given a string 's'. we want to partition the string into as many
+parts as possible so that each letter appears in at most one part. for
+example, the string 'ababcc' can be partitioned into '["abab", "cc"]'. note
+that the partition is done so that after concatenating all the parts in
+order, the resultant string should be 's'. return a list of integers
+representing the size of these parts.
+"""
+
+
+class Solution(object):
+ def partitionLabels(self, s):
+ """
+ :type s: str
+ :rtype: List[int]
+ """
+ curr, ans = 0, [0]
+ ends = {c: i for i, c in enumerate(s)}
+ while curr < len(s):
+ prev = ends[s[curr]]
+ while curr <= prev:
+ sym = s[curr]
+ prev = max(prev, ends[sym])
+ curr += 1
+ ans.append(curr)
+ return [ans[i] - ans[i - 1] for i in range(1, len(ans))]
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.partitionLabels(s="ababcbacadefegdehijhklij"))
+ print(obj.partitionLabels(s="eccbbbbdec"))
diff --git a/shopping_offers.c b/shopping_offers.c
new file mode 100644
index 0000000..bc7b735
--- /dev/null
+++ b/shopping_offers.c
@@ -0,0 +1,122 @@
+// 638. Shopping Offers
+#include "leetcode.h"
+
+/*
+ * in leetcode store, there are 'n' items to sell. each item has a price.
+ * however, there are some special offers, and a special offer consists of one
+ * or more different kinds of items with a sale price. you are given an integer
+ * array 'price' where 'price[i]' is the price of the i'th item, and an integer
+ * array 'needs' where 'needs[i]' is the number of pieces the i'th item you want
+ * to buy. you are also given an array 'special', where 'special[i]' is of size
+ * 'n + 1' where 'special[i][j]' is the number of pieces of the j'th item in the
+ * i'th other. return the lowest price you have to pay for exactly certain items
+ * as given, where you could make optimal use of the special offers. you are not
+ * allowed to buy more items that you want, even if that would lower the overall
+ * price.
+ */
+
+#define MOD 1009
+
+struct node {
+ struct node *next;
+ int key;
+ int val;
+};
+
+struct node *hash[MOD];
+
+void hash_init(void) { memset((void *)hash, 0, sizeof(hash)); }
+
+void hash_push(int key, int val) {
+ int idx = key % MOD;
+ struct node *tmp = (struct node *)malloc(sizeof(struct node));
+ tmp->key = key;
+ tmp->val = val;
+ tmp->next = hash[idx];
+ hash[idx] = tmp;
+}
+
+int hash_pop(int key) {
+ int idx = key % MOD;
+ struct node *tmp = hash[idx];
+ for (; tmp; tmp = tmp->next)
+ if (tmp->key == key)
+ return tmp->val;
+ return -1;
+}
+
+void hash_free(void) {
+ for (int i = 0; i < MOD; i++)
+ for (struct node *tmp = hash[i], *del; tmp;) {
+ del = tmp;
+ tmp = tmp->next;
+ free(del);
+ }
+}
+
+int lowest_price(int n, int need, int *prices, int **special, int specialSize,
+ int *specialColSize) {
+ int min = INT_MAX, price = 0, tmp;
+ bool accept = true;
+ if (!need)
+ return 0;
+ price = hash_pop(need);
+ if (price >= 0)
+ return price;
+ price = 0;
+ tmp = need;
+ for (int i = 0; i < n; i++) {
+ price += prices[i] * (tmp & 0x0F);
+ tmp >>= 4;
+ }
+ min = fmin(min, price);
+ for (int i = 0; i < specialSize; i++) {
+ tmp = need;
+ accept = true;
+ for (int j = 0; j < n; j++) {
+ int quantity = (tmp >> (j * 4)) & 0x0F;
+ if (quantity >= special[i][j]) {
+ quantity -= special[i][j];
+ tmp &= ~(0x0F << (j * 4));
+ tmp |= (quantity << (j * 4));
+ } else {
+ accept = false;
+ break;
+ }
+ }
+ if (accept) {
+ price = special[i][n] + lowest_price(n, tmp, prices, special, specialSize,
+ specialColSize);
+ min = fmin(min, price);
+ }
+ }
+ hash_push(need, min);
+ return min;
+}
+
+int shoppingOffers(int *price, int priceSize, int **special, int specialSize,
+ int *specialColSize, int *needs, int needsSize) {
+ int need = 0, ans;
+ hash_init();
+ for (int i = 0; i < needsSize; i++)
+ need |= (needs[i] << (i * 4));
+ ans = lowest_price(priceSize, need, price, special, specialSize,
+ specialColSize);
+ hash_free();
+ return ans;
+}
+
+int main() {
+ int p1[] = {2, 5}, s1i[2][3] = {{3, 0, 5}, {1, 2, 10}}, n1[] = {3, 2};
+ int p2[] = {2, 3, 4}, s2i[2][4] = {{1, 1, 0, 4}, {2, 2, 1, 9}},
+ n2[] = {1, 2, 1};
+ struct two_d_arr s1, s2;
+ two_d_arr_init(&s1, ARRAY_SIZE(s1i), ARRAY_SIZE(s1i[0]), s1i);
+ two_d_arr_init(&s2, ARRAY_SIZE(s2i), ARRAY_SIZE(s2i[0]), s2i);
+ printf("%d\n", shoppingOffers(p1, ARRAY_SIZE(p1), s1.arr, s1.row_size,
+ s1.col_size, n1, ARRAY_SIZE(n1))); // expect: 14
+ printf("%d\n", shoppingOffers(p2, ARRAY_SIZE(p2), s2.arr, s2.row_size,
+ s2.col_size, n2, ARRAY_SIZE(n2))); // expect: 11
+ two_d_arr_free(&s1);
+ two_d_arr_free(&s2);
+}
diff --git a/shopping_offers.py b/shopping_offers.py
new file mode 100644
index 0000000..42da709
--- /dev/null
+++ b/shopping_offers.py
@@ -0,0 +1,49 @@
+# 638. Shopping Offers
+
+"""
+in leetcode store, there are 'n' items to sell. each item has a price.
+however, there are some special offers, and a special offer consists of one
+or more different kinds of items with a sale price. you are given an integer
+array 'price' where 'price[i]' is the price of the i'th item, and an integer
+array 'needs' where 'needs[i]' is the number of pieces the i'th item you want
+to buy. you are also given an array 'special', where 'special[i]' is of size
+'n + 1' where 'special[i][j]' is the number of pieces of the j'th item in the
+i'th other. return the lowest price you have to pay for exactly certain items
+as given, where you could make optimal use of the special offers. you are not
+allowed to buy more items that you want, even if that would lower the overall
+price.
+"""
+
+
+class Solution(object):
+ def shoppingOffers(self, price, special, needs):
+ """
+ :type price: List[int]
+ :type special: List[List[int]]
+ :type needs: List[int]
+ :rtype: int
+ """
+ dp = {}
+
+ def dfs(curr):
+ val = sum(curr[i] * price[i] for i in range(len(needs)))
+ for *spec, cost in special:
+ tmp = [curr[j] - spec[j] for j in range(len(needs))]
+ if min(tmp) >= 0: # skip deals that exceed needs
+ val = min(val, dp.get(tuple(tmp), dfs(tmp)) + cost)
+ dp[tuple(curr)] = val
+ return val
+
+ return dfs(needs)
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(
+ obj.shoppingOffers(price=[2, 5], special=[[3, 0, 5], [1, 2, 10]], needs=[3, 2])
+ )
+ print(
+ obj.shoppingOffers(
+ price=[2, 3, 4], special=[[1, 1, 0, 4], [2, 2, 1, 9]], needs=[1, 2, 1]
+ )
+ )
diff --git a/sum_subset_xor.c b/sum_subset_xor.c
index cb51647..7c32618 100644
--- a/sum_subset_xor.c
+++ b/sum_subset_xor.c
@@ -8,26 +8,11 @@
* if 'a' can be obtained from 'b' by deleting some elements of 'b'.
*/
-void backtrack(int *nums, int numsSize, int tar, int idx, int *cnt) {
- if (idx == numsSize) {
- return;
- } else {
- for (int i = idx; i < numsSize; i++) {
- tar ^= nums[i];
- *cnt += tar;
- backtrack(nums, numsSize, tar, i + 1, cnt);
- tar ^= nums[i];
- }
- }
-}
-
int subsetXORSum(int *nums, int numsSize) {
- int ans = 0;
- for (int i = 0; i < numsSize; i++) {
- ans += nums[i];
- backtrack(nums, numsSize, nums[i], i + 1, &ans);
- }
- return ans;
+ int all = 0, mult = 1 << (numsSize - 1);
+ for (int i = 0; i < numsSize; i++)
+ all |= nums[i];
+ return all * mult;
}
int main() {
diff --git a/sum_subset_xor.py b/sum_subset_xor.py
index deb88ed..0560197 100644
--- a/sum_subset_xor.py
+++ b/sum_subset_xor.py
@@ -1,4 +1,6 @@
# 1863. Sum of All Subset XOR Totals
+from functools import reduce
+from operator import or_
"""
the xor total of an array is defined as the bitwise xor of all its elements
@@ -14,25 +16,7 @@ class Solution(object):
:type nums: List[int]
:rtype: int
"""
-
- def backtrack(nums, idx, tar, cnt):
- if idx == len(nums):
- cnt.append(tar[:])
- return
- tar.append(nums[idx])
- backtrack(nums, idx + 1, tar, cnt)
- tar.pop()
- backtrack(nums, idx + 1, tar, cnt)
-
- cnt = []
- backtrack(nums, 0, [], cnt)
- ans = 0
- for i in cnt:
- total = 0
- for n in i:
- total ^= n
- ans += total
- return ans
+ return reduce(or_, nums) << (len(nums) - 1)
if __name__ == "__main__":
diff --git a/total_hamming_distance.c b/total_hamming_distance.c
new file mode 100644
index 0000000..571f417
--- /dev/null
+++ b/total_hamming_distance.c
@@ -0,0 +1,25 @@
+// 477. Total Hamming Distance
+#include "leetcode.h"
+
+/*
+ * the hamming distance between two integers is the number of positions at which
+ * the corresponding bits are different. given an integer array 'nums', return
+ * the sum of hamming distances between all the pairs of the integers in 'nums'.
+ */
+
+int totalHammingDistance(int *nums, int numsSize) {
+ int total = 0;
+ for (int i = 0; i < 32; i++) {
+ int cnt = 0;
+ for (int j = 0; j < numsSize; j++)
+ cnt += (nums[j] >> i) & 1;
+ total += cnt * (numsSize - cnt);
+ }
+ return total;
+}
+
+int main() {
+ int n1[] = {4, 14, 2}, n2[] = {4, 14, 4};
+ printf("%d\n", totalHammingDistance(n1, ARRAY_SIZE(n1))); // expect: 6
+ printf("%d\n", totalHammingDistance(n2, ARRAY_SIZE(n2))); // expect: 4
+}
diff --git a/total_hamming_distance.py b/total_hamming_distance.py
new file mode 100644
index 0000000..3098372
--- /dev/null
+++ b/total_hamming_distance.py
@@ -0,0 +1,27 @@
+# 477. Total Hamming Distance
+
+"""
+the hamming distance between two integers is the number of positions at which
+the corresponding bits are different. given an integer array 'nums', return
+the sum of hamming distances between all the pairs of the integers in 'nums'.
+"""
+
+
+class Solution(object):
+ def totalHammingDistance(self, nums):
+ """
+ :type nums: List[int]
+ :rtype: int
+ """
+ bits = [[0, 0] for _ in range(32)]
+ for i in nums:
+ for j in bits:
+ j[i % 2] += 1
+ i /= 2
+ return sum(x * y for x, y in bits)
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.totalHammingDistance(nums=[4, 14, 2]))
+ print(obj.totalHammingDistance(nums=[4, 14, 4]))
diff --git a/zero_array_transformation2.c b/zero_array_transformation2.c
new file mode 100644
index 0000000..4532469
--- /dev/null
+++ b/zero_array_transformation2.c
@@ -0,0 +1,71 @@
+// 3356. Zero Array Transformation II
+#include "leetcode.h"
+
+/*
+ * you are given an integer array 'nums' of length 'n' and a 2d array 'queries'
+ * where 'queries[i] [l_i, r_i, val_i]'. each 'queries[i]' represents the
+ * following action on 'nums': decrement the value at each index in the range
+ * '[l_i, r_i]' in 'nums' by at most 'val_i'. the amount by which each value is
+ * decremented can be chosen independently for each index. a zero array is an
+ * array with all its elements equal to 0. return the minimum possible
+ * non-negative value of 'k', such that after processing the first 'k' queries
+ * in sequence, 'nums' becomes a zero array. if no such 'k' exists, return -1.
+ */
+
+bool can_cover(int *nums, int n, int **queries, int k) {
+ int *diff = (int *)calloc(n + 1, sizeof(int));
+ for (int i = 0; i < k; i++) {
+ int l = queries[i][0];
+ int r = queries[i][1];
+ int val = queries[i][2];
+ diff[l] += val;
+ if (r + 1 < n)
+ diff[r + 1] -= val;
+ }
+ int sum = 0;
+ for (int i = 0; i < n; i++) {
+ sum += diff[i];
+ if (sum < nums[i]) {
+ free(diff);
+ return false;
+ }
+ }
+ free(diff);
+ return true;
+}
+
+int minZeroArray(int *nums, int numsSize, int **queries, int queriesSize,
+ int *queriesColSize) {
+ int already_zero = 1;
+ for (int i = 0; i < numsSize; i++)
+ if (nums[i]) {
+ already_zero = 0;
+ break;
+ }
+ if (already_zero)
+ return 0;
+ int l = 1, r = queriesSize, ans = -1;
+ while (l <= r) {
+ int mid = l + (r - l) / 2;
+ if (can_cover(nums, numsSize, queries, mid)) {
+ ans = mid;
+ r = mid - 1;
+ } else
+ l = mid + 1;
+ }
+ return ans;
+}
+
+int main() {
+ int n1[] = {2, 0, 2}, q1i[3][3] = {{0, 2, 1}, {0, 2, 1}, {1, 1, 3}};
+ int n2[] = {4, 3, 2, 1}, q2i[2][3] = {{1, 3, 2}, {0, 2, 1}};
+ struct two_d_arr q1, q2;
+ two_d_arr_init(&q1, ARRAY_SIZE(q1i), ARRAY_SIZE(q1i[0]), q1i);
+ two_d_arr_init(&q2, ARRAY_SIZE(q2i), ARRAY_SIZE(q2i[0]), q2i);
+ printf("%d\n", minZeroArray(n1, ARRAY_SIZE(n1), q1.arr, q1.row_size,
+ q1.col_size)); // expect: 2
+ printf("%d\n", minZeroArray(n2, ARRAY_SIZE(n2), q2.arr, q2.row_size,
+ q2.col_size)); // expect: -1
+ two_d_arr_free(&q1);
+ two_d_arr_free(&q2);
+}
diff --git a/zero_array_transformation2.py b/zero_array_transformation2.py
new file mode 100644
index 0000000..1b462e5
--- /dev/null
+++ b/zero_array_transformation2.py
@@ -0,0 +1,41 @@
+# 3356. Zero Array Transformation II
+
+"""
+you are given an integer array 'nums' of length 'n' and a 2d array 'queries'
+where 'queries[i] [l_i, r_i, val_i]'. each 'queries[i]' represents the
+following action on 'nums': decrement the value at each index in the range
+'[l_i, r_i]' in 'nums' by at most 'val_i'. the amount by which each value is
+decremented can be chosen independently for each index. a zero array is an
+array with all its elements equal to 0. return the minimum possible
+non-negative value of 'k', such that after processing the first 'k' queries
+in sequence, 'nums' becomes a zero array. if no such 'k' exists, return -1.
+"""
+
+
+class Solution(object):
+ def minZeroArray(self, nums, queries):
+ """
+ :type nums: List[int]
+ :type queries: List[List[int]]
+ :rtype: int
+ """
+ n, ans, k = len(nums), 0, 0
+ cnt = [0 for _ in range(n + 1)]
+ for i in range(n):
+ while k + cnt[i] < nums[i]:
+ ans += 1
+ if ans - 1 >= len(queries):
+ return -1
+ l, r, val = queries[ans - 1]
+ if r < i:
+ continue
+ cnt[max(l, i)] += val
+ cnt[r + 1] -= val
+ k += cnt[i]
+ return ans
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.minZeroArray(nums=[2, 0, 2], queries=[[0, 2, 1], [0, 2, 1], [1, 1, 3]]))
+ print(obj.minZeroArray(nums=[4, 3, 2, 1], queries=[[1, 3, 2], [0, 2, 1]]))