CareerCup

O(1) space O(k.2^k) time solution, where k is the number of caterpillars (independent of n):

Example with n = 10; A = [2,4,5];

Let S2 = set of numbers in range [1..10] that divisible by 2: S2 = {2,4,6,8,10}; |S2| = n/2;
Let S4 = set of numbers in range [1..10] that divisible by 4: S4 = {4,8}; |S4| = n/4;...
Let S5 = set of numbers in range [1..10] that divisible by 5: S5 = {5,10};
Let S24 = set of numbers in range [1..10] that divisible by 2 and 4: S24 = {4,8};
Let S25 = set of numbers in range [1..10] that divisible by 2 and 5: S25 = {10};
Let S54 = set of numbers in range [1..10] that divisible by 5 and 4: S54 = {};
Let S245 = set of numbers in range [1..10] that divisible by 2, 4 and 5: S245 = {};

Let S be the union of all these sets: S=S2 + S4 + S5 + S24 + S25 + S45 + S245 = {2,4,5,6,8,10};

Thus, the number of uneaten leaves is:

ans = n - |S|;

How to calculate |S|: using inclusion-exclusion principle

|S| = |S2| + |S4| + |S5| - |S24| - |S25| - |S45| + |S245|
= 5 + 2 + 2 - 2 - 1 - 0 + 0 = 6

ans =n - |S| = 10 - 6 = 4;

Can you please specify the question properly? Do caterpillar's eat leaves that are a multiple of their jump numbers or what?

And what does the 1,241,3*1 .. mean?

import java.util.*;
public class HelloWorld{

     public static void main(String []args){
         int[] arr = {2, 3, 5};
         
        System.out.println(getCount(arr, 25));
     }
     
     public static int getCount(int[] arr, int num){

        int count=0;
        int sign=-1;
         for(int i=0; i<arr.length; i++){
             sign*=-1;
             count+= getInclExcl(arr, num, i+1, sign);
         }
         return count;
         
     }
     
     private static int getInclExcl(int[] arr, int num, int subsetSize, int sign){
         List<Set<Integer>> list = getAllSubset(arr, subsetSize);
         int count=0;
       
         for(Set<Integer> set : list){
             int lcm = getLCMFromSet(set);
             count+= num/lcm;
         }
         return count*sign;
     }
     
     private static List<Set<Integer>> getAllSubset(int[] arr, int subsetSize){
        List<Set<Integer>> list = new ArrayList<>();
        Set<Integer> set = new HashSet<>();
        getAllSubsetRec(arr, 0, list, set, subsetSize);
        return list;
     }
     
     private static void getAllSubsetRec(int[] arr, int i, List<Set<Integer>> list, 
                Set<Integer> set, int setSize){
         if(set.size()==setSize){
             list.add(new HashSet<>(set));
             return;
         } 
         if(i ==arr.length){
             return;
         }
         set.add(arr[i]);
         getAllSubsetRec(arr, i+1, list, set, setSize);
         set.remove(arr[i]);
         getAllSubsetRec(arr, i+1, list, set, setSize);
     }
     
     private static int getLCMFromSet(Set<Integer> set){
        
        return getLCMFromArray(set.toArray(new Integer[0])); 
     }
     
     private static int getLCMOfTwoNum(int a, int b){
     
        return a * (b / getGCD(a, b));
    }

    private static int getLCMFromArray(int[] input){
 
        for(int i = 1; i < input.length; i++) result = getLCMOfTwoNum(result, input[i]);
        return result;
    }
    
    public static int getGCD(int a, int b) { return b==0 ? a : getGCD(b, a%b); }
}

I think the question is meant to be multiples of the array element. For egs:

a = [2,4,6] // three caterpillars who eat at intervals of 2, 4 and 6
n = 10 // leaves

Hence the output in this case would be 4 leaves, since the 3rd, 5th, 7th and 9th leaf are not eaten by the three caterpillars.

import array


def count(n, a):
    leaves = array.array('i', (0 for i in range(0, n)))
    for i in a:
        j = i - 1
        while(j < n):
            leaves[j] = 1
            j += i
    cnt = 0
    for i in range(0, n):
        if leaves[i] == 0:
            cnt += 1
        print " %d" % leaves[i],


if __name__ == '__main__':
    count(10, [2, 4, 5])

This solution uses O(n) space and O(n) runtime complexity. I am not sure if there's a way to solve this using O(1) space complexity. If there is one I will be very interested to know the method.

public static int numberOfUneatenLeafs(int[] caterpiler, int n) throws Exception
	{
		if (caterpiler == null || caterpiler.length == 0 || n <= 0)
		{
			throw new Exception();
		}
		Util.printArray("Caterpiler jumps:", caterpiler);
		System.out.println("Numbers of leafs: " + n);
		int count = n;

		int[] leafs = new int[n + 1];
		int K = caterpiler.length;

		for (int k = 0; k < K && count > 0; k++)
		{
			int pos = 0;
			pos += caterpiler[k];

			while (pos <= n && leafs[pos] == 0 && count > 0)
			{
				leafs[pos] = 1;
				pos += caterpiler[k];
				count--;
			}

		}

		printUneatenLeafs(leafs);
		System.out.println("Number of uneaten leafs: " + count);
		System.out.println("-------------------------------------------");
		return count;
	}

	private static void printUneatenLeafs(int[] leafs)
	{

		int n = leafs.length;

		System.out.print("Uneaten leafs: ");
		for (int i = 1; i < n; i++)
		{
			if (leafs[i] == 0)
			{
				System.out.print(i + ",");
			}
		}
		System.out.println();
	}

for (int j = 0; j < K; j++) {
			int pos = A[j];
			while(pos <= N) {
				leaves[pos-1] = 1;
				pos = pos + A[j];
			}
		}

