commit fc7eb91d22820f3dbf962f377d9c2cda9787f4e5
parent 9dd307dca2a18a16e9a75d5ee511b20d021bff94
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date: Sat, 6 May 2023 11:41:12 +0200
Daily Problem
Diffstat:
2 files changed, 30 insertions(+), 4 deletions(-)
diff --git a/Problems/1498.cpp b/Problems/1498.cpp
@@ -0,0 +1,25 @@
+#define MOD (int)(1E9 + 7)
+#define SIZE (int)(1E5 + 1)
+int pows[SIZE] = {1};
+static const auto Initialize = [] {
+ ios_base::sync_with_stdio(false), cin.tie(nullptr);
+ for (int i = 1; i < SIZE; ++i) pows[i] = (pows[i - 1] << 1) % MOD;
+ return nullptr;
+}();
+
+class Solution {
+public:
+ int numSubseq(vector<int> &nums, int target) {
+ sort(nums.begin(), nums.end());
+ int n = nums.size(), l = 0, r = n - 1;
+
+ int res = 0;
+ while (l <= r) {
+ if (nums[l] + nums[r] > target)
+ r--;
+ else
+ res = (res + pows[r - l++]) % MOD;
+ }
+ return res;
+ }
+};
diff --git a/README.md b/README.md
@@ -101,7 +101,7 @@ for solving problems.
| 0082 | Medium | [Remove Duplicates from Sorted List II](Problems/0082.cpp) |
| 0083 | Easy | [Remove Duplicates from Sorted List](Problems/0083.cpp) |
| 0084 | Hard | [Largest Rectangle in Histogram](Problems/0084.cpp) |
-| 0086 | Medium | [Partition List](Problems/0086.cpp) |
+| 0086 | Medium | [Partition List](Problems/0086.cpp) |
| 0087 | Hard | [Scramble String](Problems/0087.cpp) |
| 0088 | Easy | [Merge Sorted Array](Problems/0088.cpp) |
| 0090 | Medium | [Subsets II](Problems/0090.cpp) |
@@ -223,7 +223,7 @@ for solving problems.
| 0304 | Medium | [Range Sum Query 2D - Immutable](Problems/0304.cpp) |
| 0309 | Medium | [Best Time to Buy and Sell Stock with Cooldown](Problems/0309.cpp) |
| 0310 | Medium | [Minimum Height Trees](Problems/0310.cpp) |
-| 0319 | Medium | [Bulb Switcher](Problems/0319.cpp) |
+| 0319 | Medium | [Bulb Switcher](Problems/0319.cpp) |
| 0322 | Medium | [Coin Change](Problems/0322.cpp) |
| 0326 | Easy | [Power of Three](Problems/0326.cpp) |
| 0328 | Medium | [Odd Even Linked List](Problems/0328.cpp) |
@@ -451,6 +451,7 @@ for solving problems.
| 1480 | Easy | [Running Sum of 1d Array](Problems/1480.cpp) |
| 1489 | Hard | [Find Critical and Pseudo-Critical Edges in Minimum Spanning Tree](Problems/1489.cpp) |
| 1491 | Easy | [Average Salary Excluding the Minimum and Maximum Salary](Problems/1491.cpp) |
+| 1498 | Medium | [Number of Subsequences That Satisfy the Given Sum Condition](Problems/1498.cpp) |
| 1514 | Medium | [Path with Maximum Probability](Problems/1514.cpp) |
| 1519 | Medium | [Number of Nodes in the Sub-Tree With the Same Label](Problems/1519.cpp) |
| 1523 | Easy | [Count Odd Numbers in an Interval Range](Problems/1523.cpp) |
@@ -474,7 +475,7 @@ for solving problems.
| 1704 | Easy | [Determine if String Halves Are Alike](Problems/1704.cpp) |
| 1706 | Medium | [Where Will the Ball Fall](Problems/1706.cpp) |
| 1722 | Medium | [Minimize Hamming Distance After Swap Operations](Problems/1722.cpp) |
-| 1768 | Easy | [Merge Strings Alternately](Problems/1768.cpp) |
+| 1768 | Easy | [Merge Strings Alternately](Problems/1768.cpp) |
| 1786 | Medium | [Number of Restricted Paths From First to Last Node](Problems/1786.cpp) |
| 1791 | Easy | [Find Center of Star Graph](Problems/1791.cpp) |
| 1822 | Easy | [Sign of the Product of an Array](Problems/1822.cpp) |
@@ -499,7 +500,7 @@ for solving problems.
| 2181 | Medium | [Merge Nodes in Between Zeros](Problems/2181.cpp) |
| 2187 | Medium | [Minimum Time to Complete Trips](Problems/2187.cpp) |
| 2192 | Medium | [All Ancestors of a Node in a Directed Acyclic Graph](Problems/2192.cpp) |
-| 2215 | Easy | [Find the Difference of Two Arrays](Problems/2215.cpp) |
+| 2215 | Easy | [Find the Difference of Two Arrays](Problems/2215.cpp) |
| 2218 | Hard | [Maximum Value of K Coins From Piles](Problems/2218.cpp) |
| 2235 | Easy | [Add Two Integers](Problems/2235.cpp) |
| 2236 | Easy | [Root Equals Sum of Children](Problems/2236.cpp) |
