-
-
Notifications
You must be signed in to change notification settings - Fork 299
/
823.java
68 lines (66 loc) · 2.59 KB
/
823.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
__________________________________________________________________________________________________
sample 11 ms submission
class Solution {
private static final int mod = 1000000007;
public int numFactoredBinaryTrees(int[] A) {
Arrays.sort(A);
long sum = 1;
long[] dp = new long[A.length];
for(int i = 0; i < dp.length; i++) dp[i] = 1;
for(int i = 1; i < A.length; i++) {
int j = 0, k = i - 1;
while(j <= k) {
long prod = A[j] * (long)A[k];
if(prod > A[i]) k--;
else if(prod < A[i]) j++;
else {
dp[i] = (dp[i] + dp[j] * dp[k]) % mod;
if(j < k) dp[i] = (dp[i] + dp[j] * dp[k]) % mod;
j++;
k--;
}
}
sum = (sum + dp[i]) % mod;
}
return (int)sum;
}
}
__________________________________________________________________________________________________
sample 39376 kb submission
class Solution {
public int numFactoredBinaryTrees(int[] A) {
int MOD = 1000000007;
Arrays.sort(A);
HashSet<Integer> numHash = new HashSet<Integer>();
for(int num: A)
numHash.add(num);
int total = 0;
HashMap<Integer, Integer> rtHash = new HashMap<Integer, Integer>();
for(int i = 0; i < A.length; i++){
int count = 1;
int maxNum = (int)Math.pow(A[i], 0.5);
for(int j = 0; j < i && A[j] <= maxNum; j++){
//for(int j = 0; j < i; j++){
if(A[i] % A[j] == 0){
int pair = A[i] / A[j];
if(numHash.contains(pair)){
int dup = (A[j] == pair) ? 1 : 2;
long product = ((long)rtHash.get(A[j])) * ((long)rtHash.get(pair)) % MOD;
//product = (product * dup) % MOD
if(A[j] != pair) product = (product * 2) % MOD;
count = (int)(((long)count + product) % MOD);
//count += (product * dup) % MOD;
//count += ((long)(rtHash.get(A[j]) * rtHash.get(pair) * dup)) % MOD;
//count = count % MOD;
}
}
}
rtHash.put(A[i], count);
//System.out.println(A[i] + ":" + count);
total += count% MOD;
total = total % MOD;
}
return total;
}
}
__________________________________________________________________________________________________