diff options
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]])) |