static int countUneatenLeave(int N, int[]A)
{
        int [] array = new int[N+1];
        int i;
        for(i = 1; i <= N;i++)
               array[i] = 1;
        int ans = N;
        for(i = 0; i < A.length;i++)
        {
               if(array[A[i]]==0)
                      continue;
               for(i = 1;i*A[i]<=N;i++)
               {       
                      array[A[i]*i]=0;
                      ans--;
               }
       }
       return ans;
}

import java.util.*;

public class UneatenLeaves {


//{2,4,5}
//N= 10
//uneaten leaves= 1,3,7,9

public static void findUneatenLeaves(int [] array, int n)
{
ArrayList<Integer> uneatenLeaves = new ArrayList<Integer>();
ArrayList<Integer> eatenLeaves = new ArrayList<Integer>();

for (int i=1; i<=n; i++)
{
uneatenLeaves.add(i);
}

//1. find the multiple of the eatenLeaves
for (int i=0; i<array.length; i++)
{
eatenLeaves.add(array[i]);

for (int j=1; j<uneatenLeaves.size(); j++)
{

if (array[i]*uneatenLeaves.get(j) <=n)
{
eatenLeaves.add(array[i]*uneatenLeaves.get(j));
}
}
}

// System.out.println(eatenLeaves);

//2. determine the uneaten leaves based on the jump and N
for (int i=0; i<eatenLeaves.size(); i++)
{
for (int j=1; j<uneatenLeaves.size(); j++)
{
if(eatenLeaves.get(i) == uneatenLeaves.get(j))
{
uneatenLeaves.remove(uneatenLeaves.get(j));
}
}
}

System.out.println(uneatenLeaves.size());

}


public static void main (String [] args)
{
int [] array = {3,5};
findUneatenLeaves(array, 20);
}
}

These are brute force solutions. We should also think about deterministic solutions. We know that only k's we are interested is prime numbers (we can easily ignore composite numbers as they are multiple of primes and would get covered if we take care of primes.) For example, if 2 is present, then no need to do any action on 4,6,8 etc as all leaves get eaten by 4,6,8 would already be eaten by 2.

So, we should do following:
1. Find all primes less than or equal to N.
2. See which primes are occurring in k and you get list which are not.
3. Add these to count.
4. Calculate all multiples of remaining primes and add count if they do not have a factor in k.

We only require constant space and time complexity would be O(N)

public int countUneatenLeaves(int numberLeaves, int[] catArray) {
		int uneatenLeaves = 0;
		int catArraySize = catArray.length;
		int countEaten = 0;
		// this will store which leaves are already eaten
		HashMap<Integer,Integer> positionEatenHash = new HashMap<Integer,Integer>();
		//take one element from caterpillar array and find leave position it will eat. Put eaten in hashmap
		for( int i = 0; i < catArraySize; i++ ){
			int catervalue = catArray[i];
			for(int j = 1; j*catervalue <= numberLeaves; j++){
				if(!positionEatenHash.containsKey(catArray[i]*j)){
					positionEatenHash.put(catArray[i]*j, 1);
					countEaten++;
				}
			}
		}
		uneatenLeaves = numberLeaves - countEaten;
		return uneatenLeaves;
	}

import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Solution {
    /*
 * Complete the function below.
 */
 
    static void reduceJumps(int[] A) {
        //16,2,3,8,2
        //0,2,3,8,2
        //0,0,3,8,2
        //0,0,3,8,2
        //0,0,3,0,2
        
        for (int i =0; i < A.length; i++) {
         for (int j =0; j < A.length; j++) {
             if (A[j] !=0 && A[i]%A[j] == 0 && i!=j ) {
                 //A[i] is a multiple of A[j]
                  A[i] = 0;
                 break;
              }
         }
            
        }
    }

       
    static boolean isAlreadyEaten(int [] A, int jump, int i) {
        boolean alreadyEaten = false;
          for (int j=0; j<i ;j++) {
             if (A[j] == 0) {
                 continue;
             }
              if (jump % A[j] == 0) {
                  alreadyEaten = true;
                  break;
              }
          }
          
          return alreadyEaten;
    }
    
    static int countUneatenLeaves(int N, int[] A) {
        reduceJumps(A);
        //2,4,5 are jumps
        //2,0,5
        
        //look at 2 mark 2,4,6,8,10
        //look at 5 
        //N =1-10
        
        //answer = N - set of all potentially eaten leaves
        
        int eatenleaves =0;
        for (int i=0; i< A.length; i++) {
            if (A[i] == 0) {
                continue;
            }
            int k = 1;
            int jump = A[i] * k;
            while(jump <= N) {
              
              if (!isAlreadyEaten(A, jump, i)) {
                 eatenleaves++;
              }
              k++;
              jump = A[i] * k;
              
            }
        }
       
       return N-eatenleaves;

    }

    public static void main(String[] args) throws IOException{
        Scanner in = new Scanner(System.in);
        final String fileName = System.getenv("OUTPUT_PATH");
        BufferedWriter bw = new BufferedWriter(new FileWriter(fileName));
        int res;
        int _N;
        _N = Integer.parseInt(in.nextLine());
        
        
        int _A_size = Integer.parseInt(in.nextLine());
        int[] _A = new int[_A_size];
        int _A_item;
        for(int _A_i = 0; _A_i < _A_size; _A_i++) {
            _A_item = Integer.parseInt(in.nextLine());
            _A[_A_i] = _A_item;
        }
        
        res = countUneatenLeaves(_N, _A);
        bw.write(String.valueOf(res));
        bw.newLine();
        
        bw.close();
    }
}