aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--count_num_arr_k_match_elem.c48
-rw-r--r--count_num_arr_k_match_elem.py28
-rw-r--r--divide_array_max_diff.c69
-rw-r--r--divide_array_max_diff.py17
-rw-r--r--partition_arr_max_diff_k.c32
-rw-r--r--partition_arr_max_diff_k.py34
6 files changed, 205 insertions, 23 deletions
diff --git a/count_num_arr_k_match_elem.c b/count_num_arr_k_match_elem.c
new file mode 100644
index 0000000..dd8838e
--- /dev/null
+++ b/count_num_arr_k_match_elem.c
@@ -0,0 +1,48 @@
+// 3405. Count the Number of Arrays with K Matching Adjacent Elements
+#include "leetcode.h"
+
+/*
+ * you are given three integers 'n', 'm', and 'k'. a good array 'arr' of size
+ * 'n' is defined as follows: each element in 'arr' is in inclusive range '[1,
+ * m]', and exactly 'k' indices 'i' where '1 <= i < n' satisfy the condition
+ * 'arr[i - 1] == arr[i]'. return the number of good arrays that can be formed.
+ * since the answer may be very large, return it modulo 10^9+7.
+ */
+
+const int mod = 1e9 + 7;
+
+long long mult(long long n, long long m) { return (n * m) % mod; }
+
+long long power(long long n, long long m) {
+ long long res = 1, base = n;
+ while (m > 0) {
+ if (m & 1)
+ res = mult(res, base);
+ base = mult(base, base);
+ m >>= 1;
+ }
+ return res;
+}
+
+long long inv(long long n) { return power(n, mod - 2); }
+
+long long factorial(long long n) {
+ long long res = 1;
+ for (long long i = 2; i <= n; ++i)
+ res = mult(res, i);
+ return res;
+}
+
+long long combine(long long n, long long m) {
+ return mult(factorial(n), inv(mult(factorial(m), factorial(n - m))));
+}
+
+int countGoodArrays(int n, int m, int k) {
+ return mult(mult(combine(n - 1, n - 1 - k), m), power(m - 1, n - 1 - k));
+}
+
+int main() {
+ printf("%d\n", countGoodArrays(3, 2, 1)); // expect: 4
+ printf("%d\n", countGoodArrays(4, 2, 2)); // expect: 6
+ printf("%d\n", countGoodArrays(5, 2, 0)); // expect: 2
+}
diff --git a/count_num_arr_k_match_elem.py b/count_num_arr_k_match_elem.py
new file mode 100644
index 0000000..a3bc73f
--- /dev/null
+++ b/count_num_arr_k_match_elem.py
@@ -0,0 +1,28 @@
+# 3405. Count the Number of Arrays with K Matching Adjacent Elements
+from math import comb
+
+"""
+you are given three integers 'n', 'm', and 'k'. a good array 'arr' of size
+'n' is defined as follows: each element in 'arr' is in inclusive range '[1,
+m]', and exactly 'k' indices 'i' where '1 <= i < n' satisfy the condition
+'arr[i - 1] == arr[i]'. return the number of good arrays that can be formed.
+since the answer may be very large, return it modulo 10^9+7.
+"""
+
+
+class Solution(object):
+ def countGoodArrays(self, n, m, k):
+ """
+ :type n: int
+ :type m: int
+ :type k: int
+ :rtype: int
+ """
+ return m * pow(m - 1, n - k - 1, mod := 1**9 + 7) * comb(n - 1, k) % mod
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.countGoodArrays(n=3, m=2, k=1))
+ print(obj.countGoodArrays(n=4, m=2, k=2))
+ print(obj.countGoodArrays(n=5, m=2, k=0))
diff --git a/divide_array_max_diff.c b/divide_array_max_diff.c
index 72e8648..8c510b3 100644
--- a/divide_array_max_diff.c
+++ b/divide_array_max_diff.c
@@ -11,25 +11,66 @@
* return any of them
*/
-int cmp(const void *a, const void *b) { return (*(int *)a) - (*(int *)b); }
+int cmp(const void *a, const void *b) { return (*(int *)a - *(int *)b); }
int **divideArray(int *nums, int numsSize, int k, int *returnSize,
int **returnColumnSizes) {
- int num_arr = numsSize / 3;
- int **ans = (int **)calloc(num_arr, sizeof(int *));
- *returnColumnSizes = (int *)calloc(num_arr, sizeof(int));
- *returnSize = 0;
qsort(nums, numsSize, sizeof(int), cmp);
- for (int i = 0; i < num_arr; i++) {
- ans[i] = (int *)calloc(3, sizeof(int));
- (*returnColumnSizes)[i] = 3;
- for (int j = 0; j < 3; j++) {
- int idx = i * 3 + j;
- if (j && nums[idx] - nums[i * 3] > k)
- return ans;
- ans[i][j] = nums[idx];
+ int **ans = (int **)malloc((numsSize / 3) * sizeof(int *)), rs = 0;
+ for (int i = 2; i < numsSize; i += 3) {
+ if (nums[i] - nums[i - 2] > k) {
+ *returnSize = 0;
+ return NULL;
}
+ ans[rs] = (int *)malloc(3 * sizeof(int));
+ ans[rs][0] = nums[i - 2];
+ ans[rs][1] = nums[i - 1];
+ ans[rs][2] = nums[i];
+ rs++;
}
- *returnSize = num_arr;
+ *returnSize = rs;
+ *returnColumnSizes = (int *)malloc(rs * sizeof(int));
+ for (int i = 0; i < rs; i++)
+ (*returnColumnSizes)[i] = 3;
return ans;
}
+
+int main() {
+ int n1[] = {1, 3, 4, 8, 7, 9, 3, 5, 1}, rs1, *rcs1;
+ int n2[] = {2, 4, 2, 2, 5, 2}, rs2, *rcs2;
+ int n3[] = {4, 2, 9, 8, 2, 12, 7, 12, 10, 5, 8, 5, 5, 7, 9, 2, 5, 11}, rs3,
+ *rcs3;
+ int **da1 = divideArray(n1, ARRAY_SIZE(n1), 2, &rs1, &rcs1);
+ int **da2 = divideArray(n2, ARRAY_SIZE(n2), 2, &rs2, &rcs2);
+ int **da3 = divideArray(n3, ARRAY_SIZE(n3), 14, &rs3, &rcs3);
+ for (int i = 0; i < rs1; i++) {
+ for (int j = 0; j < rcs1[i]; j++)
+ printf("%d ", da1[i][j]); // expect: [[1,1,3],[3,4,5],[7,8,9]]
+ printf("\n");
+ }
+ printf("\n");
+ for (int i = 0; i < rs2; i++) {
+ for (int j = 0; j < rcs2[i]; j++)
+ printf("%d ", da2[i][j]); // expect: null
+ printf("\n");
+ }
+ printf("\n");
+ for (int i = 0; i < rs3; i++) {
+ for (int j = 0; j < rcs3[i]; j++)
+ printf(
+ "%d ",
+ da3[i][j]); // expect:
+ // [[2,2,12],[4,8,5],[5,9,7],[7,8,5],[5,9,10],[11,12,2]]
+ printf("\n");
+ }
+ printf("\n");
+ for (int i = 0; i < rs1; i++)
+ free(da1[i]), free(rcs1);
+ free(da1);
+ for (int i = 0; i < rs2; i++)
+ free(da2[i]), free(rcs2);
+ free(da1);
+ for (int i = 0; i < rs3; i++)
+ free(da3[i]), free(rcs3);
+ free(da1);
+}
diff --git a/divide_array_max_diff.py b/divide_array_max_diff.py
index 41a2a22..3bdf682 100644
--- a/divide_array_max_diff.py
+++ b/divide_array_max_diff.py
@@ -18,18 +18,12 @@ class Solution(object):
:type k: int
:rtype: List[List[int]]
"""
- size = len(nums)
- if size % 3 != 0:
- return []
nums.sort()
ans = []
- group_idx = 0
- for i in range(0, size, 3):
- if i + 2 < size and nums[i + 2] - nums[i] <= k:
- ans.append([nums[i], nums[i + 1], nums[i + 2]])
- group_idx += 1
- else:
+ for i in range(2, len(nums), 3):
+ if nums[i] - nums[i - 2] > k:
return []
+ ans.append([nums[i - 2], nums[i - 1], nums[i]])
return ans
@@ -37,3 +31,8 @@ if __name__ == "__main__":
obj = Solution()
print(obj.divideArray(nums=[1, 3, 4, 8, 7, 9, 3, 5, 1], k=2))
print(obj.divideArray(nums=[1, 3, 3, 2, 7, 3], k=3))
+ print(
+ obj.divideArray(
+ nums=[4, 2, 9, 8, 2, 12, 7, 12, 10, 5, 8, 5, 5, 7, 9, 2, 5, 11], k=14
+ )
+ )
diff --git a/partition_arr_max_diff_k.c b/partition_arr_max_diff_k.c
new file mode 100644
index 0000000..4a1e3aa
--- /dev/null
+++ b/partition_arr_max_diff_k.c
@@ -0,0 +1,32 @@
+// 2294. Partition Array Such That Maximum Difference Is K
+#include "leetcode.h"
+
+/*
+ * you are given an integer array 'nums' and an integer 'k'. you may partition
+ * 'nums' into one or more subsequences such that each element in 'nums' appears
+ * in exactly one of the subsequences. return the minimum number of subsequences
+ * needed such that the difference between the maximum and minimum values in
+ * each subsequence is at most 'k'. a subsequence is a sequence that can be
+ * derived from another sequence by deleting some or no elements without
+ * changing the order of the remaining elements.
+ */
+
+int cmp(const void *a, const void *b) { return (*(int *)a - *(int *)b); }
+
+int partitionArray(int *nums, int numsSize, int k) {
+ qsort(nums, numsSize, sizeof(int), cmp);
+ int ans = 1, j = 0;
+ for (int i = 1; i < numsSize; i++)
+ if (nums[i] - nums[j] > k) {
+ ans++;
+ j = i;
+ }
+ return ans;
+}
+
+int main() {
+ int n1[] = {3, 6, 1, 2, 5}, n2[] = {1, 2, 3}, n3[] = {2, 2, 4, 5};
+ printf("%d\n", partitionArray(n1, ARRAY_SIZE(n1), 2)); // expect: 2
+ printf("%d\n", partitionArray(n2, ARRAY_SIZE(n2), 1)); // expect: 2
+ printf("%d\n", partitionArray(n3, ARRAY_SIZE(n3), 0)); // expect: 3
+}
diff --git a/partition_arr_max_diff_k.py b/partition_arr_max_diff_k.py
new file mode 100644
index 0000000..555cdf9
--- /dev/null
+++ b/partition_arr_max_diff_k.py
@@ -0,0 +1,34 @@
+# 2294. Partition Array Such That Maximum Difference Is K
+
+"""
+you are given an integer array 'nums' and an integer 'k'. you may partition
+'nums' into one or more subsequences such that each element in 'nums' appears
+in exactly one of the subsequences. return the minimum number of subsequences
+needed such that the difference between the maximum and minimum values in
+each subsequence is at most 'k'. a subsequence is a sequence that can be
+derived from another sequence by deleting some or no elements without
+changing the order of the remaining elements.
+"""
+
+
+class Solution(object):
+ def partitionArray(self, nums, k):
+ """
+ :type nums: List[int]
+ :type k: int
+ :rtype: int
+ """
+ nums.sort()
+ ans, j = 1, 0
+ for i in range(len(nums)):
+ if nums[i] - nums[j] > k:
+ ans += 1
+ j = i
+ return ans
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.partitionArray(nums=[3, 6, 1, 2, 5], k=2))
+ print(obj.partitionArray(nums=[1, 2, 3], k=1))
+ print(obj.partitionArray(nums=[2, 2, 4, 5], k=0))