Solutions to Find Missing Number in Array.

missing_num_array.rb

# Question:

  # Suppose you have an array of 99 numbers. 
  # The array contains the digits 1 to 100 with one digit missing. 
  # Write four different algorithms to compute the missing number. 
  # Two of these should optimize for low storage and two of these should optimize for fast processing.
  # (Keep in mind, there are no duplicates and the array is not already sorted.)

#######################################################

# Notes:
  # These Solitions are listed based on performace, from fastest to slowest.
  # Currently Ruby does not have a standard method for measuring memory optimization 
  # (like PHP has for example), however, the Performance Benchmark results are shown 
  # at the end of this document.

#######################################################

# Solution 1: Arithmetic Series - **** OPTIMAL SOLUTION ****
  # 1. Resource http://en.wikipedia.org/wiki/Arithmetic_sum#Sum
  # 2. This equation quickly finds sum of our expected series of numbers (1-100).
  # 3. Because, in our case, we have number missing, we need to alter the equation by
  #    by adjusting the increments up by 1.
  # 4. Once we've stored the arithmetic sum, we simply find the array sum,
  #    and subtract.
  # 5. The difference between the two represents the number in the series that is missing.

def arithmetic_find_missing(array)
  arithmetic_sum = (array.length + 1) * (array.length + 2) / 2
  actual_sum = array.reduce(:+)
  arithmetic_sum - actual_sum
end


#########################################################

# Solution 2: Basic iteration -
  # 1. Sort existing array.
  # 2. Iterate over the array.
  # 3. If the difference between consecutive indecies is not
  #    equal to 1, the missing number is equal to the value 
  #    of the current index + 1.
  # 4. Return the missing number.

def iteration_find_missing(array)
  array.sort!
  array.each do |i|
    if array[i + 1] - array[i] != 1
      puts array[i] + 1
    else
      if array[i + 1] - array[i] != 1 && array.last == 100
    	return 1
      elsif array[i + 1] - array[i] != 1 && array.first == 1
        return 100
      end
    end
  end
end

#########################################################

# Solution 3: Comparison -
  # 1. Sort the array.
  # 2. Create a new array of all numbers contained within
  #    the range of our current array.
  # 3. Total the sum of all numbers within each array.
  # 4. The difference between the sums is equalivalent
  #    to the missing number, which was removed from our
  #    original array.
  # 5. If however, we get a difference of 0, then the missing number
  #    is either the first or last number within our range.

def comparison_find_missing(array)
  array.sort!
  new_array = (array.first..array.last).to_a
  new_array_total = new_array.reduce(:+)
  array_total = array.reduce(:+)
  missing = new_array_total - array_total
  if missing == 0 && array.last == 100
    missing = 1
  elsif missing == 0 && array.first == 1
    missing = 100
  else
    missing
  end
end

########################################################

# Solution 4: 
  # 1. This uses a simple ruby compare functionality. Beacuse the range is given
  #    in the problem, it's not optimal, but we can hard code the data range
  #    into our method.

def simple_ruby_missing(array)
  (1..100).to_a - array
end


#########################################################

# Algorithm Tests -
test_array = (1..100).to_a
test_array.delete rand(100)


puts arithmetic_find_missing(test_array)
puts iteration_find_missing(test_array)
puts comparison_find_missing(test_array)
puts simple_ruby_missing(test_array)

#########################################################

#Speed/Performance Tests

require 'benchmark' 

Benchmark.bmbm do |x|
  x.report("Solution #1") { arithmetic_find_missing(test_array) }
  x.report("Solution #2") { iteration_find_missing(test_array) }
  x.report("Solution #3") { comparison_find_missing(test_array) } 
  x.report("Solution #4") { simple_ruby_missing(test_array) }  
end

# Benchmark Results, Testing Runtime (in seconds)
# 
#                user       system     total       real
#  Solution #1   0.000000   0.000000   0.000000 (  0.000012)
#  Solution #2   0.000000   0.000000   0.000000 (  0.000028)
#  Solution #3   0.000000   0.000000   0.000000 (  0.000030)
#  Solution #4   0.000000   0.000000   0.000000 (  0.000046)


#########################################################

nice gist check this one...

def missing_number(array)
     total = array.last * (array.last + 1)/2
    total - array.inject(:+)
end