leetcode

Solution to some Leetcode problems written in C++
git clone git://git.dimitrijedobrota.com/leetcode.git
Log | Files | Refs | README | LICENSE

1498.cpp (658B)

      1 #define MOD (int)(1E9 + 7)
      2 #define SIZE (int)(1E5 + 1)
      3 int pows[SIZE] = {1};
      4 static const auto Initialize = [] {
      5     ios_base::sync_with_stdio(false), cin.tie(nullptr);
      6     for (int i = 1; i < SIZE; ++i)
      7         pows[i] = (pows[i - 1] << 1) % MOD;
      8     return nullptr;
      9 }();
     10 
     11 class Solution {
     12   public:
     13     int numSubseq(vector<int> &nums, int target) {
     14         sort(nums.begin(), nums.end());
     15         int n = nums.size(), l = 0, r = n - 1;
     16 
     17         int res = 0;
     18         while (l <= r) {
     19             if (nums[l] + nums[r] > target)
     20                 r--;
     21             else
     22                 res = (res + pows[r - l++]) % MOD;
     23         }
     24         return res;
     25     }
     26 };