3 ms·
This seems to work (in Ruby): def find_missing_duplicate(seq) sum = seq.reduce(0, :+) corrsum = (seq.size*(seq.size+1))/2 sumpow = seq.map{|i| i
by pedrocr 16y ago
This seems to work (in Ruby):
def find_missing_duplicate(seq)
sum = seq.reduce(0, :+)
corrsum = (seq.size*(seq.size+1))/2
sumpow = seq.map{|i| i*i}.reduce(0, :+)
corrsumpow = (1..seq.size).map{|i| i*i}.reduce(0, :+)
diff = sum - corrsum
diffpow = sumpow - corrsumpow
seq.each do |i|
miss = i-diff
if (i*i - miss*miss == diffpow)
return miss, i
end
end
end
And here's some code to test it:
MIN_N = 2
MAX_N = 1000
(MIN_N..MAX_N).each do |n|
duplicate = missing = rand(n)+1
duplicate = rand(n)+1 while duplicate == missing
seq = (1..n).map{|i| i}
seq[missing-1]=duplicate
miss, dup = find_missing_duplicate(seq)
if !(miss == missing and dup == duplicate)
$stderr.puts "ERROR: expecting #{missing}:#{duplicate} got #{miss}:#{dup}"
end
end