Candy splitting - lower memory usage needed

Question

I just did CodeChief's candy splitting task here and my code is working even with a lot of test cases and big numbers, but it uses way too much memory. When I checked my submission, it was 1342M, which is a lot.

import java.util.ArrayList;
import java.util.Scanner;

class Candies {

public static void main(String[] args) {
    Scanner in = new Scanner(System.in);
    int candieStuds;
    int candieT;


    int testCases = in.nextInt();
    ArrayList<String> answ = new ArrayList<String>();
    for(int tCase = 0; tCase < testCases; tCase++){
        int candies = in.nextInt();
        int studs = in.nextInt();
            candieStuds = candies/studs;
        candieT  = candies%studs;
        StringBuilder str = new StringBuilder();
        str.append(candieStuds);
        str.append(" ");
        str.append(candieT);
        answ.add(str.toString());

    }
   for(int listInd = 0; listInd < answ.size(); listInd++){
       System.out.println(answ.get(listInd));
   }
   in.close();
}}

Can someone point out what I should use so I can have the same performance but use less memory?

Answer 1

Your code is a bit messy, and buggy, and you have a significant memory problem in the event of there being a lot of test cases.

Buggy

The problem specifies that the number of candies (N) and children (K) is a value \$0 \le N,K \le 2^{33} - 1\$ The telling part is \$2^{33} - 1\$. That number is larger than a Java int value. You need to use long in order to support the specified input values.

Messy

You declare the variables:

int candieStuds;
int candieT;

outside the loop they are used in. You should declare variables in their scope. It is more readable, and less error prone.

On the other hand, you declare the StringBuilder inside the loop, but that is a system which can be reused, so you should. Declare it outside the loop, then call str.setLength(0) to reset it.

Memory

You declare an array, and store the results of all tests in that array. Once all tests are complete, you report on all the results. In one sense, this is good, because lots of println operations will slow things down. On the other hand, this is bad, because lots of tests cases will fill up memory.....

A compromise is to wrap the System.out in a BufferedWriter, and then write to the buffer for each test, and then let the buffer occasionally flush when it's full (and at the end).

Buffering the System.in is also a good idea.

Performance

Loading all your logic in to a method that is only called once is not a great plan for either readability, or performance.

Java performance is heavily dependent on the JIT compiler. In essence, the basic unit of compilation in Java is a method. You only have one method, and it only gets called once, so it is not likely to be compiled down very well. By giving the compiler more methods, called more often, you give it more to work with in terms of ways to compile things. More is good.

In your case, I would recommend a method for parsing the input lines in to numbers, a method for doing the computations, and another method for preparing the output...

I hacked together the following, which I think will do better (not sure how much better though...). Use it to see what I mean when I talk about the functions, and the buffering.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class CCCandy {

    public static void main(String[] args) throws IOException {
        try (BufferedReader reader = new BufferedReader(new InputStreamReader(System.in))) {
            BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
            try {
                String line = reader.readLine();

                if (line == null) {
                    throw new IllegalStateException("Expecting test count input");
                }

                while ((line = reader.readLine()) != null) {
                    processCandySplit(line, writer);
                }
            } finally {
                writer.flush();
            }
        }
    }

    private static void processCandySplit(String line, BufferedWriter writer)
            throws IOException {
        line = line.trim();
        String[] inputs = line.split("\\s+");
        long candies = Long.parseLong(inputs[0]);
        long kids = Long.parseLong(inputs[1]);

        computeSplit(candies, kids, writer);

    }

    private static void computeSplit(long candies, long kids, BufferedWriter writer)
            throws IOException {
        if (kids == 0) {
            writer.write(String.format("%d %d\n", 0, candies));
        } else {
            writer.write(String.format("%d %d\n", candies / kids, candies % kids));
        }
    }

}