Number of Subsequences That Satisfy the Given Sum Condition LeetCode solution in C++

1
class Solution {
2
 private:
3
  int mod = 1e9 + 7;
4
  int multiply(int a, int b) {
5
    if (b == 0) {
6
      return 0;
7
    } else if (b % 2 == 0) {
8
      int ans = multiply(a, b / 2);
9
      return (ans % mod + ans % mod) % mod;
10
    } else {
11
      int ans = multiply(a, b - 1);
12
      return (a % mod + ans % mod) % mod;
13
    }
14
  }
15
  int power(int b, int e) {
16
    if (e == 0) {
17
      return 1;
18
    } else if (e % 2 == 0) {
19
      int ans = power(b, e / 2);
20
      return multiply(ans, ans);
21
    } else {
22
      int ans = power(b, e - 1);
23
      return multiply(b, ans);
24
    }
25
  }
26

27
 public:
28
  int numSubseq(vector<int> &nums, int target) {
29
    sort(nums.begin(), nums.end());
30
    int start = 0, end = 0;
31
    while (end < nums.size() and nums[start] + nums[end] <= target) {
32
      end++;
33
    }
34
    end--;
35
    int ans = 0;
36
    while (start <= end) {
37
      if (nums[start] + nums[end] <= target) {
38
        ans = (ans % mod + power(2, end - start)) % mod;
39
        start++;
40
      } else {
41
        end--;
42
      }
43
    }
44
    return ans;
45
  }
46
};