aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--count_subarr_max_elem_k.c20
-rw-r--r--count_subarr_max_elem_k.py16
-rw-r--r--count_subarr_score_less_k.c26
-rw-r--r--count_subarr_score_less_k.py31
-rw-r--r--find_num_even_digit.c27
-rw-r--r--find_num_even_digit.py21
-rw-r--r--max_num_tasks_assign.py64
-rw-r--r--min_ops_make_int_zero.c36
-rw-r--r--min_ops_make_int_zero.py39
9 files changed, 260 insertions, 20 deletions
diff --git a/count_subarr_max_elem_k.c b/count_subarr_max_elem_k.c
index e6bf5ad..4768843 100644
--- a/count_subarr_max_elem_k.c
+++ b/count_subarr_max_elem_k.c
@@ -9,19 +9,15 @@
*/
long long countSubarrays(int *nums, int numsSize, int k) {
- int max = 0, cnt = 0, idx[numsSize];
+ int max = -1, curr = 0;
long long ans = 0;
- for (int i = 0; i < numsSize; i++)
- max = max > nums[i];
- for (int i = 0; i < numsSize; i++)
- if (nums[i] == max)
- idx[cnt++] = i;
- for (int i = 0; i <= cnt - k; i++) {
- long long left = idx[i], right = idx[i + k - 1],
- bound = i - 1 >= 0 ? idx[i - 1] : -1;
- if (!i)
- bound = -1;
- ans += (left - bound) * (numsSize - right);
+ for (int i = 0; i < numsSize; ++i)
+ max = nums[i] > max ? nums[i] : max;
+ for (int l = 0, r = 0; r < numsSize; r++) {
+ curr += nums[r] == max;
+ while (curr >= k)
+ curr -= nums[l++] == max;
+ ans += l;
}
return ans;
}
diff --git a/count_subarr_max_elem_k.py b/count_subarr_max_elem_k.py
index 8f734f2..7852d49 100644
--- a/count_subarr_max_elem_k.py
+++ b/count_subarr_max_elem_k.py
@@ -15,18 +15,18 @@ class Solution(object):
:type k: int
:rtype: int
"""
+ ans, curr, l = 0, 0, 0
m = max(nums)
- ans, curr, i = 0, 0, 0
- for j in range(len(nums)):
- curr += nums[j] == m
+ for r in range(len(nums)):
+ curr += nums[r] == m
while curr >= k:
- curr -= nums[i] == m
- i += 1
- ans += i
+ curr -= nums[l] == m
+ l += 1
+ ans += l
return ans
if __name__ == "__main__":
obj = Solution()
- print(obj.countSubarrays(nums=[1, 3, 2, 3, 3], k=2)) # expect: 6
- print(obj.countSubarrays(nums=[1, 4, 2, 1], k=3)) # expect: 0
+ print(obj.countSubarrays(nums=[1, 3, 2, 3, 3], k=2))
+ print(obj.countSubarrays(nums=[1, 4, 2, 1], k=3))
diff --git a/count_subarr_score_less_k.c b/count_subarr_score_less_k.c
new file mode 100644
index 0000000..5c454d1
--- /dev/null
+++ b/count_subarr_score_less_k.c
@@ -0,0 +1,26 @@
+// 2302. Count Subarrays With Score Less Than K
+#include "leetcode.h"
+
+/*
+ * the score of an array is defined as the product of its sum and its length.
+ * given a positive integer array 'nums' and an integer 'k', return the number
+ * of non-empty subarrays of 'nums' whose score is strictly less than 'k'. a
+ * subarray is a contiguous sequence of elements within an array.
+ */
+
+long long countSubarrays(int *nums, int numsSize, long long k) {
+ long long ans = 0, curr = 0;
+ for (int j = 0, i = 0; j < numsSize; ++j) {
+ curr += nums[j];
+ while (curr * (j - i + 1) >= k)
+ curr -= nums[i++];
+ ans += j - i + 1;
+ }
+ return ans;
+}
+
+int main() {
+ int n1[] = {2, 1, 4, 3, 5}, n2[] = {1, 1, 1};
+ printf("%lld\n", countSubarrays(n1, ARRAY_SIZE(n1), 10)); // expect: 6
+ printf("%lld\n", countSubarrays(n2, ARRAY_SIZE(n2), 5)); // expect: 5
+}
diff --git a/count_subarr_score_less_k.py b/count_subarr_score_less_k.py
new file mode 100644
index 0000000..d60cb4b
--- /dev/null
+++ b/count_subarr_score_less_k.py
@@ -0,0 +1,31 @@
+# 2302. Count Subarrays With Score Less Than K
+
+"""
+the score of an array is defined as the product of its sum and its length.
+given a positive integer array 'nums' and an integer 'k', return the number
+of non-empty subarrays of 'nums' whose score is strictly less than 'k'. a
+subarray is a contiguous sequence of elements within an array.
+"""
+
+
+class Solution(object):
+ def countSubarrays(self, nums, k):
+ """
+ :type nums: List[int]
+ :type k: int
+ :rtype: int
+ """
+ ans, curr, i = 0, 0, 0
+ for j in range(len(nums)):
+ curr += nums[j]
+ while curr * (j - i + 1) >= k:
+ curr -= nums[i]
+ i += 1
+ ans += j - i + 1
+ return ans
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.countSubarrays(nums=[2, 1, 4, 3, 5], k=10))
+ print(obj.countSubarrays(nums=[1, 1, 1], k=5))
diff --git a/find_num_even_digit.c b/find_num_even_digit.c
new file mode 100644
index 0000000..351896f
--- /dev/null
+++ b/find_num_even_digit.c
@@ -0,0 +1,27 @@
+// 1295. Find Numbers with Even Number of Digits
+#include "leetcode.h"
+
+/*
+ * given an array 'nums' of integers, return how many of them contain an even
+ * number of digits.
+ */
+
+int findNumbers(int *nums, int numsSize) {
+ int cnt = 0;
+ for (int i = 0; i < numsSize; i++) {
+ int curr = 0;
+ while (nums[i]) {
+ curr++;
+ nums[i] /= 10;
+ }
+ if (!(curr & 1))
+ cnt++;
+ }
+ return cnt;
+}
+
+int main() {
+ int n1[] = {12, 345, 2, 6, 7896}, n2[] = {555, 901, 482, 1771};
+ printf("%d\n", findNumbers(n1, ARRAY_SIZE(n1))); // expect: 2
+ printf("%d\n", findNumbers(n2, ARRAY_SIZE(n2))); // expect: 1
+}
diff --git a/find_num_even_digit.py b/find_num_even_digit.py
new file mode 100644
index 0000000..5cdb9e3
--- /dev/null
+++ b/find_num_even_digit.py
@@ -0,0 +1,21 @@
+# 1295. Find Numbers with Even Number of Digits
+
+"""
+given an array 'nums' of integers, return how many of them contain an even
+number of digits.
+"""
+
+
+class Solution(object):
+ def findNumbers(self, nums):
+ """
+ :type nums: List[int]
+ :rtype: int
+ """
+ return sum(1 for i in nums if (len(str(i)) & 1) == 0)
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.findNumbers(nums=[12, 345, 2, 6, 7896]))
+ print(obj.findNumbers(nums=[555, 901, 482, 1771]))
diff --git a/max_num_tasks_assign.py b/max_num_tasks_assign.py
new file mode 100644
index 0000000..4c2fbf5
--- /dev/null
+++ b/max_num_tasks_assign.py
@@ -0,0 +1,64 @@
+# 2071. Maximum Number of Tasks You Can Assign
+from bisect import bisect_left
+
+"""
+you have 'n' tasks and 'm' workers. each task has a strength requirement
+stored in a 0-indexed integer array 'tasks', with the i'th task requiring
+'tasks[i]' strength to complete. the strength of each worker is stored in a
+0-indexed array 'workers' with the j'th worker having 'workers[j]' strength.
+each worker can only be assigned to a single task and must have a strength
+greather than or equal to the task's strength requirement. additionally, you
+have 'pills' magic pills that will increase a workers strength by 'strength'.
+you can decide which workers receive the pills, however, you may only give
+each worker at most one magical pill. given the 0-indexed integer arrays
+'tasks' and 'workers' and the integers 'pills' and 'strength', return the
+maximum number of tasks that can be completed.
+"""
+
+
+class Solution(object):
+ def maxTaskAssign(self, tasks, workers, pills, strength):
+ """
+ :type tasks: List[int]
+ :type workers: List[int]
+ :type pills: int
+ :type strength: int
+ :rtype: int
+ """
+
+ def check(k):
+ w, tries = workers[-k:], pills
+ for i in tasks[:k][::-1]:
+ idx = bisect_left(w, i)
+ if idx < len(w):
+ w.pop(idx)
+ elif tries > 0:
+ idx = bisect_left(w, i - strength)
+ if idx < len(w):
+ w.pop(idx)
+ tries -= 1
+ else:
+ return False
+ return len(w) == 0
+
+ tasks = sorted(tasks)
+ workers = sorted(workers)
+ l, r = 0, min(len(workers), len(tasks)) + 1
+ while l + 1 < r:
+ m = l + (r - l) // 2
+ if check(m):
+ l = m
+ else:
+ r = m
+ return l
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.maxTaskAssign(tasks=[3, 2, 1], workers=[0, 3, 3], pills=1, strength=1))
+ print(obj.maxTaskAssign(tasks=[5, 4], workers=[0, 0, 0], pills=1, strength=5))
+ print(
+ obj.maxTaskAssign(
+ tasks=[10, 15, 30], workers=[0, 10, 10, 10, 10], pills=3, strength=10
+ )
+ )
diff --git a/min_ops_make_int_zero.c b/min_ops_make_int_zero.c
new file mode 100644
index 0000000..95d7255
--- /dev/null
+++ b/min_ops_make_int_zero.c
@@ -0,0 +1,36 @@
+// 2749. Minimum Operations to Make the Integer Zero
+#include "leetcode.h"
+
+/*
+ * you are given two integers 'nums1' and 'nums2'. in one operation you can
+ * choose integer 'i' in the range '[0, 60]' and subtract '2^i + num2' from
+ * 'num1'. return the integer denoting the minimum number of operations needed
+ * to make 'nums1' equal to 0. if it is impossible to make 'nums1' equal to 0,
+ * return -1.
+ */
+
+int bit_cnt(long long num) {
+ int cnt = 0;
+ while (num > 0) {
+ cnt += num & 1;
+ num >>= 1;
+ }
+ return cnt;
+}
+
+int makeTheIntegerZero(int num1, int num2) {
+ if (num1 < num2)
+ return -1;
+ for (int i = 0; i <= 100; i++) {
+ long long diff = num1 - 1LL * num2 * i;
+ int bits = bit_cnt(diff);
+ if (bits <= i && i <= diff)
+ return i;
+ }
+ return -1;
+}
+
+int main() {
+ printf("%d\n", makeTheIntegerZero(3, -2)); // expect: 3
+ printf("%d\n", makeTheIntegerZero(5, 7)); // expect: -1
+}
diff --git a/min_ops_make_int_zero.py b/min_ops_make_int_zero.py
new file mode 100644
index 0000000..096921a
--- /dev/null
+++ b/min_ops_make_int_zero.py
@@ -0,0 +1,39 @@
+# 2749. Minimum Operations to Make the Integer Zero
+
+"""
+you are given two integers 'nums1' and 'nums2'. in one operation you can
+choose integer 'i' in the range '[0, 60]' and subtract '2^i + num2' from
+'num1'. return the integer denoting the minimum number of operations needed
+to make 'nums1' equal to 0. if it is impossible to make 'nums1' equal to 0,
+return -1.
+"""
+
+
+class Solution(object):
+ def bit_cnt(self, num):
+ cnt = 0
+ while num > 0:
+ cnt += num & 1
+ num >>= 1
+ return cnt
+
+ def makeTheIntegerZero(self, num1, num2):
+ """
+ :type num1: int
+ :type num2: int
+ :rtype: int
+ """
+ if num1 < num2:
+ return -1
+ for i in range(101):
+ diff = num1 - 1 * num2 * i
+ bits = self.bit_cnt(diff)
+ if bits <= i and i <= diff:
+ return i
+ return -1
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.makeTheIntegerZero(num1=3, num2=-2))
+ print(obj.makeTheIntegerZero(num1=5, num2=7))