Binary Trees With Factors LeetCode solution in C++

1
class Solution {
2
 public:
3
  const int mod = 1e9 + 7;
4
  int numFactoredBinaryTrees(vector<int> &arr) {
5
    sort(arr.begin(), arr.end());
6
    int n = arr.size();
7

8
    vector<int> dp(n, 1);
9

10
    for (int i = 1; i < n; i++) {
11
      int l = 0, r = i - 1;
12
      while (l <= r) {
13
        if (arr[l] * 1LL * arr[r] == arr[i] * 1LL) {
14
          if (l != r)
15
            dp[i] = (dp[i] + (dp[l] * 1LL * dp[r] % mod * 2LL % mod)) % mod;
16
          else
17
            dp[i] = (dp[i] + (dp[l] * 1LL * dp[r] % mod)) % mod;
18
          l++, r--;
19
        } else if (arr[l] * 1LL * arr[r] > arr[i] * 1LL)
20
          r--;
21
        else
22
          l++;
23
      }
24
    }
25

26
    int ans = 0;
27
    for (auto i : dp) ans = (ans + i) % mod;
28
    return ans;
29
  }
30
};