Find which element deleted from a sequential array

number_finder.rb

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

number_finder_test.rb

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