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);

    }

http://www.1point3acres.com/bbs/thread-145290-1-1.html
第二题就是虫吃叶子的题 给定一个int作为叶子的数量，再给一个数组，其中每个数代表一个虫行走的步数， 求没有被吃掉的叶子数量。 比如n = 100, bug = {2,5}, 那么一百片叶子中号码是2或者5的倍数的叶子全部被吃掉了。

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.         }

http://www.1point3acres.com/bbs/thread-133522-1-1.html

此题一开始用暴力法超时，后来用最小公因数最大公倍数的方法还是有几个case超时， 最后实在不想写就直接提交了。自己觉得这题代码写得很烂         public static int eat2(int n, int[] b) {                 HashSet<Integer> set = new HashSet<Integer>();                 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;
}