Bringing the average score up to 9.5

I've been trying my hand at some simple problems on the website topcoder.com. I've been able to solve most of the problems I've tried so far in the Easy/Medium section, but I'm scoring very low. The points are based on running time and the amount of memory used by the program AFAIK.

This is a quick piece of code that I submitted and scored around 75/200, I was just wondering what sort of things I should be avoiding or looking out for in order to write more efficient code?

Quick summary of the problem at hand:


Start with an array of test scores, calculate average and add new test scores of 10/10 to the array until the average is 9.5 or higher.

public class AimToTen{
    public static int need( int[] marks ){
        double average = 0, total = 0;
        int extras = 0;

        for( int x : marks )
            total += x;

        average = total / marks.length;

        if( average >= 9.5 )
            return 0;

        while( average < 9.5 ){
            extras++;
            total += 10;

            average = total / ( marks.length + extras );
        }

        return extras;
    }
}

The trick is not to loop to determine how many extra elements there is to add but to calculate them. A little mathematical consideration can show that you need to add 19 marks.length - 2 total elements.

So a faster solution would be:

public static int need(int[] marks) {
    int total = 0;
    for (int x : marks)
        total += x;

    return Math.max(19 * marks.length - 2 * total, 0);
}

If the number of extra steps to add with the result of that calculation is negative, it means the input array already satisfied the condition and we can return 0.

Here are the result of a small JMH benchmark comparing the code in your question and the above code. The two codes are given a random array of integers between 0 and 10, with a size going from 100,000 to 100,000,000 (Windows 10, JDK 1.8.0_66, i5 3230M @ 2.60GHz).

Benchmark             (arraySize)  Mode  Cnt     Score    Error  Units
StreamTest.testNeed        100000  avgt   30     8,208 ±  0,218  ms/op
StreamTest.testNeed       1000000  avgt   30    78,823 ±  0,834  ms/op
StreamTest.testNeed      10000000  avgt   30   798,294 ±  7,651  ms/op
StreamTest.testNeed     100000000  avgt   30  8038,244 ± 77,131  ms/op
StreamTest.testNeed2       100000  avgt   30     0,037 ±  0,004  ms/op
StreamTest.testNeed2      1000000  avgt   30     0,621 ±  0,179  ms/op
StreamTest.testNeed2     10000000  avgt   30     4,143 ±  0,090  ms/op
StreamTest.testNeed2    100000000  avgt   30    41,597 ±  1,499  ms/op

This shows a tremendous improvement! The code is at least 100x faster.

@Warmup(iterations = 10, time = 1000, timeUnit = TimeUnit.NANOSECONDS)
@Measurement(iterations = 10, time = 1000, timeUnit = TimeUnit.NANOSECONDS)
@BenchmarkMode(Mode.AverageTime)
@OutputTimeUnit(TimeUnit.MILLISECONDS)
@Fork(3)
public class StreamTest {

    private static final Random RANDOM = new Random();

    @State(Scope.Benchmark)
    public static class ArrayContainer {

        @Param({ "100000", "1000000", "10000000", "100000000"})
        private int arraySize;

        private int[] marks;

        @Setup(Level.Iteration)
        public void setUp() {
            marks = RANDOM.ints(arraySize, 0, 10).toArray();
        }

    }

    public static int need( int[] marks ){
        double average = 0, total = 0;
        int extras = 0;

        for( int x : marks )
            total += x;

        average = total / marks.length;

        if( average >= 9.5 )
            return 0;

        while( average < 9.5 ){
            extras++;
            total += 10;

            average = total / ( marks.length + extras );
        }

        return extras;
    }

    public static int need2(int[] marks) {
        int total = 0;
        for (int x : marks)
            total += x;

        return Math.max(19 * marks.length - 2 * total, 0);
    }

    @Benchmark
    public int testNeed(ArrayContainer c) {
        return need(c.marks);
    }

    @Benchmark
    public int testNeed2(ArrayContainer c) {
        return need2(c.marks);
    }

}

StackExchange Code Review Q#117403, answer score: 5