SHARE
TWEET

Untitled

a guest Oct 19th, 2017 66 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
Top