Friday, February 12, 2010

Sum It Up

You are given a sequence of numbers from 1 to n-1 with only one of the numbers repeating once. (example: 1 2 2 3 4 5) how can you find the repeating number?
Posted by Administrator at 11:25 PM

1 comment:

  1. AnonymousFebruary 12, 2010 at 11:51 PM

    As a programmer, my first answer to this problem would be make a bit vector of size n, and every time you see the number, set its correspond index bit to 1. if the bit is already set, then that's the repeater. since there were no constraints in the question, this is an ok answer. its good because it makes sense if you draw it for someone, whether they are a programmer, mathematician, or just your grandpa. its not the most efficient answer though.

    Now, if I add the constraint that you can only use a fixed amount of memory (i.e. not determined by n) and it must run in O(n) time... how do we solve it. adding all the numbers up from 1 to n-1 would give us a distinct sum. Subtracting the total sum of all the numbers from the sum of n to n-1 ( which is (n)(n-1)/2 ) would give us the secret extra number.

    What if you can only use a fixed amount of memory, and two of the numbers are repeated? we know that the numbers have a distinct sum, and the difference would be equal to the sum of our unknowns
    c = a + b
    where c is the sum and a and b are the unknowns - c is a constant
    if we had another similar formula we could solve the two unknown equations. my first thought was that the numbers would have a distinct product - (n-1)!
    if we divide the total product by the (n-1)! product, we would get another equation
    c2 = ab
    we could then solve the two equations to get them into quadratic formula notation
    0 = ax^2 + bx + c
    and solve for the two values of x. this answer is correct but factorial grows really fast. Some sort of sum would be better. the sum of the squares from n-1 to 1 would work. that would yield a function of the form
    c2 = a^2 + b^2 which could also be solved by using the quadratic equation.

    ReplyDelete

Subscribe to: Post Comments (Atom)