aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--beautiful_arrangement2.c38
-rw-r--r--beautiful_arrangement2.py36
-rw-r--r--check_digit_eq_str_op2.c64
-rw-r--r--check_digit_eq_str_op2.py45
-rw-r--r--count_and_say.c68
-rw-r--r--count_and_say.py35
-rw-r--r--count_complete_subarr_arr.c50
-rw-r--r--count_complete_subarr_arr.py35
-rw-r--r--count_equal_div_pair_arr.c23
-rw-r--r--count_equal_div_pair_arr.py37
-rw-r--r--count_good_numbers.c21
-rw-r--r--count_good_numbers.py19
-rw-r--r--count_good_triplet_arr.c64
-rw-r--r--count_good_triplet_arr.py38
-rw-r--r--count_good_triplets.c29
-rw-r--r--count_good_triplets.py36
-rw-r--r--count_hidden_sequences.c29
-rw-r--r--count_hidden_sequences.py30
-rw-r--r--count_interesting_subarr.c83
-rw-r--r--count_interesting_subarr.py34
-rw-r--r--count_largest_group.c37
-rw-r--r--count_largest_group.py39
-rw-r--r--count_num_fair_pairs.c51
-rw-r--r--count_num_fair_pairs.py5
-rw-r--r--count_num_good_subarr.c94
-rw-r--r--count_num_good_subarr.py35
-rw-r--r--count_num_ideal_arr.c36
-rw-r--r--count_num_ideal_arr.py38
-rw-r--r--count_number_powerful_integers.cpp41
-rw-r--r--count_number_powerful_integers.py47
-rw-r--r--count_symmetric_integers.c112
-rw-r--r--count_symmetric_integers.py34
-rw-r--r--find_count_good_int.c115
-rw-r--r--find_count_good_int.py71
-rw-r--r--max_product_len_palindrome_subseq.c46
-rw-r--r--max_product_len_palindrome_subseq.py46
-rw-r--r--min_num_flip_bin_grid_palin2.c50
-rw-r--r--min_num_flip_bin_grid_palin2.py42
-rw-r--r--min_num_op_elem_distinct.c30
-rw-r--r--min_num_op_elem_distinct.py31
-rw-r--r--min_ops_arr_eq_k.c35
-rw-r--r--min_ops_arr_eq_k.py37
-rw-r--r--rabbits_in_forest.c36
-rw-r--r--rabbits_in_forest.py30
-rw-r--r--range_product_queries_powers.c79
-rw-r--r--range_product_queries_powers.py41
-rw-r--r--substring_xor_queries.c137
-rw-r--r--substring_xor_queries.py43
48 files changed, 2157 insertions, 95 deletions
diff --git a/beautiful_arrangement2.c b/beautiful_arrangement2.c
new file mode 100644
index 0000000..37e2dcb
--- /dev/null
+++ b/beautiful_arrangement2.c
@@ -0,0 +1,38 @@
+// 667. Beautiful Arrangement II
+#include "leetcode.h"
+
+/*
+ * given two integers 'n' and 'k', construct a list 'answer' that contains 'n'
+ * different positive integers ranging from 1 to 'n' and obeys the following
+ * requirement: suppose this list is 'answer = [a1, a2, a3, ..., an]', the the
+ * list '[a1 - a2, a2 - a3, ..., an-1 - an]' has exactly 'k' distinct integers.
+ * return the list 'answer'. if there are multiple valid answers, return any of
+ * them.
+ */
+
+int *constructArray(int n, int k, int *returnSize) {
+ *returnSize = n;
+ int *ans = (int *)malloc(n * sizeof(int));
+ int left = 1, right = n;
+ for (int i = 0; i < n; i++) {
+ if (k > 1) {
+ ans[i] = (k & 1) ? left++ : right--;
+ k--;
+ } else
+ ans[i] = left++;
+ }
+ return ans;
+}
+
+int main() {
+ int rs1, *ca1 = constructArray(3, 1, &rs1);
+ int rs2, *ca2 = constructArray(3, 2, &rs2);
+ for (int i = 0; i < rs1; i++)
+ printf("%d ", ca1[i]); // expect: 1 2 3
+ printf("\n");
+ for (int i = 0; i < rs2; i++)
+ printf("%d ", ca2[i]); // expect: 1 3 2
+ printf("\n");
+ free(ca1);
+ free(ca2);
+}
diff --git a/beautiful_arrangement2.py b/beautiful_arrangement2.py
new file mode 100644
index 0000000..9bdfd1a
--- /dev/null
+++ b/beautiful_arrangement2.py
@@ -0,0 +1,36 @@
+# 667. Beautiful Arrangement II
+
+"""
+given two integers 'n' and 'k', construct a list 'answer' that contains 'n'
+different positive integers ranging from 1 to 'n' and obeys the following
+requirement: suppose this list is 'answer = [a1, a2, a3, ..., an]', the the
+list '[a1 - a2, a2 - a3, ..., an-1 - an]' has exactly 'k' distinct integers.
+return the list 'answer'. if there are multiple valid answers, return any of
+them.
+"""
+
+
+class Solution(object):
+ def constructArray(self, n, k):
+ """
+ :type n: int
+ :type k: int
+ :rtype: List[int]
+ """
+ ans, left, right = [0] * n, 1, k + 1
+ for i in range(k + 1):
+ if i & 1:
+ ans[i] = right
+ right -= 1
+ else:
+ ans[i] = left
+ left += 1
+ for i in range(k + 1, n):
+ ans[i] = i + 1
+ return ans
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.constructArray(3, 1))
+ print(obj.constructArray(3, 2))
diff --git a/check_digit_eq_str_op2.c b/check_digit_eq_str_op2.c
new file mode 100644
index 0000000..6b54de1
--- /dev/null
+++ b/check_digit_eq_str_op2.c
@@ -0,0 +1,64 @@
+// 3463. Check If Digits Are Equal in String After Operations II
+#include "leetcode.h"
+
+/*
+ * you are given a string 's' consisting of digits. perform the following
+ * operation repeatedly until the string has exactly two digits: for each pair
+ * of consecutive digits in 's', starting from the first digit, calculate a new
+ * digit as the sum of the two digits modulo 10. replace 's' with the sequence
+ * of newly calculated digits, maintaining the order in which they are computed.
+ * return 'true' if the final two digits in 's' are the same; otherwise return
+ * false.
+ */
+
+static inline int gcd(int a, int b) {
+ while (b) {
+ a ^= b ^= a ^= b;
+ b %= a;
+ }
+ return a;
+}
+
+static inline void fac(int a, int mod, int *r, int *cnt) {
+ int num = 0;
+ while (a && !(a % mod)) {
+ num++;
+ a /= mod;
+ }
+ *r = a % mod;
+ *cnt = num;
+}
+
+static inline int inv_mod(int a, int mod) {
+ for (int i = 1; i < mod; i++)
+ if ((a * i) % mod == 1)
+ return i;
+ return 0;
+}
+
+static bool test(int mod, char *s) {
+ int n = strlen(s), res = 0, r = 1, c = 0;
+ for (int i = 0; i < n - 1; i++) {
+ if (!c) {
+ res = (res + r * ((s[i] - '0') - (s[i + 1] - '0'))) % mod;
+ if (res < 0)
+ res += mod;
+ }
+ int rr, cc;
+ fac(n - 2 - i, mod, &rr, &cc);
+ r = (r * rr) % mod;
+ c += cc;
+ fac(i + 1, mod, &rr, &cc);
+ r = (r * inv_mod(rr, mod)) % mod;
+ c -= cc;
+ }
+ return !(res % mod);
+}
+
+bool hasSameDigits(char *s) { return test(2, s) && test(5, s); }
+
+int main() {
+ char *s1 = "3902", *s2 = "34789";
+ printf("%d\n", hasSameDigits(s1)); // expect: 1
+ printf("%d\n", hasSameDigits(s2)); // expect: 0
+}
diff --git a/check_digit_eq_str_op2.py b/check_digit_eq_str_op2.py
new file mode 100644
index 0000000..cfa1f53
--- /dev/null
+++ b/check_digit_eq_str_op2.py
@@ -0,0 +1,45 @@
+# 3463. Check If Digits Are Equal in String After Operations II
+"""
+you are given a string 's' consisting of digits. perform the following
+operation repeatedly until the string has exactly two digits: for each pair
+of consecutive digits in 's', starting from the first digit, calculate a new
+digit as the sum of the two digits modulo 10. replace 's' with the sequence
+of newly calculated digits, maintaining the order in which they are computed.
+return 'true' if the final two digits in 's' are the same; otherwise return
+false.
+"""
+
+
+class Solution(object):
+ def hasSameDigits(self, s):
+ """
+ :type s: str
+ :rtype: bool
+ """
+
+ def fac(a, mod):
+ cnt = 0
+ while a > 0 and a % mod == 0:
+ cnt += 1
+ a //= mod
+ return a % mod, cnt
+
+ def test(mod):
+ n, res, r, c = len(s), 0, 1, 0
+ for i in range(n - 1):
+ if c == 0:
+ res += r * (int(s[i]) - int(s[i + 1]))
+ rr, cc = fac(n - 2 - i, mod)
+ r = r * rr % mod
+ c += cc
+ rr, cc = fac(i + 1, mod)
+ r = r * pow(rr, mod - 2, mod) % mod
+ return res % mod == 0
+
+ return test(2) and test(5)
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.hasSameDigits(s="3902"))
+ print(obj.hasSameDigits(s="34789"))
diff --git a/count_and_say.c b/count_and_say.c
index 8d186fc..95726cd 100644
--- a/count_and_say.c
+++ b/count_and_say.c
@@ -1,7 +1,5 @@
// 38. Count and Say
-#include <stdio.h>
-#include <stdlib.h>
-#include <string.h>
+#include "leetcode.h"
/*
* the count-and-say sequence is a sequence of digit strings defined by the
@@ -16,53 +14,33 @@
* term of the count and say sequence.
*/
-char *int_to_char(int n) {
- char *res = malloc(11);
- res[10] = '\0';
- int idx = 9;
- while (n) {
- res[idx] = '0' + n % 10;
- n /= 10;
- idx--;
- }
- return &res[idx + 1];
-}
-
char *countAndSay(int n) {
- char *curr = malloc(5000), *post = malloc(5000);
- curr[0] = '1';
- curr[1] = '\0';
if (n == 1)
- return curr;
- for (int i = 2; i <= n; i++) {
- int curr_len = strlen(curr), idx = 0, cnt = 1, pos = 0;
- char *tmp;
- for (int j = 1; j < curr_len; j++) {
- if (curr[j] == curr[j - 1])
- cnt++;
- else {
- tmp = int_to_char(cnt);
- strncpy(&post[pos], tmp, strlen(tmp));
- pos += strlen(tmp);
- post[pos] = curr[j - 1];
- pos++;
- cnt = 1;
- }
+ return "1";
+ char *s = countAndSay(n - 1), curr = *s;
+ char *ans = (char *)malloc(4463 * sizeof(char));
+ int m = strlen(s), idx = 0, cnt = 1;
+ for (int i = 1; i < m; i++) {
+ char c = *(s + i);
+ if (c == curr)
+ cnt++;
+ else {
+ *(ans + idx++) = ('0' + cnt);
+ *(ans + idx++) = curr;
+ curr = c;
+ cnt = 1;
}
- tmp = int_to_char(cnt);
- strncpy(&post[pos], tmp, strlen(tmp));
- pos += strlen(tmp);
- post[pos] = curr[curr_len - 1];
- pos++;
- post[pos] = '\0';
- tmp = curr;
- curr = post;
- post = tmp;
}
- return curr;
+ *(ans + idx++) = ('0' + cnt);
+ *(ans + idx++) = curr;
+ *(ans + idx) = '\0';
+ return ans;
}
int main() {
- printf("%s\n", countAndSay(1)); // expect: 1
- printf("%s\n", countAndSay(4)); // expect: 1211
+ char *cas1 = countAndSay(4), *cas2 = countAndSay(1);
+ printf("%s\n", cas1); // expect: 1211
+ printf("%s\n", cas2); // expect: 1
+ free(cas1);
+ free(cas2);
}
diff --git a/count_and_say.py b/count_and_say.py
new file mode 100644
index 0000000..e8521b3
--- /dev/null
+++ b/count_and_say.py
@@ -0,0 +1,35 @@
+# 38. Count and Say
+from re import findall
+
+"""
+the count-and-say sequence is a sequence of digit strings defined by the
+recursive formula:
+- countAndSay(1) = "1"
+- countAndSay(n) is the way you would "say" the digit string from
+'countAndSay(n - 1)', which is then converted into a different digit string
+to determine how you "say" a digit string, split it into minimal number of
+substrings such that each substring contains exactly one unique digit. then
+for each substring, say the number of digits, then say the digit, finally,
+concatenate every said digit. given a positive integer 'n', return the n'th
+term of the count and say sequence.
+"""
+
+
+class Solution(object):
+ def countAndSay(self, n):
+ """
+ :type n: int
+ :rtype: str
+ """
+ ans = "1"
+ for _ in range(n - 1):
+ ans = "".join(
+ str(len(group)) + digit for group, digit in findall(r"((.)\2*)", ans)
+ )
+ return ans
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.countAndSay(n=4))
+ print(obj.countAndSay(n=1))
diff --git a/count_complete_subarr_arr.c b/count_complete_subarr_arr.c
new file mode 100644
index 0000000..bd16ad4
--- /dev/null
+++ b/count_complete_subarr_arr.c
@@ -0,0 +1,50 @@
+// 2799. Count Complete Subarrays in an Array
+#include "leetcode.h"
+
+/*
+ * you are given an array 'nums' consisting of positive integers. we call a
+ * subarray of an array complete if the following condition is satisfied. the
+ * number of distinct elements in the subarray is equal to the number of
+ * distinct elements in the whole array. return the number of complete
+ * subarrays. a subarray is a contiguous non-empty part of an array.
+ */
+
+int countCompleteSubarrays(int *nums, int numsSize) {
+ int elem[2001] = {0}, distinct = 0, ans = 0;
+ for (int i = 0; i < numsSize; i++) {
+ if (!elem[nums[i]])
+ distinct++;
+ elem[nums[i]]++;
+ }
+ int low = 0, high = 0, curr = 0;
+ memset(elem, 0, sizeof(elem));
+ while (curr < distinct) {
+ if (!elem[nums[high]])
+ curr++;
+ elem[nums[high]]++;
+ high++;
+ }
+ ans += numsSize - high + 1;
+ while (low < numsSize) {
+ elem[nums[low]]--;
+ if (!elem[nums[low]])
+ curr--;
+ while (high < numsSize && curr < distinct) {
+ if (!elem[nums[high]])
+ curr++;
+ elem[nums[high]]++;
+ high++;
+ }
+ if (curr < distinct)
+ break;
+ ans += numsSize - high + 1;
+ low++;
+ }
+ return ans;
+}
+
+int main() {
+ int n1[] = {1, 3, 1, 2, 2}, n2[] = {5, 5, 5, 5};
+ printf("%d\n", countCompleteSubarrays(n1, ARRAY_SIZE(n1))); // expect: 4
+ printf("%d\n", countCompleteSubarrays(n2, ARRAY_SIZE(n2))); // expect: 10
+}
diff --git a/count_complete_subarr_arr.py b/count_complete_subarr_arr.py
new file mode 100644
index 0000000..ca0371d
--- /dev/null
+++ b/count_complete_subarr_arr.py
@@ -0,0 +1,35 @@
+# 2799. Count Complete Subarrays in an Array
+from collections import Counter
+
+"""
+you are given an array 'nums' consisting of positive integers. we call a
+subarray of an array complete if the following condition is satisfied. the
+number of distinct elements in the subarray is equal to the number of
+distinct elements in the whole array. return the number of complete
+subarrays. a subarray is a contiguous non-empty part of an array.
+"""
+
+
+class Solution(object):
+ def countCompleteSubarrays(self, nums):
+ """
+ :type nums: List[int]
+ :rtype: int
+ """
+ n, k, i = len(nums), len(set(nums)), 0
+ ans, cnt = 0, Counter()
+ for j in range(n):
+ cnt[nums[j]] += 1
+ while len(cnt) == k:
+ cnt[nums[i]] -= 1
+ if cnt[nums[i]] == 0:
+ del cnt[nums[i]]
+ i += 1
+ ans += i
+ return ans
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.countCompleteSubarrays(nums=[1, 3, 1, 2, 2]))
+ print(obj.countCompleteSubarrays(nums=[5, 5, 5, 5]))
diff --git a/count_equal_div_pair_arr.c b/count_equal_div_pair_arr.c
new file mode 100644
index 0000000..d6aeb12
--- /dev/null
+++ b/count_equal_div_pair_arr.c
@@ -0,0 +1,23 @@
+// 2176. Count Equal and Divisible Pairs in an Array
+#include "leetcode.h"
+
+/*
+ * given a 0-indexed integer array 'nums' of length 'n' and an integer 'k',
+ * return the number of pairs '(i, j)' where '0 <= i < j < n' such that 'nums[i]
+ * == nums[j]' and '(i * j)' is divisble by 'k'.
+ */
+
+int countPairs(int *nums, int numsSize, int k) {
+ int cnt = 0;
+ for (int i = 0; i < numsSize; i++)
+ for (int j = i + 1; j < numsSize; j++)
+ if (nums[i] == nums[j] && !((i * j) % k))
+ cnt++;
+ return cnt;
+}
+
+int main() {
+ int n1[] = {3, 1, 2, 2, 2, 1, 3}, n2[] = {1, 2, 3, 4};
+ printf("%d\n", countPairs(n1, ARRAY_SIZE(n1), 2)); // expect: 4
+ printf("%d\n", countPairs(n2, ARRAY_SIZE(n2), 1)); // expect: 0
+}
diff --git a/count_equal_div_pair_arr.py b/count_equal_div_pair_arr.py
new file mode 100644
index 0000000..84d4a55
--- /dev/null
+++ b/count_equal_div_pair_arr.py
@@ -0,0 +1,37 @@
+# 2176. Count Equal and Divisible Pairs in an Array
+import collections
+from math import gcd
+
+"""
+given a 0-indexed integer array 'nums' of length 'n' and an integer 'k',
+return the number of pairs '(i, j)' where '0 <= i < j < n' such that 'nums[i]
+== nums[j]' and '(i * j)' is divisble by 'k'.
+"""
+
+
+class Solution(object):
+ def countPairs(self, nums, k):
+ """
+ :type nums: List[int]
+ :type k: int
+ :rtype: int
+ """
+ ids = collections.defaultdict(list)
+ for i, j in enumerate(nums):
+ ids[j].append(i)
+ ans = 0
+ for i in ids.values():
+ gcds = collections.Counter()
+ for j in i:
+ curr_i = gcd(j, k)
+ ans += sum(
+ cnt for curr_j, cnt in gcds.items() if curr_i * curr_j % k == 0
+ )
+ gcds[curr_i] += 1
+ return ans
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.countPairs(nums=[3, 1, 2, 2, 2, 1, 3], k=2))
+ print(obj.countPairs(nums=[1, 2, 3, 4], k=1))
diff --git a/count_good_numbers.c b/count_good_numbers.c
index 86432c4..639c723 100644
--- a/count_good_numbers.c
+++ b/count_good_numbers.c
@@ -12,17 +12,24 @@
* contain leading zeros.
*/
-const int MOD = 1e9 + 7;
+static int mod = 1e9 + 7;
-long long _pow(long long a, long long b) {
- if (!b)
- return 1;
- return b % 2 ? a * _pow(a, b - 1) % MOD : _pow((a * a) % MOD, b / 2);
+long long mod_exp(long long n, long long e) {
+ int res = 1;
+ n %= mod;
+ while (e > 0) {
+ if (e & 1)
+ res = res * n % mod;
+ e >>= 1;
+ n = n * n % mod;
+ }
+ return res;
}
int countGoodNumbers(long long n) {
- long long odd = n / 2, even = n - odd;
- return _pow(20, odd) * ((n % 2) ? 5 : 1) % MOD;
+ long long a = mod_exp(5, (n + 1) / 2);
+ long long b = mod_exp(4, n / 2);
+ return (int)((a * b) % mod);
}
int main() {
diff --git a/count_good_numbers.py b/count_good_numbers.py
index 93455c9..17243a6 100644
--- a/count_good_numbers.py
+++ b/count_good_numbers.py
@@ -13,15 +13,26 @@ contain leading zeros.
class Solution(object):
+ mod = 10**9 + 7
+
+ def mod_exp(self, n, e):
+ res = 1
+ n %= self.mod
+ while e > 0:
+ if e % 2 == 1:
+ res = (res * n) % self.mod
+ n = (n * n) % self.mod
+ e //= 2
+ return res
+
def countGoodNumbers(self, n):
"""
:type n: int
:rtype: int
"""
- cnt, x = 5 ** (n % 2), 20
- for _ in range(n // 2):
- cnt = cnt * x % (10**9 + 7)
- return cnt
+ a = self.mod_exp(5, (n + 1) // 2)
+ b = self.mod_exp(4, n // 2)
+ return (a * b) % self.mod
if __name__ == "__main__":
diff --git a/count_good_triplet_arr.c b/count_good_triplet_arr.c
new file mode 100644
index 0000000..fd32e94
--- /dev/null
+++ b/count_good_triplet_arr.c
@@ -0,0 +1,64 @@
+// 2179. Count Good Triplets in an Array
+#include "leetcode.h"
+
+/*
+ * you are given two 0-indexed arrays 'nums1' and 'nums2' of length 'n', both of
+ * which are permutations of '[0, 1, ..., n - 1]'. a good triplet is a set of
+ * three distinct values which are present in increasing order by position in
+ * both 'nums1' and 'nums2'. in other words, if we consider 'pos1v' as the index
+ * of the value 'v' in 'nums1' and 'pos2v' as the index of the value 'v' in
+ * 'nums2', then a good triplet will be a set '(x, y, z)'. return the total
+ * number of good triplets.
+ */
+
+#define MAX_SIZE 100010
+
+static int tree[MAX_SIZE];
+
+void tree_push(int idx, int val, int n) {
+ idx++;
+ while (idx <= n + 2) {
+ tree[idx] += val;
+ idx += idx & (-idx);
+ }
+}
+
+int tree_query(int idx) {
+ idx++;
+ int res = 0;
+ while (idx > 0) {
+ res += tree[idx];
+ idx -= idx & (-idx);
+ }
+ return res;
+}
+
+long long goodTriplets(int *nums1, int nums1Size, int *nums2, int nums2Size) {
+ int n = nums1Size, p2v[MAX_SIZE], arr[MAX_SIZE], left[MAX_SIZE] = {0};
+ for (int i = 0; i < n; i++)
+ p2v[nums2[i]] = i;
+ for (int i = 0; i < n; i++)
+ arr[i] = p2v[nums1[i]];
+ memset(tree, 0, sizeof(tree));
+ for (int i = 0; i < n; i++) {
+ left[i] = tree_query(arr[i] - 1);
+ tree_push(arr[i], 1, n);
+ }
+ memset(tree, 0, sizeof(tree));
+ long long ans = 0;
+ for (int i = n - 1; i >= 0; i--) {
+ int right = tree_query(n - 1) - tree_query(arr[i]);
+ ans += (long long)left[i] * right;
+ tree_push(arr[i], 1, n);
+ }
+ return ans;
+}
+
+int main() {
+ int n11[] = {2, 0, 1, 3}, n21[] = {0, 1, 2, 3};
+ int n12[] = {4, 0, 1, 3, 2}, n22[] = {4, 1, 0, 2, 3};
+ printf("%lld\n",
+ goodTriplets(n11, ARRAY_SIZE(n11), n21, ARRAY_SIZE(n21))); // expect: 1
+ printf("%lld\n",
+ goodTriplets(n12, ARRAY_SIZE(n12), n22, ARRAY_SIZE(n22))); // expect: 4
+}
diff --git a/count_good_triplet_arr.py b/count_good_triplet_arr.py
new file mode 100644
index 0000000..ec42ec0
--- /dev/null
+++ b/count_good_triplet_arr.py
@@ -0,0 +1,38 @@
+# 2179. Count Good Triplets in an Array
+import bisect
+
+"""
+you are given two 0-indexed arrays 'nums1' and 'nums2' of length 'n', both of
+which are permutations of '[0, 1, ..., n - 1]'. a good triplet is a set of
+three distinct values which are present in increasing order by position in
+both 'nums1' and 'nums2'. in other words, if we consider 'pos1v' as the index
+of the value 'v' in 'nums1' and 'pos2v' as the index of the value 'v' in
+'nums2', then a good triplet will be a set '(x, y, z)'. return the total
+number of good triplets.
+"""
+
+
+class Solution(object):
+ def goodTriplets(self, nums1, nums2):
+ """
+ :type nums1: List[int]
+ :type nums2: List[int]
+ :rtype: int
+ """
+ arr, n = {}, len(nums1)
+ for i, j in enumerate(nums1):
+ arr[j] = i
+ ans, stk = 0, []
+ for i in nums2:
+ idx = arr[i]
+ left = bisect.bisect_left(stk, idx)
+ right = (n - 1 - idx) - (len(stk) - left)
+ ans += left * right
+ bisect.insort(stk, idx)
+ return ans
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.goodTriplets(nums1=[2, 0, 1, 3], nums2=[0, 1, 2, 3]))
+ print(obj.goodTriplets(nums1=[4, 0, 1, 3, 2], nums2=[4, 1, 0, 2, 3]))
diff --git a/count_good_triplets.c b/count_good_triplets.c
new file mode 100644
index 0000000..9275841
--- /dev/null
+++ b/count_good_triplets.c
@@ -0,0 +1,29 @@
+// 1534. Count Good Triplets
+#include "leetcode.h"
+
+/*
+ * given an array of integers 'arr', and three integers 'a, b, c', yo need to
+ * find the number of good triplets. a triplet '(arr[i], arr[j], arr[k])' is
+ * good if the following conditions are met: '0 <= i < j < k < arr.len, |arr[i]
+ * - arr[j]| <= (a, b, c)' where '|x|' denotes the absolute value of 'x'. return
+ * the number of good triplets.
+ */
+
+int countGoodTriplets(int *arr, int arrSize, int a, int b, int c) {
+ int cnt = 0;
+ for (int i = 0; i < arrSize - 2; i++)
+ for (int k = i + 2; k < arrSize; k++) {
+ if (abs(arr[k] - arr[i]) > c)
+ continue;
+ for (int j = i + 1; j < k; j++)
+ if (abs(arr[i] - arr[j]) <= a && abs(arr[j] - arr[k]) <= b)
+ ++cnt;
+ }
+ return cnt;
+}
+
+int main() {
+ int a1[] = {3, 0, 1, 1, 9, 7}, a2[] = {1, 1, 2, 2, 3};
+ printf("%d\n", countGoodTriplets(a1, ARRAY_SIZE(a1), 7, 2, 3)); // expect: 4
+ printf("%d\n", countGoodTriplets(a2, ARRAY_SIZE(a2), 0, 0, 1)); // expect: 0
+}
diff --git a/count_good_triplets.py b/count_good_triplets.py
new file mode 100644
index 0000000..c3007cf
--- /dev/null
+++ b/count_good_triplets.py
@@ -0,0 +1,36 @@
+# 1534. Count Good Triplets
+
+"""
+given an array of integers 'arr', and three integers 'a, b, c', yo need to
+find the number of good triplets. a triplet '(arr[i], arr[j], arr[k])' is
+good if the following conditions are met: '0 <= i < j < k < arr.len, |arr[i]
+- arr[j]| <= (a, b, c)' where '|x|' denotes the absolute value of 'x'. return
+the number of good triplets.
+"""
+
+
+class Solution(object):
+ def countGoodTriplets(self, arr, a, b, c):
+ """
+ :type arr: List[int]
+ :type a: int
+ :type b: int
+ :type c: int
+ :rtype: int
+ """
+ cnt = 0
+ n = len(arr)
+ for i in range(n - 2):
+ for k in range(i + 2, n):
+ if abs(arr[k] - arr[i]) > c:
+ continue
+ for j in range(i + 1, k):
+ if abs(arr[i] - arr[j]) <= a and abs(arr[j] - arr[k]) <= b:
+ cnt += 1
+ return cnt
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.countGoodTriplets(arr=[3, 0, 1, 1, 9, 7], a=7, b=2, c=3))
+ print(obj.countGoodTriplets(arr=[1, 1, 2, 2, 3], a=0, b=0, c=1))
diff --git a/count_hidden_sequences.c b/count_hidden_sequences.c
new file mode 100644
index 0000000..0d8c2e1
--- /dev/null
+++ b/count_hidden_sequences.c
@@ -0,0 +1,29 @@
+// 2145. Count the Hidden Sequences
+#include "leetcode.h"
+
+/*
+ * you are given a 0-indexed array of 'n' integers 'differences', which
+ * describes the differences between each pair of consecutive integers of a
+ * hidden sequence of length '(n + 1)'. you are further given two integers
+ * 'lower' and 'upper' that describe the inclusive range of values '[lower,
+ * upper]' that the hidden sequence can contain. return the number of possible
+ * hidden sequences there are. if there are no possible sequences, return 0.
+ */
+
+int numberOfArrays(int *differences, int differencesSize, int lower,
+ int upper) {
+ long long cnt = 0, a = 0, b = 0;
+ for (int i = 0; i < differencesSize; i++) {
+ cnt += differences[i];
+ a = fmax(a, cnt);
+ b = fmin(b, cnt);
+ }
+ return fmax(0L, (upper - lower) - (a - b) + 1);
+}
+
+int main() {
+ int d1[] = {1, -3, 4}, d2[] = {3, -4, 5, 1, -2}, d3[] = {4, -7, 2};
+ printf("%d\n", numberOfArrays(d1, ARRAY_SIZE(d1), 1, 6)); // expect: 2
+ printf("%d\n", numberOfArrays(d2, ARRAY_SIZE(d2), -4, 5)); // expect: 4
+ printf("%d\n", numberOfArrays(d3, ARRAY_SIZE(d3), 3, 6)); // expect: 0
+}
diff --git a/count_hidden_sequences.py b/count_hidden_sequences.py
new file mode 100644
index 0000000..c229f7a
--- /dev/null
+++ b/count_hidden_sequences.py
@@ -0,0 +1,30 @@
+# 2145. Count the Hidden Sequences
+from itertools import accumulate
+
+"""
+you are given a 0-indexed array of 'n' integers 'differences', which
+describes the differences between each pair of consecutive integers of a
+hidden sequence of length '(n + 1)'. you are further given two integers
+'lower' and 'upper' that describe the inclusive range of values '[lower,
+upper]' that the hidden sequence can contain. return the number of possible
+hidden sequences there are. if there are no possible sequences, return 0.
+"""
+
+
+class Solution(object):
+ def numberOfcntrrays(self, differences, lower, upper):
+ """
+ :type differences: List[int]
+ :type lower: int
+ :type upper: int
+ :rtype: int
+ """
+ cnt = list(accumulate(differences, initial=0))
+ return max(0, (upper - lower) - (max(cnt) - min(cnt)) + 1)
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.numberOfcntrrays(differences=[1, -3, 4], lower=1, upper=6))
+ print(obj.numberOfcntrrays(differences=[3, -4, 5, 1, -2], lower=-4, upper=5))
+ print(obj.numberOfcntrrays(differences=[4, -7, 2], lower=3, upper=6))
diff --git a/count_interesting_subarr.c b/count_interesting_subarr.c
new file mode 100644
index 0000000..0a379d5
--- /dev/null
+++ b/count_interesting_subarr.c
@@ -0,0 +1,83 @@
+// 2845. Count of Interesting Subarrays
+#include "leetcode.h"
+
+/*
+ * you are given a 0-indexed integer array 'nums', an integer 'modulo', and an
+ * integer 'k'. your task is to find the count of the subarrays that are
+ * interesting. a subarray 'nums[l..r]' is interesting if the following
+ * condition holds: let 'cnt' be the number of indices 'i' in the range '[l, r]'
+ * such that 'nums[i] % modulo == k'. then 'cnt % modulo == k'. return an
+ * integer denoting the count of interesting subarrays.
+ */
+
+struct pair {
+ int key;
+ int val;
+};
+
+struct hash {
+ struct pair *pairs;
+ int size;
+ int max;
+};
+
+struct hash *hash_init(int size) {
+ struct hash *new = (struct hash *)malloc(sizeof(struct hash));
+ new->pairs = (struct pair *)malloc(size * sizeof(struct pair));
+ new->size = 0;
+ new->max = size;
+ return new;
+}
+
+int get(struct hash *obj, int key) {
+ for (int i = 0; i < obj->size; i++)
+ if (obj->pairs[i].key == key)
+ return obj->pairs[i].val;
+ return 0;
+}
+
+void put(struct hash *obj, int key, int val) {
+ for (int i = 0; i < obj->size; i++)
+ if (obj->pairs[i].key == key) {
+ obj->pairs[i].val = val;
+ return;
+ }
+ if (obj->size == obj->max) {
+ obj->max *= 2;
+ obj->pairs =
+ (struct pair *)realloc(obj->pairs, obj->max * sizeof(struct pair));
+ }
+ obj->pairs[obj->size].key = key;
+ obj->pairs[obj->size].val = val;
+ obj->size++;
+}
+
+void hash_free(struct hash *obj) {
+ free(obj->pairs);
+ free(obj);
+}
+
+long long countInterestingSubarrays(int *nums, int numsSize, int modulo,
+ int k) {
+ int cnt = 0;
+ struct hash *map = hash_init(numsSize);
+ put(map, 0, 1);
+ long long ans = 0;
+ for (int i = 0; i < numsSize; i++) {
+ cnt += (nums[i] % modulo == k);
+ int k1 = cnt % modulo;
+ int k2 = (k1 - k + modulo) % modulo;
+ ans += get(map, k2);
+ put(map, k1, get(map, k1) + 1);
+ }
+ hash_free(map);
+ return ans;
+}
+
+int main() {
+ int n1[] = {3, 2, 4}, n2[] = {3, 1, 9, 6};
+ printf("%lld\n",
+ countInterestingSubarrays(n1, ARRAY_SIZE(n1), 2, 1)); // expect: 3
+ printf("%lld\n",
+ countInterestingSubarrays(n2, ARRAY_SIZE(n2), 3, 0)); // expect: 2
+}
diff --git a/count_interesting_subarr.py b/count_interesting_subarr.py
new file mode 100644
index 0000000..9e76d99
--- /dev/null
+++ b/count_interesting_subarr.py
@@ -0,0 +1,34 @@
+# 2845. Count of Interesting Subarrays
+from collections import Counter
+
+"""
+you are given a 0-indexed integer array 'nums', an integer 'modulo', and an
+integer 'k'. your task is to find the count of the subarrays that are
+interesting. a subarray 'nums[l..r]' is interesting if the following
+condition holds: let 'cnt' be the number of indices 'i' in the range '[l, r]'
+such that 'nums[i] % modulo == k'. then 'cnt % modulo == k'. return an
+integer denoting the count of interesting subarrays.
+"""
+
+
+class Solution(object):
+ def countInterestingSubarrays(self, nums, modulo, k):
+ """
+ :type nums: List[int]
+ :type modulo: int
+ :type k: int
+ :rtype: int
+ """
+ ans, cnt = 0, 0
+ m = Counter({0: 1})
+ for i in nums:
+ cnt = (cnt + (1 if i % modulo == k else 0)) % modulo
+ ans += m[(cnt - k) % modulo]
+ m[cnt] += 1
+ return ans
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.countInterestingSubarrays(nums=[3, 2, 4], modulo=2, k=1))
+ print(obj.countInterestingSubarrays(nums=[3, 1, 9, 6], modulo=3, k=0))
diff --git a/count_largest_group.c b/count_largest_group.c
new file mode 100644
index 0000000..4d9063b
--- /dev/null
+++ b/count_largest_group.c
@@ -0,0 +1,37 @@
+// 1399. Count Largest Group
+#include "leetcode.h"
+
+/*
+ * you are given an integer 'n'. each number from 1 to 'n' is grouped according
+ * to the sum of its digits. return the number of groups that have the largest
+ * size.
+ */
+
+int get_num(int n) {
+ int res = 0;
+ while (n) {
+ res += n % 10;
+ n /= 10;
+ }
+ return res;
+}
+
+int countLargestGroup(int n) {
+ int arr[37] = {0}, max = 0;
+ for (int i = 1; i <= n; i++) {
+ int curr = get_num(i);
+ arr[curr]++;
+ if (arr[curr] > max)
+ max = arr[curr];
+ }
+ int cnt = 0;
+ for (int i = 1; i <= 36; i++)
+ if (arr[i] == max)
+ cnt++;
+ return cnt;
+}
+
+int main() {
+ printf("%d\n", countLargestGroup(13)); // expect: 4
+ printf("%d\n", countLargestGroup(2)); // expect: 2
+}
diff --git a/count_largest_group.py b/count_largest_group.py
new file mode 100644
index 0000000..3158100
--- /dev/null
+++ b/count_largest_group.py
@@ -0,0 +1,39 @@
+# 1399. Count Largest Group
+
+"""
+you are given an integer 'n'. each number from 1 to 'n' is grouped according
+to the sum of its digits. return the number of groups that have the largest
+size.
+"""
+
+
+class Solution(object):
+ def get_num(self, n):
+ res = 0
+ while n != 0:
+ res += n % 10
+ n //= 10
+ return res
+
+ def countLargestGroup(self, n):
+ """
+ :type n: int
+ :rtype: int
+ """
+ arr, m = [0] * 37, 0
+ for i in range(1, n + 1):
+ curr = self.get_num(i)
+ arr[curr] += 1
+ if arr[curr] > m:
+ m = arr[curr]
+ cnt = 0
+ for i in range(37):
+ if arr[i] == m:
+ cnt += 1
+ return cnt
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.countLargestGroup(n=13))
+ print(obj.countLargestGroup(n=2))
diff --git a/count_num_fair_pairs.c b/count_num_fair_pairs.c
index 80d26f1..9ddfc9a 100644
--- a/count_num_fair_pairs.c
+++ b/count_num_fair_pairs.c
@@ -7,46 +7,25 @@
* i < j < n' and 'lower <= nums[i] + nums[j] <= upper'
*/
-int cmp(const void *a, const void *b) { return *(int *)a - *(int *)b; }
-
-int bs_lower(int *nums, int n, int left, int right, int lower) {
- int l = left, r = right;
- if (nums[r] < lower)
- return -1;
- while (l < r) {
- int m = l + (r - l) / 2;
- if (nums[m] < lower)
- l = m + 1;
- else
- r = m;
- }
- return l;
-}
-
-int bs_upper(int *nums, int n, int left, int right, int upper) {
- int l = left, r = right;
- if (nums[l] > upper)
- return -1;
- while (l < r) {
- int m = r - (r - l) / 2;
- if (nums[m] > upper)
- r = m - 1;
- else
- l = m;
- }
- return l;
+int cmp(const void *a, const void *b) {
+ return (*(int *)a > *(int *)b) - (*(int *)b > *(int *)a);
}
long long countFairPairs(int *nums, int numsSize, int lower, int upper) {
- int n = numsSize;
+ qsort(nums, numsSize, sizeof(int), cmp);
long long ans = 0;
- qsort(nums, n, sizeof(int), cmp);
- for (int i = 0; i < n - 1; i++) {
- int left = bs_lower(nums, n, i + 1, n - 1, lower - nums[i]);
- int right = bs_upper(nums, n, i + 1, n - 1, upper - nums[i]);
- if (left != -1 && right != -1)
- ans += right - left + 1;
- }
+ int i = 0, j = numsSize - 1;
+ while (i < j)
+ if (nums[i] + nums[j] < lower)
+ ans -= j - i++;
+ else
+ j--;
+ i = 0, j = numsSize - 1;
+ while (i < j)
+ if (nums[i] + nums[j] <= upper)
+ ans += j - i++;
+ else
+ j--;
return ans;
}
diff --git a/count_num_fair_pairs.py b/count_num_fair_pairs.py
index 5933dbd..8d02562 100644
--- a/count_num_fair_pairs.py
+++ b/count_num_fair_pairs.py
@@ -19,9 +19,8 @@ class Solution(object):
nums.sort()
ans = 0
for i in range(len(nums) - 1, -1, -1):
- v = nums[i]
- a = bisect.bisect_left(nums, lower - v, lo=0, hi=i)
- b = bisect.bisect_right(nums, upper - v, lo=0, hi=i)
+ a = bisect.bisect_left(nums, lower - nums[i], i + 1)
+ b = bisect.bisect_right(nums, upper - nums[i], i + 1)
ans += b - a
return ans
diff --git a/count_num_good_subarr.c b/count_num_good_subarr.c
new file mode 100644
index 0000000..40c20c4
--- /dev/null
+++ b/count_num_good_subarr.c
@@ -0,0 +1,94 @@
+// 2537. Count the Number of Good Subarrays
+#include "leetcode.h"
+
+/*
+ * given an integer array 'nums' and an integer 'k', return the number of good
+ * subarrays of 'nums'. a subarray 'arr' is good if there are at least 'k' pairs
+ * of indices '(i, j)' such that 'i < j' and 'arr[i] == arr[j]'. a subarray is a
+ * contiguous non-empty sequence of elements within an array.
+ */
+
+struct hash {
+ int *key;
+ int *val;
+ int size;
+};
+
+bool is_prime(int n) {
+ for (int i = 2; i < (int)sqrt(n) + 1; i++)
+ if (!(n % i))
+ return false;
+ return true;
+}
+
+struct hash *hash_init(int size) {
+ int max;
+ if (size < 8)
+ max = 11;
+ else {
+ max = size * 4 / 3;
+ int remove = (max - 3) % 4;
+ max += (remove > 0) * (4 - remove);
+ while (!is_prime(max))
+ max += 4;
+ }
+ struct hash *new = (struct hash *)malloc(sizeof(struct hash));
+ *new = (struct hash){(int *)calloc(max, sizeof(int)),
+ (int *)calloc(max, sizeof(int)), max};
+ return new;
+}
+
+void hash_free(struct hash *obj) {
+ free(obj->key);
+ free(obj->val);
+ free(obj);
+}
+
+int hash_getidx(struct hash *obj, int key) {
+ int idx = key % obj->size;
+ while (obj->key[idx] > 0 && obj->key[idx] != key)
+ if (++idx == obj->size)
+ idx = 0;
+ obj->key[idx] = key;
+ return idx;
+}
+
+int hash_getkey(struct hash *obj, int key) {
+ int idx = key % obj->size;
+ while (obj->key[idx] > 0) {
+ if (obj->key[idx] == key)
+ return idx;
+ if (++idx == obj->size)
+ idx = 0;
+ }
+ return -1;
+}
+
+int hash_addkey(struct hash *obj, int key) { return hash_getidx(obj, key); }
+
+long long countGood(int *nums, int numsSize, int k) {
+ long long ans = 0;
+ int curr = 0;
+ struct hash *map = hash_init(numsSize);
+ for (int l = 0, r = 0; r < numsSize; r++) {
+ int i = hash_getkey(map, nums[r]);
+ if (i == -1) {
+ i = hash_addkey(map, nums[r]);
+ map->val[i] = 1;
+ } else
+ curr += map->val[i]++;
+ while (curr >= k) {
+ ans += numsSize - r;
+ curr -= --map->val[hash_getidx(map, nums[l])];
+ l++;
+ }
+ }
+ hash_free(map);
+ return ans;
+}
+
+int main() {
+ int n1[] = {1, 1, 1, 1, 1}, n2[] = {3, 1, 4, 3, 2, 2, 4};
+ printf("%lld\n", countGood(n1, ARRAY_SIZE(n1), 10)); // expect: 1
+ printf("%lld\n", countGood(n2, ARRAY_SIZE(n2), 2)); // expect: 4
+}
diff --git a/count_num_good_subarr.py b/count_num_good_subarr.py
new file mode 100644
index 0000000..69eedce
--- /dev/null
+++ b/count_num_good_subarr.py
@@ -0,0 +1,35 @@
+# 2537. Count the Number of Good Subarrays
+from collections import Counter
+
+"""
+given an integer array 'nums' and an integer 'k', return the number of good
+subarrays of 'nums'. a subarray 'arr' is good if there are at least 'k' pairs
+of indices '(i, j)' such that 'i < j' and 'arr[i] == arr[j]'. a subarray is a
+contiguous non-empty sequence of elements within an array.
+"""
+
+
+class Solution(object):
+ def countGood(self, nums, k):
+ """
+ :type nums: List[int]
+ :type k: int
+ :rtype: int
+ """
+ ans, i = 0, 0
+ cnt = Counter()
+ for j in range(len(nums)):
+ k -= cnt[nums[j]]
+ cnt[nums[j]] += 1
+ while k <= 0:
+ cnt[nums[i]] -= 1
+ k += cnt[nums[i]]
+ i += 1
+ ans += i
+ return ans
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.countGood(nums=[1, 1, 1, 1, 1], k=10))
+ print(obj.countGood(nums=[3, 1, 4, 3, 2, 2, 4], k=2))
diff --git a/count_num_ideal_arr.c b/count_num_ideal_arr.c
new file mode 100644
index 0000000..298b1da
--- /dev/null
+++ b/count_num_ideal_arr.c
@@ -0,0 +1,36 @@
+// 2338. Count the Number of Ideal Arrays
+#include "leetcode.h"
+
+/*
+ * you are given two integers 'n' and 'maxValue' which are used to describe an
+ * ideal array. a 0-indexed integer array 'arr' of length 'n' is considered
+ * ideal if the following conditions hold true: every 'arr[i]' is a value from 1
+ * to 'maxValue' for '0 <= i < n', and every 'arr[i]' is divisble by 'arr[i -
+ * 1]'. return the number of distinct ideal arrays of length 'n'. since the
+ * answer may be very large, return it modulo 10^9+7.
+ */
+
+int idealArrays(int n, int maxValue) {
+ int cmb[10001][14] = {1}, cnt[10001][14] = {}, mod = 1e9 + 7;
+ if (!cmb[1][1]) {
+ for (int i = 1; i <= 10000; ++i)
+ for (int j = 0; j < 14; ++j)
+ cmb[i][j] = !j ? 1 : (cmb[i - 1][j - 1] + cmb[i - 1][j]) % mod;
+ for (int i = 1; i <= 10000; ++i) {
+ ++cnt[i][0];
+ for (int j = 2 * i; j <= 10000; j += i)
+ for (int k = 0; cnt[i][k]; ++k)
+ cnt[j][k + 1] += cnt[i][k];
+ }
+ }
+ int ans = 0;
+ for (int i = 1; i <= maxValue; ++i)
+ for (int j = 0; j < fmin(14, n) && cnt[i][j]; ++j)
+ ans = (1LL * cnt[i][j] * cmb[n - 1][j] + ans) % mod;
+ return ans;
+}
+
+int main() {
+ printf("%d\n", idealArrays(2, 5)); // expect: 10
+ printf("%d\n", idealArrays(5, 3)); // expect: 11
+}
diff --git a/count_num_ideal_arr.py b/count_num_ideal_arr.py
new file mode 100644
index 0000000..6966711
--- /dev/null
+++ b/count_num_ideal_arr.py
@@ -0,0 +1,38 @@
+# 2338. Count the Number of Ideal Arrays
+from collections import Counter
+from math import comb
+
+"""
+you are given two integers 'n' and 'maxValue' which are used to describe an
+ideal array. a 0-indexed integer array 'arr' of length 'n' is considered
+ideal if the following conditions hold true: every 'arr[i]' is a value from 1
+to 'maxValue' for '0 <= i < n', and every 'arr[i]' is divisble by 'arr[i -
+1]'. return the number of distinct ideal arrays of length 'n'. since the
+answer may be very large, return it modulo 10^9+7.
+"""
+
+
+class Solution(object):
+ def idealArrays(self, n, maxValue):
+ """
+ :type n: int
+ :type maxValue: int
+ :rtype: int
+ """
+ ans = maxValue
+ freq = {i: 1 for i in range(1, maxValue + 1)}
+ for i in range(1, n):
+ tmp = Counter()
+ for j in freq:
+ for k in range(2, maxValue // j + 1):
+ ans += comb(n - 1, i) * freq[j]
+ tmp[k * j] += freq[j]
+ freq = tmp
+ ans %= 10**9 + 7
+ return ans
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.idealArrays(n=2, maxValue=5))
+ print(obj.idealArrays(n=5, maxValue=3))
diff --git a/count_number_powerful_integers.cpp b/count_number_powerful_integers.cpp
new file mode 100644
index 0000000..2d5981d
--- /dev/null
+++ b/count_number_powerful_integers.cpp
@@ -0,0 +1,41 @@
+// 2999. Count the Number of Powerful Integers
+#include "leetcode.h"
+
+/*
+ * you are given three integers 'start', 'finish', and 'limit'. you are also
+ * given a 0-indexed string 's' representing a positive integer. a positive
+ * integer 'x' is called powerful if it ends with 's' and each digit in 'x' is
+ * at most 'limit'. return the total number of powerful integers in the range
+ * '[start .. finish]'. a string 'x' is a suffix of a string 'y' if and only if
+ * 'x' is a substring of 'y' that starts from some index in 'y' and extends to
+ * the index 'y.length - 1'.
+ */
+
+class Solution {
+private:
+ long long cnt[16];
+ long long get_cnt(char l, const string &n, const string &s) {
+ long long res = cnt[n.size() - 1], i = 0, size = n.size() - s.size();
+ do
+ res += i == size ? n.substr(i) >= s
+ : cnt[n.size() - i - 1] * (min(l, n[i]) - '1' + (i > 0));
+ while (i < size && n[i++] < l);
+ return res;
+ }
+
+public:
+ long long numberOfPowerfulInt(long long start, long long finish, int limit,
+ string s) {
+ for (int i = s.size(); i < 16; ++i)
+ cnt[i] = i == s.size() ? 1 : cnt[i - 1] * (limit + 1);
+ return get_cnt(limit + '1', to_string(finish), s) -
+ get_cnt(limit + '1', to_string(start - 1), s);
+ }
+};
+
+int main() {
+ Solution obj;
+ printf("%lld\n", obj.numberOfPowerfulInt(1, 6000, 4, "124")); // expect: 5
+ printf("%lld\n", obj.numberOfPowerfulInt(15, 215, 6, "")); // expect: 2
+ printf("%lld\n", obj.numberOfPowerfulInt(1000, 2000, 4, "3000")); // expect: 0
+}
diff --git a/count_number_powerful_integers.py b/count_number_powerful_integers.py
new file mode 100644
index 0000000..da77940
--- /dev/null
+++ b/count_number_powerful_integers.py
@@ -0,0 +1,47 @@
+# 2999. Count the Number of Powerful Integers
+
+"""
+you are given three integers 'start', 'finish', and 'limit'. you are also
+given a 0-indexed string 's' representing a positive integer. a positive
+integer 'x' is called powerful if it ends with 's' and each digit in 'x' is
+at most 'limit'. return the total number of powerful integers in the range
+'[start .. finish]'. a string 'x' is a suffix of a string 'y' if and only if
+'x' is a substring of 'y' that starts from some index in 'y' and extends to
+the index 'y.length - 1'.
+"""
+
+
+class Solution(object):
+ def numberOfPowerfulInt(self, start, finish, limit, s):
+ """
+ :type start: int
+ :type finish: int
+ :type limit: int
+ :type s: str
+ :rtype: int
+ """
+ cnt = [0] * 16
+
+ def get_cnt(n, s):
+ res, i, size = cnt[len(n) - 1], 0, len(n) - len(s)
+ while True:
+ res += (
+ n[i:] >= s
+ if i == size
+ else cnt[len(n) - i - 1] * (min(limit, int(n[i]) - 1) + (i > 0))
+ )
+ i += 1
+ if i > size or int(n[i - 1]) > limit:
+ break
+ return res
+
+ for i in range(len(s), 16):
+ cnt[i] = 1 if i == len(s) else cnt[i - 1] * (limit + 1)
+ return get_cnt(str(finish), s) - get_cnt(str(start - 1), s)
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.numberOfPowerfulInt(start=1, finish=6000, limit=4, s="124"))
+ print(obj.numberOfPowerfulInt(start=15, finish=215, limit=6, s="10"))
+ print(obj.numberOfPowerfulInt(start=1000, finish=2000, limit=4, s="3000"))
diff --git a/count_symmetric_integers.c b/count_symmetric_integers.c
new file mode 100644
index 0000000..126e711
--- /dev/null
+++ b/count_symmetric_integers.c
@@ -0,0 +1,112 @@
+// 2843. Count Symmetric Integers
+#include "leetcode.h"
+
+/*
+ * you are given two positive integers 'low' and 'high'. an integer 'x'
+ * consisting of '2 * n' digits is symmetric if the sum of the first 'n' digits
+ * of 'x' is equal to the sum of the last 'n' digits of 'x'. numbers with an odd
+ * number of digits are never symmetric. return the number of symmetric integers
+ * in the range '[low, high]'.
+ */
+
+__attribute__((naked)) int countSymmetricIntegers(int low, int high) {
+ /*
+ int cnt = 0;
+ for (int i = 11; i <= 99; i += 11)
+ if (i >= low && i <= high)
+ cnt++;
+ for (int i = 1; i <= 9; ++i)
+ for (int j = 0; j <= 9; ++j) {
+ int sum = i + j;
+ for (int k = 0; k <= 9; ++k) {
+ int l = sum - k;
+ if (0 <= l && l <= 9) {
+ int num = i * 1000 + j * 100 + k * 10 + l;
+ if (num >= low && num <= high)
+ cnt++;
+ }
+ }
+ }
+ return cnt;
+ */
+ __asm__ __volatile__(".intel_syntax noprefix \n\t"
+ "push rbp \n\t"
+ "mov rbp, rsp \n\t"
+ "sub rsp, 32 \n\t"
+ "mov dword ptr [rbp-4], edi \n\t"
+ "mov dword ptr [rbp-8], esi \n\t"
+ "mov dword ptr [rbp-12], 0 \n\t"
+ "mov eax, 11 \n\t"
+ "L_loop2: \n\t"
+ "cmp eax, 99 \n\t"
+ "jg L_fourdigit \n\t"
+ "mov ecx, dword ptr [rbp-4] \n\t"
+ "cmp eax, ecx \n\t"
+ "jl L_skip2 \n\t"
+ "mov ecx, dword ptr [rbp-8] \n\t"
+ "cmp eax, ecx \n\t"
+ "jg L_skip2 \n\t"
+ "add dword ptr [rbp-12], 1 \n\t"
+ "L_skip2: \n\t"
+ "add eax, 11 \n\t"
+ "jmp L_loop2 \n\t"
+ "L_fourdigit: \n\t"
+ "mov r8d, 1 \n\t"
+ "L_a_loop: \n\t"
+ "cmp r8d, 9 \n\t"
+ "jg L_end \n\t"
+ "mov r9d, 0 \n\t"
+ "L_b_loop: \n\t"
+ "cmp r9d, 9 \n\t"
+ "jg L_next_a \n\t"
+ "mov eax, r8d \n\t"
+ "add eax, r9d \n\t"
+ "mov dword ptr [rbp-16], eax \n\t"
+ "mov r10d, 0 \n\t"
+ "L_c_loop: \n\t"
+ "cmp r10d, 9 \n\t"
+ "jg L_next_b \n\t"
+ "mov eax, dword ptr [rbp-16] \n\t"
+ "sub eax, r10d \n\t"
+ "cmp eax, 0 \n\t"
+ "jl L_skip_d \n\t"
+ "cmp eax, 9 \n\t"
+ "jg L_skip_d \n\t"
+ "mov ecx, r8d \n\t"
+ "imul ecx, 1000 \n\t"
+ "mov edx, r9d \n\t"
+ "imul edx, 100 \n\t"
+ "add ecx, edx \n\t"
+ "mov edx, r10d \n\t"
+ "imul edx, 10 \n\t"
+ "add ecx, edx \n\t"
+ "add ecx, eax \n\t"
+ "mov edx, dword ptr [rbp-4] \n\t"
+ "cmp ecx, edx \n\t"
+ "jl L_skip_d \n\t"
+ "mov edx, dword ptr [rbp-8] \n\t"
+ "cmp ecx, edx \n\t"
+ "jg L_skip_d \n\t"
+ "add dword ptr [rbp-12], 1 \n\t"
+ "L_skip_d: \n\t"
+ "inc r10d \n\t"
+ "jmp L_c_loop \n\t"
+ "L_next_b: \n\t"
+ "inc r9d \n\t"
+ "jmp L_b_loop \n\t"
+ "L_next_a: \n\t"
+ "inc r8d \n\t"
+ "jmp L_a_loop \n\t"
+ "L_end: \n\t"
+ "mov eax, dword ptr [rbp-12] \n\t"
+ "leave \n\t"
+ "ret \n\t"
+ ".att_syntax prefix \n"
+ :
+ :);
+}
+
+int main() {
+ printf("%d\n", countSymmetricIntegers(1, 100)); // expect: 9
+ printf("%d\n", countSymmetricIntegers(1200, 1230)); // expect: 4
+}
diff --git a/count_symmetric_integers.py b/count_symmetric_integers.py
new file mode 100644
index 0000000..b7ccbd2
--- /dev/null
+++ b/count_symmetric_integers.py
@@ -0,0 +1,34 @@
+# 2843. Count Symmetric Integers
+
+"""
+you are given two positive integers 'low' and 'high'. an integer 'x'
+consisting of '2 * n' digits is symmetric if the sum of the first 'n' digits
+of 'x' is equal to the sum of the last 'n' digits of 'x'. numbers with an odd
+number of digits are never symmetric. return the number of symmetric integers
+in the range '[low, high]'.
+"""
+
+
+class Solution(object):
+ def countSymmetricIntegers(self, low, high):
+ """
+ :type low: int
+ :type high: int
+ :rtype: int
+ """
+ cnt = 0
+ for i in range(low, high + 1):
+ if i < 100 and i % 11 == 0:
+ cnt += 1
+ elif 1000 <= i < 10000:
+ left = i // 1000 + (i % 1000) // 100
+ right = (i % 100) // 10 + (i % 10)
+ if left == right:
+ cnt += 1
+ return cnt
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.countSymmetricIntegers(low=1, high=100))
+ print(obj.countSymmetricIntegers(low=1200, high=1230))
diff --git a/find_count_good_int.c b/find_count_good_int.c
new file mode 100644
index 0000000..d69105e
--- /dev/null
+++ b/find_count_good_int.c
@@ -0,0 +1,115 @@
+// 3272. Find the Count of Good Integers
+#include "leetcode.h"
+
+/*
+ * you are given two positive integers 'n' and 'k'. an integer 'x' is called
+ * k-palindromic if 'x' is a palindrome and 'x' is divisble by 'k'. an integer
+ * is called good if its digits can be rearranged to form a k-palindromic
+ * integer. for example, for 'k = 2', 2020 can be rearranged to form the
+ * k-palindromic integer 2002, wherase 1010 cannot be rearranged to form a
+ * k-palindromic integer. return the count of good integers containing 'n'
+ * digits.
+ */
+
+#define HASH_SIZE (1 << 17)
+
+static unsigned long long vis[HASH_SIZE];
+static long long fact[11], ans;
+
+static inline uint hash(unsigned long long key) {
+ return (uint)(key % HASH_SIZE);
+}
+
+bool insert(unsigned long long key) {
+ uint idx = hash(key);
+ while (true) {
+ if (!vis[idx]) {
+ vis[idx] = key;
+ return true;
+ } else if (vis[idx] == key)
+ return false;
+ idx = (idx + 1) & (HASH_SIZE - 1);
+ }
+}
+
+void hash_init(void) {
+ fact[0] = 1;
+ for (int i = 1; i <= 10; i++)
+ fact[i] = fact[i - 1] * i;
+}
+
+long long permutation_cnt(int *freq, int n) {
+ long long total = fact[n];
+ for (int i = 0; i < 10; i++)
+ total /= fact[freq[i]];
+ return total;
+}
+
+long long permutation_lead_zero(int *freq, int n) {
+ if (!freq[0])
+ return 0;
+ int copy[10];
+ memcpy(copy, freq, sizeof(int) * 10);
+ copy[0]--;
+ long long total = fact[n - 1];
+ for (int i = 0; i < 10; i++)
+ total /= fact[copy[i]];
+ return total;
+}
+
+long long multiset(int *freq, int n) {
+ long long total = permutation_cnt(freq, n);
+ long long lz = permutation_lead_zero(freq, n);
+ return total - lz;
+}
+
+unsigned long long encode_freq(int *freq) {
+ unsigned long long enc = 0;
+ for (int i = 0; i < 10; i++)
+ enc |= ((unsigned long long)freq[i] & 0xCAFE) << (4 * i);
+ return enc;
+}
+
+long long to_num(int *num, int n) {
+ long long res = 0;
+ for (int i = 0; i < n; i++)
+ res *= 10 + num[i];
+ return res;
+}
+
+void gen_palindrome(int *num, int left, int right, int n, int k) {
+ if (left > right) {
+ long long candidtate = to_num(num, n);
+ if (!(candidtate % k)) {
+ int freq[10] = {0};
+ for (int i = 0; i < n; i++)
+ freq[num[i]]++;
+ unsigned long long code = encode_freq(freq);
+ if (insert(code))
+ ans += multiset(freq, n);
+ }
+ return;
+ }
+ int start = !left ? 1 : 0;
+ for (int i = start; i <= 9; i++) {
+ num[left] = i;
+ num[right] = i;
+ gen_palindrome(num, left + 1, right - 1, n, k);
+ }
+}
+
+long long countGoodIntegers(int n, int k) {
+ ans = 0;
+ memset(vis, 0, sizeof(vis));
+ hash_init();
+ int *num = (int *)malloc(n * sizeof(int));
+ gen_palindrome(num, 0, n - 1, n, k);
+ free(num);
+ return ans;
+}
+
+int main() {
+ printf("%lld\n", countGoodIntegers(3, 5)); // expect: 27
+ printf("%lld\n", countGoodIntegers(1, 4)); // expect: 2
+ printf("%lld\n", countGoodIntegers(5, 6)); // expect: 2468
+}
diff --git a/find_count_good_int.py b/find_count_good_int.py
new file mode 100644
index 0000000..0b7f0bf
--- /dev/null
+++ b/find_count_good_int.py
@@ -0,0 +1,71 @@
+# 3272. Find the Count of Good Integers
+from math import factorial
+from collections import Counter
+
+"""
+you are given two positive integers 'n' and 'k'. an integer 'x' is called
+k-palindromic if 'x' is a palindrome and 'x' is divisble by 'k'. an integer
+is called good if its digits can be rearranged to form a k-palindromic
+integer. for example, for 'k = 2', 2020 can be rearranged to form the
+k-palindromic integer 2002, wherase 1010 cannot be rearranged to form a
+k-palindromic integer. return the count of good integers containing 'n'
+digits.
+"""
+
+
+class Solution(object):
+ def __init__(self):
+ self.ans = 0
+ self.vis = set()
+
+ def to_num(self, digits):
+ return int("".join(map(str, digits)))
+
+ def permutation_cnt(self, freq, total):
+ res = factorial(total)
+ for i in freq.values():
+ res //= factorial(i)
+ return res
+
+ def permutation_leading_zero(self, freq, total):
+ if freq.get(0, 0) == 0:
+ return 0
+ freq[0] -= 1
+ res = factorial(total - 1)
+ for i in freq.values():
+ res //= factorial(i)
+ return res
+
+ def gen_palindrome(self, palin, left, right, divisor, total):
+ if left > right:
+ val = self.to_num(palin)
+ if val % divisor == 0:
+ freq = Counter(palin)
+ key = tuple(sorted(freq.items()))
+ if key not in self.vis:
+ self.ans += self.permutation_cnt(
+ freq, total
+ ) - self.permutation_leading_zero(freq.copy(), total)
+ self.vis.add(key)
+ return
+ for i in range(1 if left == 0 else 0, 10):
+ palin[left] = palin[right] = i
+ self.gen_palindrome(palin, left + 1, right - 1, divisor, total)
+
+ def countGoodIntegers(self, n, k):
+ """
+ :type n: int
+ :type k: int
+ :rtype: int
+ """
+ self.ans = 0
+ self.vis.clear()
+ self.gen_palindrome([0] * n, 0, n - 1, k, n)
+ return self.ans
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.countGoodIntegers(n=3, k=5))
+ print(obj.countGoodIntegers(n=1, k=4))
+ print(obj.countGoodIntegers(n=5, k=6))
diff --git a/max_product_len_palindrome_subseq.c b/max_product_len_palindrome_subseq.c
new file mode 100644
index 0000000..b3e3a66
--- /dev/null
+++ b/max_product_len_palindrome_subseq.c
@@ -0,0 +1,46 @@
+// 2002. Maximum Product of the Length of Two Palindromic Subsequences
+#include "leetcode.h"
+
+/*
+ * given a string 's', find two disjoint palindromic subsequences of 's' such
+ * that the product of their lengths is maximised. the two subsequences are
+ * disjoint if they do not both pick a character at the same index. return the
+ * maximum possible product of the lengths of the two palindromic subsequences.
+ * a subsequence is a string that can be derived from another string by deleting
+ * some or none of its characters without changing the ordering of the remaining
+ * characters. a string is palindromic if it reads the same forward and backward
+ */
+
+int maxProduct(char *s) {
+ int n = strlen(s), *bits = (int *)calloc(1 << n, sizeof(int));
+ for (int i = 1; i < 1 << n; i++)
+ bits[i] = bits[i >> 1] + (i & 1);
+ for (int i = (1 << n) - 1; i >= 0; i--) {
+ int l = 0, r = n - 1;
+ while (l < r) {
+ while (l < n && !(i & (1 << l)))
+ l++;
+ while (r >= 0 && !(i & (1 << r)))
+ r--;
+ if (l < r && s[l] != s[r]) {
+ bits[i] = 0;
+ break;
+ }
+ l++, r--;
+ }
+ }
+ int ans = 1;
+ for (int i = (1 << n) - 1; i > 0; i--)
+ if (bits[i])
+ for (int j = (i + 1) & ~i; j < 1 << n; j = ((j | i) + 1) & ~i)
+ if (bits[j])
+ ans = fmax(ans, bits[i] * bits[j]);
+ return ans;
+}
+
+int main() {
+ char *s1 = "leetcodecom", *s2 = "bb", *s3 = "accbcaxxcxx";
+ printf("%d\n", maxProduct(s1)); // expect: 9
+ printf("%d\n", maxProduct(s2)); // expect: 1
+ printf("%d\n", maxProduct(s3)); // expect: 25
+}
diff --git a/max_product_len_palindrome_subseq.py b/max_product_len_palindrome_subseq.py
new file mode 100644
index 0000000..52ecafc
--- /dev/null
+++ b/max_product_len_palindrome_subseq.py
@@ -0,0 +1,46 @@
+# 2002. Maximum Product of the Length of Two Palindromic Subsequences
+
+"""
+given a string 's', find two disjoint palindromic subsequences of 's' such
+that the product of their lengths is maximised. the two subsequences are
+disjoint if they do not both pick a character at the same index. return the
+maximum possible product of the lengths of the two palindromic subsequences.
+a subsequence is a string that can be derived from another string by deleting
+some or none of its characters without changing the ordering of the remaining
+characters. a string is palindromic if it reads the same forward and backward
+"""
+
+
+class Solution(object):
+ def maxProduct(self, s):
+ """
+ :type s: str
+ :rtype: int
+ """
+ n = len(s)
+ first, last = [0] * (1 << n), [0] * (1 << n)
+ for i in range(n):
+ for j in range(1 << i, 1 << (i + 1)):
+ first[j] = i
+ for i in range(n):
+ for j in range(1 << i, 1 << n, 1 << (i + 1)):
+ last[j] = i
+
+ def dp(m):
+ if m & (m - 1) == 0:
+ return m != 0
+ f, l = first[m], last[m]
+ fb, lb = 1 << f, 1 << l
+ return max(dp(m - lb), dp(m - fb), dp(m - lb - fb) + (s[l] == s[f]) * 2)
+
+ ans = 0
+ for i in range(1, 1 << n):
+ ans = max(ans, dp(i) * dp((1 << n) - 1 - i))
+ return ans
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.maxProduct(s="leetcodecom"))
+ print(obj.maxProduct(s="bb"))
+ print(obj.maxProduct(s="accbcaxxcxx"))
diff --git a/min_num_flip_bin_grid_palin2.c b/min_num_flip_bin_grid_palin2.c
new file mode 100644
index 0000000..fe3ffdf
--- /dev/null
+++ b/min_num_flip_bin_grid_palin2.c
@@ -0,0 +1,50 @@
+// 3240. Minimum Number of Flips to Make Binary Grid Palindromic II
+#include "leetcode.h"
+
+/*
+ * you are given an 'm x n' binary matrix 'grid'. a row or column is considered
+ * palindromic if its values read the same forward as backward. you can flip any
+ * number of cells in 'grid' from 0 to 1 or from 1 to 0. return the minimum
+ * number of cells that need to be flipped to make all rows and columns
+ * palindromic and the total number of 1s in 'grid' divisible by 4.
+ */
+
+int minFlips(int **grid, int gridSize, int *gridColSize) {
+ int ans = 0, one = 0, diff = 0, m = gridSize, n = gridColSize[0];
+ for (int i = 0; i < m / 2; ++i)
+ for (int j = 0; j < n / 2; ++j) {
+ int v = grid[i][j] + grid[i][n - 1 - j] + grid[m - 1 - i][j] +
+ grid[m - 1 - i][n - 1 - j];
+ ans += fmin(v, 4 - v);
+ }
+ if (n % 2)
+ for (int i = 0; i < m / 2; ++i) {
+ diff += grid[i][n / 2] != grid[m - 1 - i][n / 2];
+ one += grid[i][n / 2] + grid[m - 1 - i][n / 2];
+ }
+ if (m % 2)
+ for (int j = 0; j < n / 2; ++j) {
+ diff += grid[m / 2][j] != grid[m / 2][n - 1 - j];
+ one += grid[m / 2][j] + grid[m / 2][n - 1 - j];
+ }
+ if (n % 2 && m % 2)
+ ans += grid[m / 2][n / 2];
+ if (!diff && one % 4)
+ ans += 2;
+ return ans + diff;
+}
+
+int main() {
+ int g1i[3][3] = {{1, 0, 0}, {0, 1, 0}, {0, 0, 1}},
+ g2i[3][2] = {{0, 1}, {0, 1}, {0, 0}}, g3i[2][1] = {{1}, {1}};
+ 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", minFlips(g1.arr, g1.row_size, g1.col_size)); // expect: 3
+ printf("%d\n", minFlips(g2.arr, g2.row_size, g2.col_size)); // expect: 2
+ printf("%d\n", minFlips(g3.arr, g3.row_size, g3.col_size)); // expect: 2
+ two_d_arr_free(&g1);
+ two_d_arr_free(&g2);
+ two_d_arr_free(&g3);
+}
diff --git a/min_num_flip_bin_grid_palin2.py b/min_num_flip_bin_grid_palin2.py
new file mode 100644
index 0000000..3f196bb
--- /dev/null
+++ b/min_num_flip_bin_grid_palin2.py
@@ -0,0 +1,42 @@
+# 3240. Minimum Number of Flips to Make Binary Grid Palindromic II
+
+"""
+you are given an 'm x n' binary matrix 'grid'. a row or column is considered
+palindromic if its values read the same forward as backward. you can flip any
+number of cells in 'grid' from 0 to 1 or from 1 to 0. return the minimum
+number of cells that need to be flipped to make all rows and columns
+palindromic and the total number of 1s in 'grid' divisible by 4.
+"""
+
+
+class Solution(object):
+ def minFlips(self, grid):
+ """
+ :type grid: List[List[int]]
+ :rtype: int
+ """
+ ans, one, diff, m, n = 0, 0, 0, len(grid), len(grid[0])
+ for i in range(m // 2):
+ for j in range(n // 2):
+ v = grid[i][j] + grid[i][~j] + grid[~i][j] + grid[~i][~j]
+ ans += min(v, 4 - v)
+ if n % 2:
+ for i in range(m // 2):
+ diff += grid[i][n // 2] ^ grid[~i][n // 2]
+ one += grid[i][n // 2] + grid[~i][n // 2]
+ if m % 2:
+ for i in range(n // 2):
+ diff += grid[m // 2][j] ^ grid[m // 2][~j]
+ one += grid[m // 2][j] + grid[m // 2][~j]
+ if n % 2 and m % 2:
+ ans += grid[m // 2][n // 2]
+ if diff == 0 and one % 4:
+ ans += 2
+ return ans + diff
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.minFlips(grid=[[1, 0, 0], [0, 1, 0], [0, 0, 1]]))
+ print(obj.minFlips(grid=[[0, 1], [0, 1], [0, 0]]))
+ print(obj.minFlips(grid=[[1], [1]]))
diff --git a/min_num_op_elem_distinct.c b/min_num_op_elem_distinct.c
new file mode 100644
index 0000000..2ea72b5
--- /dev/null
+++ b/min_num_op_elem_distinct.c
@@ -0,0 +1,30 @@
+// 3396. Minimum Number of Operations to Make Elements in Array Distinct
+#include "leetcode.h"
+
+/*
+ * you are given an integer array 'nums'. you need to ensure that the elements
+ * in the array are distinct. to achieve this, you can remove 3 elements from
+ * the beginning of the array. if the array has fewer than 3 elements, remove
+ * all remaining elements. note that an empty array is considered to have
+ * distinct elements. return the minimum number of operations needed to make the
+ * elements in the array distinct.
+ */
+
+int minimumOperations(int *nums, int numsSize) {
+ char prev[101], max = -1;
+ memset(prev, -1, sizeof(prev));
+ for (int i = 0; i < numsSize; i++) {
+ if (prev[nums[i]] != -1 && max < prev[nums[i]])
+ max = prev[nums[i]];
+ prev[nums[i]] = i;
+ }
+ return (int)(max + 1) / 3 + ((max + 1) % 3 > 0);
+}
+
+int main() {
+ int n1[] = {1, 2, 3, 4, 2, 3, 3, 5, 7}, n2[] = {4, 5, 6, 4, 4},
+ n3[] = {6, 7, 8, 9};
+ printf("%d\n", minimumOperations(n1, ARRAY_SIZE(n1))); // expect: 2
+ printf("%d\n", minimumOperations(n2, ARRAY_SIZE(n2))); // expect: 2
+ printf("%d\n", minimumOperations(n3, ARRAY_SIZE(n3))); // expect: 0
+}
diff --git a/min_num_op_elem_distinct.py b/min_num_op_elem_distinct.py
new file mode 100644
index 0000000..a0015f9
--- /dev/null
+++ b/min_num_op_elem_distinct.py
@@ -0,0 +1,31 @@
+# 3396. Minimum Number of Operations to Make Elements in Array Distinct
+
+"""
+you are given an integer array 'nums'. you need to ensure that the elements
+in the array are distinct. to achieve this, you can remove 3 elements from
+the beginning of the array. if the array has fewer than 3 elements, remove
+all remaining elements. note that an empty array is considered to have
+distinct elements. return the minimum number of operations needed to make the
+elements in the array distinct.
+"""
+
+
+class Solution(object):
+ def minimumOperations(self, nums):
+ """
+ :type nums: List[int]
+ :rtype: int
+ """
+ prev = [0] * 101
+ for i in range(len(nums) - 1, -1, -1):
+ prev[nums[i]] += 1
+ if prev[nums[i]] == 2:
+ return (i + 3) // 3
+ return 0
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.minimumOperations(nums=[1, 2, 3, 4, 2, 3, 3, 5, 7]))
+ print(obj.minimumOperations(nums=[4, 5, 6, 4, 4]))
+ print(obj.minimumOperations(nums=[6, 7, 8, 9]))
diff --git a/min_ops_arr_eq_k.c b/min_ops_arr_eq_k.c
new file mode 100644
index 0000000..19bc647
--- /dev/null
+++ b/min_ops_arr_eq_k.c
@@ -0,0 +1,35 @@
+// 3375. Minimum Operations to Make Array Values Equal to K
+#include "leetcode.h"
+
+/*
+ * you are given an integer array 'nums' and an integer 'k'. an integer 'h' is
+ * called valid if all values in the array that are strictly greater than 'h'
+ * are identical. for example, if 'nums = [10, 8, 10, 8]', a valid integer is 'h
+ * = 9' because all 'nums[i] > 9' are equal to 10, but 5 is not a valid integer.
+ * you are allowed to perform the following operation on 'nums': select an
+ * integer 'h' that is valid for the current value in 'nums', for each index 'i'
+ * where 'nums[i] > h', set 'nums[i]' to 'h'. return the minimum number of
+ * operations required to make every element in 'nums' equal to 'k'. if it is
+ * impossible, return -1
+ */
+
+int minOperations(int *nums, int numsSize, int k) {
+ ulong bits[2] = {0};
+ int distinct = 0;
+ for (int i = 0; i < numsSize; i++) {
+ if (nums[i] < k)
+ return -1;
+ if (!(bits[nums[i] / 64] & (ulong)1 << (nums[i] % 64)) && nums[i] > k) {
+ distinct++;
+ bits[nums[i] / 64] |= (ulong)1 << (nums[i] % 64);
+ }
+ }
+ return distinct;
+}
+
+int main() {
+ int n1[] = {5, 2, 5, 4, 5}, n2[] = {2, 1, 2}, n3[] = {9, 7, 5, 3};
+ printf("%d\n", minOperations(n1, ARRAY_SIZE(n1), 2)); // expect: 2
+ printf("%d\n", minOperations(n2, ARRAY_SIZE(n2), 2)); // expect: -1
+ printf("%d\n", minOperations(n3, ARRAY_SIZE(n3), 1)); // expect: 4
+}
diff --git a/min_ops_arr_eq_k.py b/min_ops_arr_eq_k.py
new file mode 100644
index 0000000..67ff36e
--- /dev/null
+++ b/min_ops_arr_eq_k.py
@@ -0,0 +1,37 @@
+# 3375. Minimum Operations to Make Array Values Equal to K
+
+"""
+you are given an integer array 'nums' and an integer 'k'. an integer 'h' is
+called valid if all values in the array that are strictly greater than 'h'
+are identical. for example, if 'nums = [10, 8, 10, 8]', a valid integer is 'h
+= 9' because all 'nums[i] > 9' are equal to 10, but 5 is not a valid integer.
+you are allowed to perform the following operation on 'nums': select an
+integer 'h' that is valid for the current value in 'nums', for each index 'i'
+where 'nums[i] > h', set 'nums[i]' to 'h'. return the minimum number of
+operations required to make every element in 'nums' equal to 'k'. if it is
+impossible, return -1
+"""
+
+
+class Solution(object):
+ def minOperations(self, nums, k):
+ """
+ :type nums: List[int]
+ :type k: int
+ :rtype: int
+ """
+ distinct, bits = 0, 101
+ for i in nums:
+ distinct |= 1 << i
+ bits = min(bits, i)
+ if bits < k:
+ return -1
+ cnt = distinct.bit_count()
+ return cnt - 1 if bits == k else cnt
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.minOperations(nums=[5, 2, 5, 4, 5], k=2))
+ print(obj.minOperations(nums=[2, 1, 2], k=2))
+ print(obj.minOperations(nums=[9, 7, 5, 3], k=1))
diff --git a/rabbits_in_forest.c b/rabbits_in_forest.c
new file mode 100644
index 0000000..caf618f
--- /dev/null
+++ b/rabbits_in_forest.c
@@ -0,0 +1,36 @@
+// 781. Rabbits in Forest
+#include "leetcode.h"
+
+/*
+ * there is a forest with an unknown number of rabbits. we asked 'n' rabbits
+ * "how many rabbithave the same colour as you?" and collected the answers in an
+ * integer array 'answers' where 'answers[i]' is the answer of the i'th rabbit.
+ * given the array 'answers', return the minimum number of rabbits that could be
+ * in the forest.
+ */
+
+int numRabbits(int *answers, int answersSize) {
+ int ans = 0;
+ for (int i = 0; i < answersSize - 1; i++) {
+ int freq = 0;
+ if (answers[i] != -1 && answers[i])
+ for (int j = i + 1; j < answersSize; j++) {
+ if (answers[i] == answers[j]) {
+ answers[j] = -1;
+ freq++;
+ }
+ if (freq == answers[i])
+ break;
+ }
+ }
+ for (int i = 0; i < answersSize; i++)
+ if (answers[i] != -1)
+ ans += (answers[i] + 1);
+ return ans;
+}
+
+int main() {
+ int a1[] = {1, 1, 2}, a2[] = {10, 10, 10};
+ printf("%d\n", numRabbits(a1, ARRAY_SIZE(a1))); // expect: 5
+ printf("%d\n", numRabbits(a2, ARRAY_SIZE(a2))); // expect: 11
+}
diff --git a/rabbits_in_forest.py b/rabbits_in_forest.py
new file mode 100644
index 0000000..7d91e99
--- /dev/null
+++ b/rabbits_in_forest.py
@@ -0,0 +1,30 @@
+# 781. Rabbits in Forest
+from collections import Counter
+
+"""
+there is a forest with an unknown number of rabbits. we asked 'n' rabbits
+"how many rabbithave the same colour as you?" and collected the answers in an
+integer array 'answers' where 'answers[i]' is the answer of the i'th rabbit.
+given the array 'answers', return the minimum number of rabbits that could be
+in the forest.
+"""
+
+
+class Solution(object):
+ def numRabbits(self, answers):
+ """
+ :type answers: List[int]
+ :rtype: int
+ """
+ ans, freq = 0, Counter()
+ for i in answers:
+ if freq[i] % (i + 1) == 0:
+ ans += i + 1
+ freq[i] += 1
+ return ans
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.numRabbits(answers=[1, 1, 2]))
+ print(obj.numRabbits(answers=[10, 10, 10]))
diff --git a/range_product_queries_powers.c b/range_product_queries_powers.c
new file mode 100644
index 0000000..fb70f41
--- /dev/null
+++ b/range_product_queries_powers.c
@@ -0,0 +1,79 @@
+// 2438. Range Product Queries of Powers
+#include "leetcode.h"
+
+/*
+ * given a positive integer 'n', there exists a 0-indexed array called 'powers'
+ * composed of the minimum number of powers of 2 that sum to 'n'. the array is
+ * sorted in non-decreasing order, and there is only one way to form the array.
+ * you are also given a 0-indexed 2d integer array 'queries' where 'queries[i] =
+ * [left_i, right_i]'. each 'queries[i]' represents a query where you have to
+ * find the product of all 'powers[j]' with 'left_i <= j <= right_i'. return an
+ * array 'answers', equal in length to 'queries', where 'answers[i]' is the
+ * answer to each i'th query. since the answer may be too large, each
+ * 'answers[i]' should be returned modulo 10e9+7.
+ */
+
+const int mod = 1e9 + 7;
+
+void get_products(int *powers, long long *seg, int root, int low, int high) {
+ if (low == high) {
+ seg[root] = powers[low];
+ return;
+ }
+ int i = (root << 1) + 1;
+ int mid = (low + high) >> 1;
+ get_products(powers, seg, i, low, mid);
+ get_products(powers, seg, i + 1, mid + 1, high);
+ seg[root] = (seg[i] * seg[i + 1]) % mod;
+}
+
+int range_query(long long *seg, int root, int low, int high, int left,
+ int right) {
+ if (high < left || low > right)
+ return 1;
+ if (low >= left && high <= right)
+ return seg[root];
+ int i = (root << 1) + 1;
+ int mid = (low + high) >> 1;
+ long p1 = range_query(seg, i, low, mid, left, right);
+ long p2 = range_query(seg, i + 1, mid + 1, high, left, right);
+ return (p1 * p2) % mod;
+}
+
+int *productQueries(int n, int **queries, int queriesSize, int *queriesColSize,
+ int *returnSize) {
+ int powers[33], ns = 0, mask = 1;
+ while (n > 0) {
+ if (n & mask) {
+ powers[ns++] = mask;
+ n &= ~mask;
+ }
+ mask <<= 1;
+ }
+ long long seg[150];
+ get_products(powers, seg, 0, 0, ns - 1);
+ int *ans = (int *)malloc(queriesSize * sizeof(int));
+ for (int i = 0; i < queriesSize; ++i)
+ ans[i] = range_query(seg, 0, 0, ns - 1, queries[i][0], queries[i][1]);
+ *returnSize = queriesSize;
+ return ans;
+}
+
+int main() {
+ int q1i[3][2] = {{0, 1}, {2, 2}, {0, 3}}, q2i[1][2] = {{0, 0}};
+ 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);
+ int rs1, *pq1 = productQueries(15, q1.arr, q1.row_size, q1.col_size, &rs1);
+ int rs2, *pq2 = productQueries(2, q2.arr, q2.row_size, q2.col_size, &rs2);
+ for (int i = 0; i < rs1; i++)
+ printf("%d ", pq1[i]); // expect: 2 4 6
+ printf("\n");
+ for (int i = 0; i < rs2; i++)
+ printf("%d ", pq2[i]); // expect: 2
+ printf("\n");
+ free(pq1);
+ free(pq2);
+ two_d_arr_free(&q1);
+ two_d_arr_free(&q2);
+}
diff --git a/range_product_queries_powers.py b/range_product_queries_powers.py
new file mode 100644
index 0000000..81b31f9
--- /dev/null
+++ b/range_product_queries_powers.py
@@ -0,0 +1,41 @@
+# 2438. Range Product Queries of Powers
+
+"""
+given a positive integer 'n', there exists a 0-indexed array called 'powers'
+composed of the minimum number of powers of 2 that sum to 'n'. the array is
+sorted in non-decreasing order, and there is only one way to form the array.
+you are also given a 0-indexed 2d integer array 'queries' where 'queries[i] =
+[left_i, right_i]'. each 'queries[i]' represents a query where you have to
+find the product of all 'powers[j]' with 'left_i <= j <= right_i'. return an
+array 'answers', equal in length to 'queries', where 'answers[i]' is the
+answer to each i'th query. since the answer may be too large, each
+'answers[i]' should be returned modulo 10e9+7.
+"""
+
+
+class Solution(object):
+ def productQueries(self, n, queries):
+ """
+ :type n: int
+ :type queries: List[List[int]]
+ :rtype: List[int]
+ """
+ mod, powers, i = 10**9 + 7, [], 0
+ while n > 0:
+ if n & 1:
+ powers.append(1 << i)
+ n >>= 1
+ i += 1
+ ans = []
+ for left, right in queries:
+ prod = 1
+ for i in range(left, right + 1):
+ prod = (prod * powers[i]) % mod
+ ans.append(prod)
+ return ans
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.productQueries(n=15, queries=[[0, 1], [2, 2], [0, 3]]))
+ print(obj.productQueries(n=2, queries=[[0, 0]]))
diff --git a/substring_xor_queries.c b/substring_xor_queries.c
new file mode 100644
index 0000000..4c2a6d2
--- /dev/null
+++ b/substring_xor_queries.c
@@ -0,0 +1,137 @@
+// 2564. Substring XOR Queries
+#include "leetcode.h"
+
+/*
+ * you are given a binary string 's' and a 2d integer array 'queries' where
+ * 'queries[i] = [first_i, second_i]'. for the i'th query, find the shortest
+ * substring of 's' whose decimal value 'val' yields 'second_i' when bitwise
+ * xor'd with 'first_i'. in other words, 'val ^ first_i == second_i'. the answer
+ * to the i'th query is the endpoints of the substring '[left_i, right_i]' or
+ * '[-1, -1]' if no such substring exists. if there are multiple answers, choose
+ * the one with the minimum 'left_i'. return an array 'ans' where 'ans[i] =
+ * [left_i, right_i]' is the answer to the i'th query. a substring is a
+ * contiguous non-empty sequence of characters within a string.
+ */
+
+struct hash {
+ int key;
+ struct hash *next;
+ UT_hash_handle hh;
+};
+
+void resp(struct hash *entry, int idx, struct hash *entries, int **out) {
+ int start = idx, end = idx, target = entry->key;
+ while (target >>= 1)
+ --start;
+ do {
+ int res = entry - entries;
+ out[res][0] = start;
+ out[res][1] = end;
+ } while ((entry = entry->next));
+}
+
+int **substringXorQueries(char *s, int **queries, int queriesSize,
+ int *queriesColSize, int *returnSize,
+ int **returnColumnSizes) {
+ int **ans = (int **)malloc(queriesSize * sizeof(int *));
+ *returnColumnSizes = (int *)malloc(queriesSize * sizeof(int));
+ for (int i = 0; i < queriesSize; ++i) {
+ ans[i] = (int *)malloc(2 * sizeof(int));
+ (*returnColumnSizes)[i] = 2;
+ }
+ *returnSize = queriesSize;
+ struct hash *table = NULL, *entry;
+ struct hash *const entries =
+ (struct hash *)malloc(queriesSize * sizeof(struct hash));
+ for (int i = 0; i < queriesSize; ++i) {
+ int target = queries[i][0] ^ queries[i][1];
+ HASH_FIND_INT(table, &target, entry);
+ if (!entry) {
+ entries[i].key = target;
+ entries[i].next = NULL;
+ HASH_ADD_INT(table, key, &entries[i]);
+ } else {
+ entries[i].next = entry->next;
+ entry->next = &entries[i];
+ }
+ }
+ int arr[31], cnt = 0;
+ for (int i = 0; s[i]; i++) {
+ cnt = 30 == cnt ? 30 : cnt + 1;
+ for (int j = cnt - 1; j; --j) {
+ arr[j] = (arr[j - 1] << 1) + ('1' == s[i]);
+ HASH_FIND_INT(table, &arr[j], entry);
+ if (entry) {
+ resp(entry, i, entries, ans);
+ HASH_DEL(table, entry);
+ }
+ }
+ arr[0] = ('1' == s[i]);
+ HASH_FIND_INT(table, &arr[0], entry);
+ if (entry) {
+ resp(entry, i, entries, ans);
+ HASH_DEL(table, entry);
+ }
+ }
+ struct hash *tmp;
+ HASH_ITER(hh, table, entry, tmp) {
+ do {
+ ans[entry - entries][0] = -1;
+ ans[entry - entries][1] = -1;
+ } while ((entry = entry->next));
+ }
+ HASH_CLEAR(hh, table);
+ free(entries);
+ return ans;
+}
+
+int main() {
+ char *s1 = "101101", *s2 = "0101", *s3 = "1";
+ int q1i[2][2] = {{0, 5}, {1, 2}}, q2i[1][2] = {{12, 8}}, q3i[1][2] = {{4, 5}};
+ struct two_d_arr q1, q2, q3;
+ 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);
+ two_d_arr_init(&q3, ARRAY_SIZE(q3i), ARRAY_SIZE(q3i[0]), q3i);
+ int rs1, *rcs1,
+ **sxq1 = substringXorQueries(s1, q1.arr, q1.row_size, q1.col_size, &rs1,
+ &rcs1);
+ int rs2, *rcs2,
+ **sxq2 = substringXorQueries(s2, q2.arr, q2.row_size, q2.col_size, &rs2,
+ &rcs2);
+ int rs3, *rcs3,
+ **sxq3 = substringXorQueries(s3, q3.arr, q3.row_size, q3.col_size, &rs3,
+ &rcs3);
+ for (int i = 0; i < rs1; i++) {
+ for (int j = 0; j < rcs1[i]; j++)
+ printf("%d ", sxq1[i][j]); // expect: [[0,2],[2,3]]
+ printf("\n");
+ }
+ printf("\n");
+ for (int i = 0; i < rs2; i++) {
+ for (int j = 0; j < rcs2[i]; j++)
+ printf("%d ", sxq2[i][j]); // expect: [[-1,-1]]
+ printf("\n");
+ }
+ printf("\n");
+ for (int i = 0; i < rs3; i++) {
+ for (int j = 0; j < rcs3[i]; j++)
+ printf("%d ", sxq1[i][j]); // expect: [[0,0]]
+ printf("\n");
+ }
+ printf("\n");
+ for (int i = 0; i < rs1; i++)
+ free(sxq1[i]);
+ free(sxq1);
+ for (int i = 0; i < rs2; i++)
+ free(sxq2[i]);
+ free(sxq1);
+ for (int i = 0; i < rs3; i++)
+ free(sxq3[i]);
+ free(sxq3);
+ free(rcs1);
+ free(rcs2);
+ free(rcs3);
+ two_d_arr_free(&q1);
+ two_d_arr_free(&q2);
+ two_d_arr_free(&q3);
+}
diff --git a/substring_xor_queries.py b/substring_xor_queries.py
new file mode 100644
index 0000000..4e40a1c
--- /dev/null
+++ b/substring_xor_queries.py
@@ -0,0 +1,43 @@
+# 2564. Substring XOR Queries
+from collections import defaultdict
+
+"""
+you are given a binary string 's' and a 2d integer array 'queries' where
+'queries[i] = [first_i, second_i]'. for the i'th query, find the shortest
+substring of 's' whose decimal value 'val' yields 'second_i' when bitwise
+xor'd with 'first_i'. in other words, 'val ^ first_i == second_i'. the answer
+to the i'th query is the endpoints of the substring '[left_i, right_i]' or
+'[-1, -1]' if no such substring exists. if there are multiple answers, choose
+the one with the minimum 'left_i'. return an array 'ans' where 'ans[i] =
+[left_i, right_i]' is the answer to the i'th query. a substring is a
+contiguous non-empty sequence of characters within a string.
+"""
+
+
+class Solution(object):
+ def substringXorQueries(self, s, queries):
+ """
+ :type s: str
+ :type queries: List[List[int]]
+ :rtype: List[List[int]]
+ """
+ n = len(s)
+ vis = defaultdict(lambda: [-1, -1])
+ for i in range(n - 1, -1, -1):
+ if s[i] == "0":
+ vis[0] = [i, i]
+ continue
+ curr = 0
+ for j in range(i, n):
+ curr = curr * 2 + int(s[j])
+ if curr > 2**32:
+ break
+ vis[curr] = [i, j]
+ return [vis[a ^ b] for b, a in queries]
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.substringXorQueries(s="101101", queries=[[0, 5], [1, 2]]))
+ print(obj.substringXorQueries(s="0101", queries=[[12, 8]]))
+ print(obj.substringXorQueries(s="1", queries=[[4, 5]]))