Into which technique would this algorithm fall into? Brute Force or Greedy?

Question

I have an algorithm that I am not sure whether to classify as a greedy algorithm or a brute force algorithm.

while(true) {
            int n = 0;
            int d = 0;
              int r = 0;
              int outcome = 0;
            
            n = scan.nextInt();
            d = scan.nextInt();
            r = scan.nextInt();

            if ( n + d + r == 0) break;

            int[] morning = new int[n];
            int[] afternoon = new int[n];

            for (int i = 0; i < n; i++) {
                morning[i] = scan.nextInt();
            }
            for (int i = 0; i < n; i++) {
                afternoon[i] = -scan.nextInt();
            }

            for (int i = 0; i < n; i++) {
                int sum = morning[i] + (-afternoon[i]) - d;
                if (sum > 0) outcome += sum * r;
            }
            System.out.printf("%d\n", outcome);
        }

I feel like it is most likely greedy, not completely certain.

Answer 1

A Greedy algorithm is one that limits the amount of work it has to do by making certain assumptions about data values it receives along the way. Your code is definitely not greedy, as it is going to perform the same logic on every value in the incoming data set, regardless of the specific values involved.

An algorithm is Brute Force if it takes a naive approach to solving a problem that will consume considerably more resources (time and/or memory) than another algorithm that is able to limit resource usage by being more clever in its approach to the problem.

So if your algorithm is Brute Force or not, IMO, comes down to if there could be a more efficient way to process the same data and arrive at the same answer. Looking at your code, it isn't obvious to me how there could be a more efficient way to do what it is doing. It seems to me that you will need to process every set of values in the data set, regardless of the particular values involved. For that reason, I don't think your algorithm could be said to be Brute Force.

It could be that the incoming data has characteristics that would allow you to optimize your approach. For example, say that you know that once the sum value that you compute for an entry is negative, all of the remaining data values will produce a sum value that is negative as well. In that case, you could stop processing data as soon as you see a negative value for sum. In this case, your algorithm would be Brute Force vs the algorithm that stops processing upon seeing a negative value.