4 ms·

I've been asked this question before. I don't remember if I already knew the answer or not. But.... When does this ever come up in the real world. > You are g

I've been asked this question before. I don't remember if I already knew the answer or not. But.... When does this ever come up in the real world. > You are given an array of n - 1 integers which are in the range between 1 and n. All numbers appear exactly once, except one number, which is missing. Find this missing number. This has happened to me in real life exactly NEVER! I think maybe I was asked you have a list of pairs of integers except one number is missing its pair. Again, no idea where I would apply this in a real world situation.

gnull 6y ago
> This has happened to me in real life exactly NEVER! Do you do something applied like programming? I think problems (and solutions) similar to this one should be easy to find in TCS. The problem you quote seems valuable to me for its insight, it shows that you can reduce certain search problems to algebraic calculations which are easy to do. I think this is useful concept to understand, and a good mental exercise to try coming up with it yourself (even if you don't apply it directly). Could it be that even if you're a programmer who will never have to solve exactly this problem, you could still use the intuition you gain from this problem to solve others (or understand existing solutions you need to implement)? Could it be that you indirectly used the knowledge you have of this solution without being aware of it?
physicles 6y ago
I had a case today where I was comparing two sets for equality. If the range of values is large, you could xor everything together as a O(1) space check for likely equality. Result is nonzero -> sets definitely aren’t equal; result is zero -> sets are probably equal, but you’ll need to check again some other way to make sure. Of course this is absurd if you’re dealing with anything that already fits in ram, but it’s still neat to think about.

gnull 6y ago

> This has happened to me in real life exactly NEVER! Do you do something applied like programming? I think problems (and solutions) similar to this one should be easy to find in TCS. The problem you quote seems valuable to me for its insight, it shows that you can reduce certain search problems to algebraic calculations which are easy to do. I think this is useful concept to understand, and a good mental exercise to try coming up with it yourself (even if you don't apply it directly). Could it be that even if you're a programmer who will never have to solve exactly this problem, you could still use the intuition you gain from this problem to solve others (or understand existing solutions you need to implement)? Could it be that you indirectly used the knowledge you have of this solution without being aware of it?

physicles 6y ago

I had a case today where I was comparing two sets for equality. If the range of values is large, you could xor everything together as a O(1) space check for likely equality. Result is nonzero -> sets definitely aren’t equal; result is zero -> sets are probably equal, but you’ll need to check again some other way to make sure. Of course this is absurd if you’re dealing with anything that already fits in ram, but it’s still neat to think about.