Class: Kata::Algorithms::SumOfThreeSort

Inherits:
SumOfThree
  • Object
show all
Defined in:
lib/kata/algorithms/sum_of_three/sum_of_three_sort.rb

Instance Attribute Summary

Attributes inherited from SumOfThree

#array_of_integers

Instance Method Summary collapse

Constructor Details

#initialize(array_of_integers) ⇒ SumOfThreeSort

Returns a new instance of SumOfThreeSort.



7
8
9
 
# File 'lib/kata/algorithms/sum_of_three/sum_of_three_sort.rb', line 7

def initialize(array_of_integers)
  super
end

Instance Method Details

#find_three ⇒ Object

Tries to find 3 integers that sum up to 0. In other words given an array a, we want to find the 3 integers that satisfy the equation:

a[i] + a[j] + a[k] == 0

where i != j && i != k && j !=k

The algorithm first sorts the input array, and then follows a clever algorithm that does not have to use any search for pairs.

This is the pseudo-algorithm

sort(array_of_integers);

for i=0 to n-3 do
  a = S[i];
  j = i+1;
  k = size_of_array - 1;
  while (j < k) do
    b = S[j];
    c = S[k];
    if (a + b + c == 0) then
      return a, b, c; # This is the happy case and we stop
    else if (a + b + c > 0) then
      k = k - 1; # In this case, the b + c is big enough and we need to make it smaller. We know for sure that c is quite big
                 # because it has been set as the value of the element that is on the far right, a.k.a. the biggest one.
                 # So, let us try to use the previous element, which is smaller than c. Hence we will make the (b+c) factor
                 # smaller and the (a + b + c) moving closer to 0.
    else
      j = j + 1; # In this case, the b + c is small enough so that the (a + b + c) < 0. We need to increase b + c but
                 # not so much to go over 0. We need to increase it a little bit. That's why we decide to pick up the
                 # next biggest element, which is j + 1.
    end
  end
end



48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
 
# File 'lib/kata/algorithms/sum_of_three/sum_of_three_sort.rb', line 48

def find_three
  array_of_integers.sort!
  i = 0
  size_of_array = array_of_integers.size
  while i <= size_of_array - 3
    a = array_of_integers[i]
    j = i + 1
    k = size_of_array - 1

    while j < k
      b = array_of_integers[j]
      c = array_of_integers[k]
      sum = a + b + c
      if sum == 0
        return [a, b, c]
      elsif sum > 0
        k -= 1
      else
        j += 1
      end
    end

    i += 1
  end
  []
end