Posted tagged ‘Sum’

Sum it Up

August 24, 2011

Problem: you are given a sequence of numbers from 1 to n-1 with one of the numbers repeating only once. (example: 1 2 3 3 4 5). how can you find the repeating number? what if i give you the constraint that you can’t use a dynamic amount of memory (i.e. the amount of memory you use can’t be related to n)?
what if there are two repeating numbers (and the same memory constraint?)

Solution

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, mathemetician, 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.

i think its fine to remind someone of the quadratic equation… (maybe only because i myself had to look it up to solve the problem) i mean really though, the last time i used it was probably in 10th grade. as long as they get the idea that given two unknowns and two equations you can solve for the unknowns – thats the point.

Daughters’ Ages

August 24, 2011

Two MIT math grads bump into each other at Fairway on the upper west side. They haven’t seen each other in over 20 years.

THE FIRST GRAD SAYS TO THE SECOND: “how have you been?”
SECOND: “great! i got married and i have three daughters now”
FIRST: “really? how old are they?”
SECOND: “well, the product of their ages is 72, and the sum of their ages is the same as the number on that building over there..”
FIRST: “right, ok.. oh wait.. hmm, i still don’t know”
SECOND: “oh sorry, the oldest one just started to play the piano”
FIRST: “wonderful! my oldest is the same age!”

problem: how old are the daughters?

Solution

solution: start with what you know. you know there are 3 daughters whose ages multiply to 72. let’s look at the possibilities…

AGES:            SUM OF AGES:
1 1 72            74
1 2 36            39
1 3 24            28
1 4 18            23
1 6 12            19
1 8 9             18
2 2 18            22
2 3 12            17
2 4 9             15
2 6 6             14
3 3 8             14
3 4 6             13

after looking at the building number the man still can’t figure out what their ages are (we’re assuming since he’s an MIT math grad, he can factor 72 and add up the sums), so the building number must be 14, since that is the only sum that has more than one possibility.

finally the man discovers that there is an oldest daughter. that rules out the “2 6 6” possibility since the two oldest would be twins. therefore, the daughters ages must be “3 3 8”.

(caveat: an astute reader pointed out that it IS possible for two siblings to have the same age but not be twins, for instance one is born in january, and the next is conceived right away and delivered in october. next october both siblings will be one year old. if a candidate points this out, extra credit points to him/her.)

this question is pretty neat, although there is certainly a bit of an ahafactor to it. the clues are given in such a way that you think you are missing information (the building number), but whats important isn’t the building number, but the fact that the first man thought that it was enough information, but actually wasn’t.

even if the candidate doesn’t know the solution, they could come up with some interesting thoughts. if they just stare at you and shrug “i dunno” then thank them for their time and don’t give them afogcreek pen.