CODEWITHSUNDEEP
rubyalgorithmoptimization
Evan
Evan

Reputation: 6115

optimize this ruby code

So this code will count the total number of pairs of numbers whose difference is K. it is naive method and I need to optimize it. suggestions?

test = $stdin.readlines 

input = test[0].split(" ")

numbers = test[1].split(" ")

N = input[0]
K = input[1]

count = 0

for i in numbers
   current = i.to_i
   numbers.shift
   for j in numbers
       difference = (j.to_i - current).abs
       if (difference == K)
           count += 1
       end
   end
end

puts count

Upvotes: 2

Views: 275

Answers (4)

Joshua Cheek
Joshua Cheek

Reputation: 31726

Would have been nice for you to give some examples of input and output, but I think this is correct.

require 'set'

def count_diff(numbers, difference)
  set = Set.new numbers
  set.inject 0 do |count, num|
    set.include?(num+difference) ? count+1 : count
  end
end


difference  =  gets.split[1].to_i
numbers     =  gets.split.map { |num| num.to_i }

puts count_diff(numbers, difference)

Upvotes: 4

JMichelB
JMichelB

Reputation: 475

Someone deleted his post, or his post was deleted... He had the best solution, here it is :

test = $stdin.readlines
input = test[0].split(" ")
numbers = test[1].split(" ")
K = input[1]
count = 0
numbers.combination(2){|couple| couple.inject(:-).abs == K ? count++}
puts count

You don't even need N.

Upvotes: 1

hugomg
hugomg

Reputation: 69934

Untested, hopefully actual Ruby code

Documentation for Set: http://www.ruby-doc.org/stdlib/libdoc/set/rdoc/classes/Set.html

require 'set'
numbers_set = Set.new
npairs = 0

numbers.each do |number|
     if numbers_set.include?(number + K)
         npairs += 1
     end
     if numbers_set.include?(number - K)
         npairs += 1
     end
     numbers_set.add(number)
end

Upvotes: 3

tskuzzy
tskuzzy

Reputation: 36446

I do not know Ruby so I'll just give you the big idea:

  1. Get the list
  2. Keep a boolean array (call it arr), marking off numbers as true if the number exists in the list
  3. Loop through the list and see if arr[num-K] and/or arr[num+K] is true where num is a number in your list

This uses up quite a bit of memory though so another method is to do the following:

  1. Keep a hash map from an integer n to an integer count
  2. Go through your list, adding num+K and num-K to the hash map, incrementing count accordingly
  3. Go through your list and see if num is in the hash map. If it is, increment your counter by count

Upvotes: 0

Related Questions