leetcode

Solution to some Leetcode problems written in C++

git clone git://git.dimitrijedobrota.com/leetcode.git

0823.cpp (1172B)

0 class Solution { 1 static const int MOD = 1E9 + 7; 2 3 static int binary_search(const vector<int> &arr, const int end, const int target) { 4 int low = 0, high = end - 1; 5 while (low <= high) { 6 const int mid = low + (high - low) / 2; 7 if (arr[mid] == target) return mid; 8 if (arr[mid] > target) 9 high = mid - 1; 10 else 11 low = mid + 1; 12 } 13 return -1; 14 } 15 16 public: 17 int numFactoredBinaryTrees(vector<int> &arr) const { 18 static int mem[1000]; 19 memset(mem, 0x00, sizeof(mem)); 20 21 sort(begin(arr), end(arr)); 22 long long res = 0; 23 for (int i = 0; i < arr.size(); i++) { 24 const int crnt = arr[i]; 25 long long local = 1; 26 for (int j = 0; j < i; j++) { 27 if (crnt % arr[j] != 0) continue; 28 const int idx = binary_search(arr, i, crnt / arr[j]); 29 if (idx == -1) continue; 30 local = (local + (long long)mem[j] * mem[idx]) % MOD; 31 } 32 mem[i] = local; 33 res = (res + mem[i]) % MOD; 34 } 35 return res; 36 } 37 };