46
Math and Other Problems / Mild Nerdsnipe
« on: July 06, 2008, 01:01:45 am »
A friend at work got me with this one, but luckily I forgot about it because I got distracted with work. When he asked me about it the next morning, I thought about it for a few minutes and had an answer.
You're given a list of arbitrary length where each element in the list is repeated exactly once except for one value in an arbitrary location. Your task is to find the value. You're allowed to pass over the list exactly once and use O(1) (constant, i.e. the amount of space you're using doesn't depend on the size of the list) extra space.
You're given a list of arbitrary length where each element in the list is repeated exactly once except for one value in an arbitrary location. Your task is to find the value. You're allowed to pass over the list exactly once and use O(1) (constant, i.e. the amount of space you're using doesn't depend on the size of the list) extra space.