module Algorithmable::Cups::NumberOfOccurrencesInArray

Public Instance Methods

find_first_one(collection, low, high, target) click to toggle source
# File lib/algorithmable/cups/number_of_occurrences_in_array.rb, line 20
def find_first_one(collection, low, high, target)
  #   if(high >= low)
  #   {
  #     int mid = (low + high)/2;  /*low + (high - low)/2;*/
  #     if( ( mid == 0 || x > arr[mid-1]) && arr[mid] == x)
  #       return mid;
  #     else if(x > arr[mid])
  #       return first(arr, (mid + 1), high, x, n);
  #     else
  #       return first(arr, low, (mid -1), x, n);
  #   }
  #   return -1
end
find_last_one(collection, low, high, target) click to toggle source
# File lib/algorithmable/cups/number_of_occurrences_in_array.rb, line 34
def find_last_one(collection, low, high, target)
  # if(high >= low)
  #   {
  #     int mid = (low + high)/2;  /*low + (high - low)/2;*/
  #     if( ( mid == n-1 || x < arr[mid+1]) && arr[mid] == x )
  #       return mid;
  #     else if(x < arr[mid])
  #       return last(arr, low, (mid -1), x, n);
  #     else
  #       return last(arr, (mid + 1), high, x, n);
  #   }
  #   return -1;
end
linear_solve(collection, target) click to toggle source
# File lib/algorithmable/cups/number_of_occurrences_in_array.rb, line 6
def linear_solve(collection, target)
  result = Hash.new 0
  collection.each do |item|
    result[item] += 1
  end
  result[target]
end
logarithmic(collection, target) click to toggle source
# File lib/algorithmable/cups/number_of_occurrences_in_array.rb, line 14
def logarithmic(collection, target)
  i = find_first_one collection, 0, collection.size - 1, target
  j = find_last_one collection, i, collection.size - 1, target
  j - i + 1
end