daily pastebin goal
85%
SHARE
TWEET

Untitled

a guest Oct 19th, 2017 68 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. # You will be given a certain array of length n, such that n > 4, having positive and negative integers but there will be no zeroes and all the elements will occur once in it.
  2.  
  3. # We may obtain an amount of n sub-arrays of length n - 1, removing one element at a time (from left to right).
  4.  
  5. # For each subarray, let's calculate the product and sum of its elements with the corresponding absolute value of the quotient, q = SubProduct/SubSum (if it is possible, SubSum cannot be 0). Then we select the array with the lowest value of |q|(absolute value)
  6.  
  7. # e.g.: we have the array, arr = [1, 23, 2, -8, 5]
  8.  
  9. # Sub Arrays            SubSum    SubProduct         |q|
  10. # [23, 2, -8, 5]         22         -1840         83.636363
  11. # [1, 2, -8, 5]           0           -80          No value
  12. # [1, 23, -8, 5]         21          -920         43.809524
  13. # [1, 23, 2, 5]          31           230          7.419355  <--- selected array
  14. # [1, 23, 2, -8]         18           368         20.444444
  15. # Let's compare the given array with the selected subarray:
  16.  
  17. # [1, 23, 2, -8, 5]
  18. # [1, 23, 2,     5]
  19. # The difference between them is at the index 3 for the given array, with element -8, so we put both things for a result [3, -8].
  20.  
  21. # That means that to obtain the selected subarray we have to take out the value -8 at index 3. We need a function that receives an array as an argument and outputs the the pair [index, arr[index]] that generates the subarray with the lowest value of |q|.
  22.  
  23. # select_subarray([1, 23, 2, -8, 5]) == [3, -8]
  24. # Another case:
  25.  
  26. # select_subarray([1, 3, 23, 4, 2, -8, 5, 18]) == [2, 23]
  27. # In Javascript the function will be selectSubarray().
  28.  
  29. # We may have some special arrays that may have more than one solution as the one that follows below.
  30.  
  31. # select_subarray([10, 20, -30, 100, 200]) == [[3, 100], [4, 200]]
  32. # If there is more than one result the function should output a 2Darray sorted by the index of the element removed from the array.
  33.  
  34. # Thanks to Unnamed for detecting the special cases when we have multiple solutions.
  35.  
  36. require 'minitest/autorun'
  37.  
  38. def select_subarray(ary)
  39.   min = { indexes: [], quotient: Float::MAX }
  40.   ary.each_with_index do |val, i|
  41.     subAry = ary.clone
  42.     subAry.delete_at i
  43.     sum = subSum(subAry)
  44.     next if sum == 0
  45.     quotient = (subProduct(subAry)/sum).abs
  46.     if quotient < min[:quotient]
  47.       min[:quotient] = quotient
  48.       min[:indexes] = [i]
  49.     elsif quotient == min[:quotient]
  50.       min[:indexes] << i
  51.     end
  52.   end
  53.  
  54.   if min[:indexes].length > 1
  55.     min[:indexes].sort.map { |i| [i, ary[i]]}
  56.   end
  57.  
  58.   i = min[:indexes][0]
  59.   [i, ary[i]]
  60. end
  61.  
  62. def subSum(ary)
  63.   ary.inject(&:+)
  64. end
  65.  
  66. def subProduct(ary)
  67.   ary.inject(&:*).to_f
  68. end
  69.  
  70. class QuotientTest < Minitest::Test
  71.   def test_quotient
  72.     assert_equal(select_subarray([1, 23, 2, -8, 5]), [3, -8])
  73.     assert_equal(select_subarray([1, 3, 23, 4, 2, -8, 5, 18]), [2, 23])
  74.     assert_equal select_subarray([10, 20, -30, 100, 200]), [[3, 100], [4, 200]]
  75.   end
  76. end
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top