## Saturday, November 28, 2015

### worms eat leaves|Uneaten Leaves – HackerEarth - Zenefits

https://crypticarticles.wordpress.com/2015/08/10/uneaten-leaves-hackerearth-interview-question/
K caterpillars are eating their way through N leaves. Each caterpillar falls from leaf to leaf in a unique sequence.All caterpillars start at a twig in position 0 and fall onto the leaves at positions between 1 and N. Each caterpillar i has an associated ‘jump-number’ A . A caterpillar with jump number j eats leaves at positions that are multiples of j. It will proceed in the order j, 2j, 3j, … till it reaches the end of the leaves, then it stops and builds its cocoon.
Given a set A of K elements, K ≤ 15, N ≤ 10 , we need to determine the number of uneaten leaves.
Input Format:
N = number of leaves
K = number of caterpillars
A = Array of integer jump numbers (one per line).
Output Format:
An integer denoting the number of uneaten leaves.
Sample Input:
10
3

2

4

5

Sample Output:

4
Explanation
[2,4,5] is the 3-member set of jump numbers. All leaves which are multiples of 2, 4, and 5 are eaten. Leaves 1,3,7,9 are left, and they number 4.
`    ``public` `static` `void` `main(String[] args) {`
`        ``// Read Input`
`        ``Scanner scanner = ``new` `Scanner(System.in);`
`        ``System.out.println(``"Input Total Number of Leaves"``);`
`        ``int` `N = scanner.nextInt();`
`        ``int` `balanceN = N;`
`        ``System.out.println(``"Enter total number of Caterpillars"``);`
`        ``int` `K = scanner.nextInt();`
`        ``int``[] A = ``new` `int``[K];`

`        ``System.out.println(``"Array of integer jump numbers (one per line)."``);`
`        ``for` `(``int` `i = ``0``; i < K; i++) {`
`            ``A[i]=scanner.nextInt();`
`            ``int` `gcd=A[i];`
`            ``for` `(``int` `j = ``0``; j <=i && balanceN>``0``; j++) {`
`                ``gcd = findGCD(A[j],A[i]);`
`                ``if` `(gcd>``1``&& gcd<A[i]){`
`                    ``break``;`
`                ``}`
`            ``}`
`            ``if` `(gcd==A[i]){`
`                ``balanceN=balanceN-(N/A[i]);`
`                ``HashSet<Integer> commonMultiples = ``new` `HashSet<Integer>();`
`                ``for` `(``int` `j = ``0``; j <i ; j++) {`
`                   ``int` `lcm = lcm(A[j],A[i]);`

`                     ``while` `(lcm<=N){`
`                        ``commonMultiples.add(lcm);`
`                        ``lcm+=lcm;`
`                        `
`                    ``}`
`                ``}`
`                ``balanceN+=commonMultiples.size();`
`            ``}`

`        ``}`
`        ``System.out.println(``"Balance "` `+ balanceN);`

`    ``}`

`    ``private` `static` `int` `lcm(``int` `a, ``int` `b)`
`    ``{`
`        ``return` `a * (b / findGCD (a, b));`
`    ``}`

`    ``private` `static` `int` `findGCD(``int` `number1, ``int` `number2) {`
`    ``//base case`
`        ``if``(number2 == ``0``)`
`        ``{`
`            ``return` `number1;`
`        ``}`

`        ``return` `findGCD(number2, number1%number2);`
`    ``}`

