forked from diwu001/Algorithm
-
Notifications
You must be signed in to change notification settings - Fork 0
/
Uneaten_Leaves.java
61 lines (55 loc) · 1.69 KB
/
Uneaten_Leaves.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
/*K caterpillars are eating N leaves, e.g. N=10.
Given int[] a = {2,4,5} as jump numbers,
these caterpillars can eat leaves of 2,4,5,6,8,10, and leaves 1,3,7,9 are uneaten,
so the number of uneaten leaves are 4*/
import java.util.*;
public class Uneaten_Leaves {
public static int count(int total,int n, int[] a) {
int result=0;
ArrayList<ArrayList<Integer>> subset = new ArrayList<ArrayList<Integer>>();
ArrayList<Integer> path = new ArrayList<Integer>();
findAllSubsets(subset,path,0,a);
for(int i=0;i<subset.size();i++) System.out.println(subset.get(i));
for(int i=0;i<subset.size();i++) {
int temp = lcms(subset.get(i));
if(temp>0){
if(subset.get(i).size()%2==0) {
result-=total/temp;
} else {
result+=total/temp;
}
}
}
return total-result;
}
public static void findAllSubsets(ArrayList<ArrayList<Integer>> subset,ArrayList<Integer> path,int index,int[] a) {
if(path.size()>0) subset.add(new ArrayList<Integer>(path));
if(path.size()==a.length) return;
for(int i=index;i<a.length;i++) {
path.add(a[i]);
findAllSubsets(subset,path,i+1,a);
path.remove(path.size()-1);
}
}
public static int lcms(ArrayList<Integer> path) {
if(path.size()==1) return path.get(0);
long result=path.get(0);
for(int i=1;i<path.size();i++) {
long a=path.get(i);
result = a*result/gcd(a,result);
}
return (result<=100000)? (int)result:-1;
}
public static long gcd(long a,long b) {
while(b>0) {
long r=a%b;
a=b;
b=r;
}
return a;
}
public static void main(String[] args) {
int[] a = {2,4,5};
System.out.println(count(10,3,a)); //1 3 7 9->4 leaves
}
}