1
\$\begingroup\$

I tried to resolve this task:

The integers 14 and 15, are contiguous (1 the difference between them, noticeable) and have the same number of divisors.

14 ----> 1, 2, 7, 14 (4 divisors)
15 ----> 1, 3, 5, 15 (4 divisors)

The next pair of contiguous integers with this property is 21 and 22.

21 -----> 1, 3, 7, 21 (4 divisors)
22 -----> 1, 2, 11, 22 (4 divisors)

We have 8 pairs of integers below 50 having this property, they are:

[[2, 3], [14, 15], [21, 22], [26, 27], [33, 34], [34, 35], [38, 39], [44, 45]]

Let's see now the integers that have a difference of 3 between them. There are seven pairs below 100:

[[2, 5], [35, 38], [55, 58], [62, 65], [74, 77], [82, 85], [91, 94]]

Let's name, diff, the difference between two integers, next and prev, (diff = next - prev) and nMax, an upper bound of the range.

We need a particular function, count_pairsInt(), that receives two arguments, diff, and nMax and outputs the amount of pairs of integers that fulfill this property, all of them being smaller (not less or equal) than nMax.

Let's see it more clearly with examples.

count_pairs_int(1, 50) -----> 8 (See case above)
count_pairs_int(3, 100) -----> 7 (See case above)

Source: codewars.com

My code:

def count_pairs_int(diff, n_max)
  (1..n_max - diff).select { |n| getDivisors(n) == getDivisors(n + diff) }.count
end

def getDivisors(num)
  (1..num).select { |n| (num % n).zero? }.count
end

There is a problem with time of execution code:

The process terminated. It took longer than 8000ms to complete

Initial tests are passed (first 10). Any ideas on how I can optimize the code?

\$\endgroup\$
1
\$\begingroup\$

You are not interested in the divisors themselves, only how many there are. This can be calculated if the prime factors are known. For example, 12 has two 2' s and one 3 (12 = 2*2*3). The divisors are the product of 0,1 or 2 2's and 0 or 1 3's. So six divisors. The primes themselves are irrelevant, what matters is how many of each there are.

If only Ruby shipped with a method to do this prime division...

require 'prime' # delivers the prime_division method

class Integer
  def tau
    self.prime_division.map(&:last).inject(1){|prod,i| prod *= i+1}
  end
end

def count_pairsInt(diff,  nMax )
  (1..nMax-diff).count{|n| n.tau == (n+diff).tau}
end

Note: Probably this can be faster by memoizing (storing) the last diff tau (divisor count) calculations, to avoid calculating them twice.

\$\endgroup\$
  • 1
    \$\begingroup\$ thank you @steenslag, you are great. In count_pairseInt should be range (1..nMax - diff). \$\endgroup\$ – Prezes Łukasz Oct 12 '16 at 22:04
  • \$\begingroup\$ @ŁukaszKorol yes, nasty trap I fell into. \$\endgroup\$ – steenslag Oct 12 '16 at 22:22
  • 2
    \$\begingroup\$ Typically it will be much faster, when computing a function on prime factors over a wide range of consecutive integers, to use a sieve approach and compute them all together rather than individually. E.g. for every fifth number, push 5 onto its list of prime factors. \$\endgroup\$ – Erick Wong Oct 12 '16 at 23:53
0
\$\begingroup\$

A glaring performance issue I see is the use of count for both methods. Count will enumerate over each element in the array to return the final count and should be avoided if possible. Instead, you could use size. This alone is a simple change that should greatly improve your execution time.

Your updated code should look like this:

def count_pairs_int(diff, n_max)
  (1..n_max - diff).select { |n| getDivisors(n) == getDivisors(n + diff) }.size
end

def getDivisors(num)
  (1..num).select { |n| (num % n).zero? }.size
end
\$\endgroup\$
  • \$\begingroup\$ thank you for your suggestion. Unfortunately, a process still terminated. \$\endgroup\$ – Prezes Łukasz Oct 12 '16 at 18:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.