4
\$\begingroup\$

Looking for code review, suggestions for improvement, best practices etc.

Given N leaves numbered from 1 to N . A caterpillar at leaf 1, jumps from leaf to leaf in multiples of Aj (Aj, 2Aj, 3Aj). j is specific to the caterpillar. Whenever a caterpillar reaches a leaf, it eats it a little bit.. You have to find out how many leaves, from 1 to N, are left uneaten after all K caterpillars have reached the end. Each caterpillar has its own jump factor denoted by Aj, and each caterpillar starts at leaf number 1.

Input: The first line consists of a integer T denoting the number of testcases. T test cases follow. Each test case consists of two lines of input. The first line consists of two integers: N, which denotes the number of leaves; and K, which denotes the number of caterpillars. Second line of each test case consists of K space seperated integers denoting the jumping factor of caterpillars.

Example:

Input:
1
10 3 
2 3 5
Output: 2

Explanation: Testcase1: The leaves eaten by the first caterpillar are (2, 4, 6, 8, 10). The leaves eaten by the second caterpilllar are (3, 6, 9) The leaves eaten by the third caterpilllar are (5, 10) Ultimately, the uneaten leaves are 1, 7 and their number is 2

class CatterpillarDetails{
    int leaves;
    public int getLeaves() {
        return leaves;
    }

    ArrayList<Integer> caterpillarOrder;

    public void setCaterpillarOrder(int order) {
        caterpillarOrder.add(order);
    }

    public ArrayList<Integer> getcaterpillarOrder() {
        return caterpillarOrder;
    }

    int noOfCatterpillar;
    public int getNoOfCatterpillar() {
        return noOfCatterpillar;
    }

    int result;

    public int getResult() {
        return result;
    }

    public void setResult(int result) {
        this.result = result;
    }

    CatterpillarDetails(int leaves, int noOfCaterpillar)
    {
        this.leaves = leaves;
        this.noOfCatterpillar = noOfCaterpillar;
        this.caterpillarOrder = new ArrayList<Integer>(noOfCaterpillar);
    }
}

public class Catterpillar {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int testcase = sc.nextInt();
        CatterpillarDetails[] detailsObj = new CatterpillarDetails[testcase];
        for(int i = 0 ; i < testcase ; i++)
        {
            int leaves = sc.nextInt();
            int noOfCatterpillar = sc.nextInt();
            detailsObj[i] = new CatterpillarDetails(leaves,noOfCatterpillar);

            boolean[] eaten = new boolean[leaves];
            for(int j = 0 ; j < noOfCatterpillar ; j++) {
                int catterpillarOrder = sc.nextInt();
                detailsObj[i].setCaterpillarOrder(catterpillarOrder);

                for(int k = 1 ; k <= leaves ; k++)
                {
                    if(catterpillarOrder*k > leaves)
                        break;
                    else
                    {
                        eaten[(catterpillarOrder*k)-1] = true;
                    }
                }
            }
            detailsObj[i].setResult(calculateNotEaten(eaten));
        }
        for(int i = 0 ; i < testcase ; i++)
        {
            System.out.println(detailsObj[i].getResult());
        }
    }

    private static int calculateNotEaten(boolean[] eaten) {
        int count = 0;
        for(Boolean i : eaten)
        {
            if(!i)
            {
                count++;
            }
        }
        return count;
    }
}
\$\endgroup\$
0

1 Answer 1

3
\$\begingroup\$

I'm going to assume this question is in the context of quality interview code, not quality production code. Websites like GeeksForGeeks (https://practice.geeksforgeeks.org/problems/jumping-caterpillars/0) don't grade you based on production code quality.

Your failure to correctly spell the most important word in the problem domain (Caterpillar) would put me off to a sour start. To me, that suggests an inattention to detail. In software development, little details can make a big difference.

You're doing a lot more work than you need to. The basic algorithm here should be - for each leaf, if it can be evenly divided by any of the caterpillar numbers, it gets eaten and you should move on. If none of the caterpillars eat it, increment the uneaten count and continue.

In idiomatic Java, whitespace is placed between a control flow keyword (if, else) and the open paren there is no whitespace before a semicolon binary operators, including -, == and -, should have whitespace on both sides. opening curly braces belong on the same line, not a newline

You should use try-with-resources blocks to handle closeable resources such as Scanner.

testcase is not a good variable name because it doesn't correctly explain what it's pointing to. numberOfTestCases would be better. scanner is also better than sc, because I don't have to assume what it holds.

You can also look for more opportunities to break out methods. A method with as much nested code as you have is hard to read and understand. Maximize readability until you have a known performance bottleneck.

If you were to rewrite your code using all these suggestions, it might look more like the untested code below:

import java.util.Arrays;
import java.util.Scanner;

public class Caterpillar {

    public static void main(String[] args) {
        try (Scanner sc = new Scanner(System.in)) {
            int numberOfTestCases = sc.nextInt();

            for (int testCase = 0; testCase < numberOfTestCases; testCase++) {
                int numberOfLeaves = sc.nextInt();
                int[] caterpillars = readCaterpillarsFrom(sc);
                int uneatenLeaves = 0;
                for (int leaf = 1; leaf <= numberOfLeaves; leaf++) {
                    if (isLeafUneaten(leaf, caterpillars)) {
                        uneatenLeaves++;
                    }
                }
                System.out.println(uneatenLeaves);
            }
        }
    }

    private static int[] readCaterpillarsFrom(Scanner scanner) {
        int[] caterpillars = new int[scanner.nextInt()];
        for (int j = 0; j < caterpillars.length; j++) {
            caterpillars[j] = scanner.nextInt();
        }

        /* You're more likely to get a hit on smaller numbers, so the sort helps you leave earlier in some cases.
         * This is arguably a premature optimization, and may be a performance loss if the there are many 
         * caterpillars and few leaves.
         */
        Arrays.sort(caterpillars);

        return caterpillars;
    }

    private static boolean isLeafUneaten(int leaf, int[] caterpillars) {
        for (int caterpillar : caterpillars) {
            if (leaf % caterpillar == 0) {
                return false;
            }
        }
        return true;
    }

}
\$\endgroup\$
1
  • \$\begingroup\$ Could you please explain when we use the getters and setters methods and why it's not needed here? @Eric Stein Thanks for the minutes in the answer. \$\endgroup\$
    – learner
    Jan 20, 2020 at 1:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.