3
\$\begingroup\$

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;
    }
}
\$\endgroup\$

migrated from stackoverflow.com Jan 20 '16 at 21:02

This question came from our site for professional and enthusiast programmers.

  • \$\begingroup\$ And maybe use a float instead of a double, if it is not compulsory to use a double precision number, it would save you some bits of memory \$\endgroup\$ – Dark_eye Jan 16 '16 at 17:41
5
\$\begingroup\$

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);
    }

}
\$\endgroup\$
  • 1
    \$\begingroup\$ This was awesome! Thanks so much :) It seems like a completely different way of thinking about the problem! I'll try and think about different ways to solve the problems in future. Both of you were incredible helpful. So, here is a little plot twist that might puzzle you. I submitted this new piece of code and it scored 164/300 .. Much better than mine, although just over 50% mark. It baffles me how it's supposed to be more efficient? Is it maybe using Java over C++ or Python? \$\endgroup\$ – nickcorin Jan 16 '16 at 18:01
  • 1
    \$\begingroup\$ @nickcorin I edited with a benchmark that shows the big improvement. \$\endgroup\$ – Tunaki Jan 16 '16 at 18:33
2
\$\begingroup\$

Calculate the number of extras (X):

average = (total + 10 * X) / (marks.length + X)
average >= 9.5

(total + 10 * X) / (marks.length + X) >= 9.5
(total + 10 * X) >= 9.5 * (marks.length + X)
total + 10 * X >= 9.5 * marks.length + 9.5 * X
10 * X - 9.5 * X >= 9.5 * marks.length - total
0.5 * X >= 9.5 * marks.length - total
X >= 19 * marks.length - 2 * total
\$\endgroup\$
2
\$\begingroup\$

This is indeed a simple math problem. Suppose the end result after you added need more 10-marks. And you've had have marks already. In that case your average will be

oldTotal = sum(oldMarks);
oldCount = oldMarks.length
totalSum = (oldTotal + need*10)/
totalCount = oldCount + need
newAverage = totalSum / totalCount = (oldTotal + need*10)/(oldCount + need)

and you need it to be more than 9.5. One more tricky part in those kind of problems is rounding errors. So you might be safer if you use 95/10 instead. So, you get this simple equation

(oldTotal + need*10)/(oldCount + need) >= 95/10
10*oldTotal + need*100 >= 95*oldCount + need*95
need*5 >= 95*oldCount - 10*oldTotal
need >= 19*oldCount - 2*oldTotal

As you need the smallest answer, you can just take

need == 19*oldCount - 2*oldTotal
\$\endgroup\$
1
\$\begingroup\$

The following block can be removed, as it does not reduce your runtime when your average is above 9.5 but increases your runtime by one useless if-statement if your average is below 9.5

if( average >= 9.5 )
        return 0;

And use float instead of double to save some memory.

\$\endgroup\$
  • \$\begingroup\$ Using all integer math and no second loop is much faster. if statement is nothing in comparison, and neither is changing double to float. \$\endgroup\$ – Andreas Jan 16 '16 at 17:58
  • \$\begingroup\$ @Andreas: "all integer math" is not possible if you want to calculate decimal places and compare to 9.5 \$\endgroup\$ – Simulant Jan 16 '16 at 21:10
  • \$\begingroup\$ If you look at my answer and the accepted answer, you'll see that it is possible. \$\endgroup\$ – Andreas Jan 16 '16 at 22:48
1
\$\begingroup\$

imho the task contains a "trap". Don't add 10/10 until the score becomes 9.5 but instead just calculate the number needed instead.

i.e.

9.5 <= (10 * extra + total) / (marks.len + extra)
9.5 len + 9.5 extra <= 10 extra + total
9.5 len - total <= 0.5 extra
19 * len - 2 * total <= extra

So just calculate the final left-hand side (in the program) and round up to the nearest integer. Please check if what i wrote is correct, I didn't double check it but the general idea should work jsut fine Like this, no while loop is needed anymore and the program will run much faster.

In your version, most time is most probably spent doing the calculation average = total / ( marks.length + extras ); many times inside the while loop.

\$\endgroup\$
0
\$\begingroup\$

This is more a Math problem than a programming problem.

Suppose you have 200 marks, and a sum of 1500.

That makes an average of 7.5.

The goal is to find the number of 10/10 marks (let's call that x) to add to have an average of 9.5.

So you have the following equation to solve:

(1500 + (x * 10)) / (200 + x) = 9.5

Good luck. That is simple enough for you to find.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy