Last active
August 29, 2015 14:05
-
-
Save varyonic/4231a7c76fd6d9aa2166 to your computer and use it in GitHub Desktop.
Find which element deleted from a sequential array
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
require 'set' | |
module NumberFinder | |
# Most efficient solution for single number missing from sequence. | |
def self.method1(arr) | |
(arr.size+1)*(arr.size+2)/2 - arr.reduce(:+) | |
end | |
# Generic solution works with any quantity of missing numbers. | |
# Creates complete reference set and compares. | |
def self.method2(arr) | |
(Set.new(1..(arr.size+1)).difference Set.new(arr)).first | |
end | |
# Use Ruby's native quicksort and step through looking for the missing numeber. | |
def self.method3(arr) | |
arr.sort! | |
arr.each_index { |i| return (i+1) if arr[i] != i+1 } | |
arr.size+1 | |
end | |
# A less efficient but more expressive variant of 3. | |
def self.method3a(arr) | |
arr.sort! | |
gt = arr.detect { |x| x > arr.index(x)+1 } | |
gt ? gt - 1 : arr.size + 1 | |
end | |
# Use Ruby's native quicksort and bsearch for the missing numeber (Ruby 2+ only). | |
def self.method4(arr) | |
arr.sort! | |
gt = arr.bsearch { |x| x > arr.index(x)+1 if x } | |
gt ? gt - 1 : arr.size + 1 | |
end | |
end |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
gem "minitest" | |
require "minitest/autorun" | |
require 'number_finder' | |
describe NumberFinder do | |
before (:each) do | |
seed = [*1..99] | |
@removed = seed.delete_at(rand(seed.size)-1) | |
@arr = [] | |
@arr << seed.delete_at(rand(seed.size)-1) until seed.empty? | |
end | |
describe "method1" do | |
it "finds the missing number" do | |
missing = NumberFinder.method1(@arr) | |
missing.must_equal @removed | |
end | |
end | |
describe "method2" do | |
it "finds the missing number" do | |
missing = NumberFinder.method2(@arr) | |
missing.must_equal @removed | |
end | |
end | |
describe "method3" do | |
it "finds the missing number" do | |
missing = NumberFinder.method3(@arr) | |
missing.must_equal @removed | |
end | |
end | |
describe "method3a" do | |
it "finds the missing number" do | |
missing = NumberFinder.method3a(@arr) | |
missing.must_equal @removed | |
end | |
end | |
describe "method4" do | |
it "finds the missing number" do | |
missing = NumberFinder.method4(@arr) | |
missing.must_equal @removed | |
end | |
end | |
end |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment