Using arithmetical operations, how many goals were scored?

Question

A man is keeping score of a football (soccer) game. He tracks partial results like this: 1-0, 1-1, 2-1, 2-2, 3-2. The sum of the goals in all of these partial results is 15, and the final result is 3-2, which is 5 goals. Given N which is sum of the goals of the partial results, you need to find number of goals of the final result. Here are some examples:

Input 15
Output 5

Input 6
Output 3

Input 55
Output 10

I can't use loops to solve the problem; I can only use if/else and arithmetical operations. Using just those operations, how can I find hte number of goals of the final result?

Answer 1

It is a summation problem. A record is created every time a goal is scored. The record is always one larger than the previous record. The total is the sum of all records.

Total = summation( number of goals scored )

So is the total is 1 then you know the number of goals is 1 as well.

If the total is three then there were two goals scored (1 and 1+1)

55 = 10 + 9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 so there were 10 goals scored.

edit Calculating the actual answer is simpler than using the fractional math shown in other answers, but it requires solving a quadratic equation.

Note that the solution to ax**2 + bx + c == 0 is 
x = (-b +/- SQRT( b**2 - 4*a*c) / 2*a

T = n(n+1)/2
2T = n**2 + n
n**2 + n - 2T = 0
n = (-1 +/- SQRT( 1 - 4*1*(-2T))) / (2 * 1), n > 0
n = (SQRT( 1 + 8T ) - 1) / 2

so if T = 10, n = (SQRT(81) - 1) / 2 == 4

Answer 2

r ="result"
s = "sum of goals"
n = "number of goals"

r      s            n

1-0    1            1
1-1    3            2
2-1    6            3
2-2    10           4
3-2    15           5

This tells us that s is just the sum of the first n integers, but we need n(s), not s(n).

Here's an example calculation.

Here's the code for making this happen in java:

class Example {
    public static int n(int s) {
        return (int) Math.round(-1.0 / 2.0 + Math.sqrt(1.0 / 4.0 + 2.0 * s));
    }

    public static int s(int n) {
        return (n * (n + 1)) / 2;
    }

    public static void main(String[] args) {
        for (int n = 0; n <= 10; n++) {
            int s = s(n);
            printResult(s);
        }
    }

    private static void printResult(int s) {
        int n = n(s);
        System.out.println("If the sum of goals is " + s + ", then the number of goals is " + n);
    }
}

Here's the output:

If the sum of goals is 0, then the number of goals is 0
If the sum of goals is 1, then the number of goals is 1
If the sum of goals is 3, then the number of goals is 2
If the sum of goals is 6, then the number of goals is 3
If the sum of goals is 10, then the number of goals is 4
If the sum of goals is 15, then the number of goals is 5
If the sum of goals is 21, then the number of goals is 6
If the sum of goals is 28, then the number of goals is 7
If the sum of goals is 36, then the number of goals is 8

Answer 3

The question is ambiguous as to whether square root is allowed, does it strictly count as an arithmetic operation?

If we assume its not allowed and we cannot use any looping we can use Newton's method to give a good approximation to the answer. Others have pointed out that we are basically trying the find the inverse of the triangular numbers T(n)=n(n+1)/2. If we are given a sum S let f(n)=n^2/2+n/2-S we want to solve f(n)=0. Newton's method is a fast iterative method, given an initial guess x0 we can find a better guess x1 using

 x1 = x0 - f(x) / df(x)

where df(x)=x-1/2 is the derivative. If we do this 4 times we get a pretty good solution.

public class InverseSqrt {

    static float f(float x,float S) {
        return x*x/2+x/2-S;
    }

    static float df(float x,float S) {
        return x+0.5f;
    }

    static float newton(float sum) {
        float x = sum/2; // first initial guess

        // Apply Newton's method four time
        x = x - f(x,sum) / df(x,sum); 
        x = x - f(x,sum) / df(x,sum);
        x = x - f(x,sum) / df(x,sum);
        x = x - f(x,sum) / df(x,sum);
        return x;
    }

    public static void main(String[] args) {
        int i=0;
        int ires=0;
        do {        // loop through possible number of goals
            ++i;
            float s = i * (i+1) * 0.5f; // calculate the total
            float res = newton(s);
            ires = (int) (res+0.5); // round to nearest integer

            System.out.print("T("+i+")="+(int)s);
            System.out.println("\tres="+ires+"\t("+res+")");

        } while(ires==i); // break first time it fails
    }
}

This works pretty well up to an input of 351 giving an output of 26. But fails for the next input 378 giving 28 rather than 27 goal.

We can improve things a bit by using 5 steps of Newtons method working up to an input of 1176 with an output of 48. Tuning the initial guess improves things dramatically, using a starting guess of n/16 with 5 steps works upto input 42195 output 290.

A much better solution can be found using the Fast inverse squareroot. This can be implemented in Java following this answer.

static float Q_rsqrt( float x )
{
    float xhalf = 0.5f*x;
    int i = Float.floatToIntBits(x);
    i = 0x5f3759df - (i>>1);
    x = Float.intBitsToFloat(i);
    x = x*(1.5f - xhalf*x*x);
    return x;
}

Our Newton iteration method is then

static float newton(float sum) {
    float x = Q_rsqrt(1/sum);

    x = x - f(x,sum) / df(x,sum);
    x = x - f(x,sum) / df(x,sum);
    x = x - f(x,sum) / df(x,sum);
    return x;
}

with only 3 iteration steps.

This works upto Input 1073720960 Output 46340. The next item after than gives an integer overflow in calculating the sum, so it can be said to work for all legal int values.

This might not be counted as a legal solution as it uses floatToIntBits(x) and intBitsToFloat(x) which don't really class as arithmetic operations.

Answer 4

It seems that sum of arithmetic progression S(n) is given, and you have to find n. Use simple math and calculate n from equation:

S(n) = n * (n + 1) / 2