1. int numberOfUneaten(int n, int[] p){
2.                 // find non divisible numbers in p
3.                 Arrays.sort(p);
4.                 for (int i = 0; i < p.length; i++){
5.                         for (int j = 0; j < i; j++){-google 1point3acres
6.                                 if (p[j] != 0 && p[i] % p[j] == 0){
7.                                         p[i] = 0;. from: 1point3acres.com/bbs
8.                                         break;
9.                                 }
10.                         }
11.                 }
12.                 // find lcm of numbers in p
13.                 int l = 1;
14.                 for (int i = 0; i < p.length; i++){. from: 1point3acres.com/bbs
15.                         if (p[i] != 0){
16.                                 l = lcm(l, p[i]);
17.                         }
18.                 }
19.                 int res = n % l;
20.                 // find undivisible numbers from 1 to min(lcm, n)
21.                 int[] mark = new int[Math.min(l, n) + 1];. 鐣欏鐢宠璁哄潧-涓€浜╀笁鍒嗗湴
22.                 for (int i = 0; i < p.length; i++){. Waral 鍗氬鏈夋洿澶氭枃绔�,
23.                         if (p[i] != 0){. 鐣欏鐢宠璁哄潧-涓€浜╀笁鍒嗗湴
24.                                 for (int j = p[i]; j <= Math.min(l, n); j += p[i]){
25.                                         mark[j] = 1;
26.                                 }. Waral 鍗氬鏈夋洿澶氭枃绔�,
27.                         }
28.                 }
29.                 int count = 0;
30.                 int count1 = 0;
31.                 for (int i = 1; i < Math.min(l, n); i++){
32.                         if (mark[i] == 0){
33.                                 count++;. 鐗涗汉浜戦泦,涓€浜╀笁鍒嗗湴
34.                                 if (i <= res) count1++;. Waral 鍗氬鏈夋洿澶氭枃绔�,
35.                         }
36.                 }.1point3acres缃�
37.                 . 1point 3acres 璁哄潧
38.                 // find undivisible numbers from 1 to n
39.                 if (n < l) return count;. 1point 3acres 璁哄潧
40.                 else{
41.                         return n / l * count + count1;
42.                 }
43.         }.鏈枃鍘熷垱鑷�1point3acres璁哄潧
44.         int lcm(int a, int b){
45.                 return a * b / gcd(a, b);
46.         }
47.         int gcd(int a, int b){. 1point 3acres 璁哄潧
48.                 if (a < b) return gcd(b, a);
49.                 return b == 0 ? a : gcd(b, a % b);. visit 1point3acres.com for more.
50.         }
 此题一开始用暴力法超时，后来用最小公因数最大公倍数的方法还是有几个case超时， 最后实在不想写就直接提交了。自己觉得这题代码写得很烂         public static int eat2(int n, int[] b) {                 HashSet set = new HashSet();                 for (int x : b) {                         boolean test = false;                         for (int y : set) { 鏉ユ簮涓€浜�.涓夊垎鍦拌鍧�.                                  if (x % y == 0){                                         test = true;                                         break;                                 }                                 if (y % x == 0){                                         test = true;                                         set.remove(y);                                         set.add(x);                                         break;                                 }                         }                         if (!test) set.add(x);. more info on 1point3acres.com                 }                                  int cm = 1;                 while (true) {                         boolean test = true;                         for (int x : set) {                                 if (x > cm || cm % x != 0) {                                         test = false;                                         break;                                 }                         }                         if (test) break;. visit 1point3acres.com for more.                         cm++;                 }-google 1point3acres                 int count = 0;                 for (int i = 1; i <= cm; i++) {. more info on 1point3acres.com                         boolean test = false;                         for (int x : set) {. 鐗涗汉浜戦泦,涓€浜╀笁鍒嗗湴                                 if (i >= x && (i % x == 0)) {                                         test = true;                                         break;                                 }                                         }                         if (test) count++;                 }                 int time = n / cm;                 int rest = n % cm;. 鐣欏鐢宠璁哄潧-涓€浜╀笁鍒嗗湴                 int sum = time * count;                                  for (int i = 1; i <= rest; i++) {. 鐣欏鐢宠璁哄潧-涓€浜╀笁鍒嗗湴                         boolean test = false;                         for (int x : set) {                                 if (i >= x && i % x == 0) {                                         test = true;                                         break;. 鍥磋鎴戜滑@1point 3 acres                                 } . 鐣欏鐢宠璁哄潧-涓€浜╀笁鍒嗗湴                         }                         if (test) sum++; 鏉ユ簮涓€浜�.涓夊垎鍦拌鍧�.                  }                 return n - sum;         }
https://github.com/xieqilu/Qilu-leetcode/blob/master/B227.UneatenLeaves.cs
public static int UneatenLeaves(int[] a, int num){
int res = 0;
int numOfSubsets = 1<<a.Length;
for(int i=1;i<numOfSubsets;i++){
int product=1;
int s = CountOne(i) & 1==1? 1:-1;
for(int j=0;j<a.Length;j++){
if(1<<j & i==1)
product*=a[j];
}
res+= s*num/product;
}
return num-res;
}

private static int CountOne(int n){
int count=0;
while(n>0){
n = n & (n-1);
count++;
}
return count;
}