4 ms·
Here's a sketchy description for a possible solution. The easy part is that we know that if x and y are the missing and duplicate indices form vector V then we
by yuvadam 16y ago
Here's a sketchy description for a possible solution.
The easy part is that we know that if x and y are the missing and duplicate indices form vector V then we have:
|x-y| = |sum(V) - (N*(N-1))/2|
So far - constant space and linear time. From here it's either cleverly (linearly!) scanning the vector or similarly concluding something else about the vector and crossing that info with what we have ;)
- slay2k 16y agoDid you mean (N*(N+1))/2 ?
- yuvadam 16y agoNope :)
- makmanalp 16y agoThis is close to the solution I had in mind, however summing lots of 64 bit integers probably yields a huge number that overflows, so some Bigints (which are comparatively slow) or clever hackery might be required to mitigate that.
- deleted 16y ago[deleted]