CODEWITHSUNDEEP
ruby-on-railsrubyalgorithm
Gol. D Roger
Gol. D Roger

Reputation: 119

How to optimize the program with two for loops

I have a following programm

def calc_res(a)
  n = a.length
  result = 0
  for i in 0 .. (n - 1)
    for j in i .. (n - 1)
      if (a[i] != a[j] && j - i > result) then
        result = j - i
      end
    end
  end
  return result
end

which return following output

irb(main):013:0> calc_res([4, 6, 2, 2, 6, 6, 4])
=> 5

but it is taking time if array size is too large e.g. [0,1,2,3,.....70000]

can any one suggest me how can I optimize it.

Thanks

Upvotes: 0

Views: 126

Answers (3)

engineersmnky
engineersmnky

Reputation: 29318

A more rubyesque versions include:

def calc_res(a)
  last = a.last
  idx = a.find_index {|e| e != last }&.+(1) || a.size
  a.size - idx
end

def calc_res(a)
  last = a.last
  a.size - a.each.with_index(1).detect(->{[a.size]}) {|e,_| e != last }.last 
end

def calc_res(a)
  last = a.last
  a.reduce(a.size) do |memo, e| 
    return memo unless e == last
    memo -= 1
  end
end

def calc_res(a)
  return 0 if b = a.uniq and b.size == 1
  a.size - a.index(b[-1]).+(1)
end

Upvotes: 0

Cary Swoveland
Cary Swoveland

Reputation: 110675

My understanding is that the problem is to find two unique elements in the array whose distance apart (difference in indices) is maximum, and to return the distance they are apart. I return nil if all elements are the same.

My solution attempts to minimize the numbers of pairs of elements that must be examined before an optimal solution is identified. For the example given in the question only two pairs of elements need be considered.

def calc_res(a)
  sz = a.size-1
  sz.downto(2).find { |n| (0..sz-n).any? { |i| a[i] != a[i+n] } }
end

a = [4,6,2,2,6,6,4]
calc_res a
  #=> 5

If sz = a.size-1, sz is the greatest possible distance two elements can be apart. If, for example, a = [1,2,3,4], sz = 3, which is the number of positions 1 and 4 are apart.

For a, sz = a.size-1 #=> 6. I first determine if any pair of elements that are n = sz positions apart are unique. [a[0], a[6]] #=> [4,4] is the only pair of elements 6 positions apart. Since they are not unique I reduce n by one (to 5) and examine all pairs of elements n positions apart, looking for one whose elements are unique. There are two pairs 5 positions apart: [a[0], a[5]] #=> [4,6] and [a[1], a[6]] #=> [6,4]. Both of these meet the test, so we are finished, and return n #=> 5. In fact we are finished after testing the first of these two pairs. Had neither these pairs contained unique values n would have been reduced by 1 to 4 and the three pairs [a[0], a[4]] #=> [4,6], [a[1], a[5]] #=> [6,6] and [a[2], a[6]] #=> [2,6] would have been searched for one with unique values, and so on.

See Integer#downto, Enumerable#find and Enumerable#any?.

Upvotes: 0

Nermin
Nermin

Reputation: 6100

If I have understood the problem you are trying to solve (from code)

def calc_res(a)
  last_index = a.length - 1
  index = 0
  while a[index] == a.last do
    index = index + 1
    break if index == last_index
  end
  last_index - index
end

It checks items from start if they are equal to items from end, end it moves the index toward the last element. As I understood you search for max length between different elements.

For you problem with [4, 6, 2, 2, 6, 6, 4] it will have one iteration and return 5, for the problem with [1...70000] it will have zero iterations and will return the difference in positions for those two (size of the array - 1)

Upvotes: 1

Related Questions