4
\$\begingroup\$

Problem:

Find all the pairs (a, b) whose product is equal to the sum of all numbers in the sequence [1..n] excluding both a and b.

I have made code for one program and need refactoring for code to get execution in less time. I am currently getting 13 sec for 500 number range.

def get_correct_array(n)
 beginning_time = Time.now
 puts " Begin with #{Time.now}"
 mul = 0
 arr = []
 last_arr = []

(1..n).each do |x|

 (x+1..n).each do |y|

    mul = x * y
    result = (1..n).reject {|n| n == x || n == y}.inject(&:+)
    if result == mul
        arr.concat([x,y])
        @x = x
        @y = y
    end
 end
end

last_arr << arr

if arr != []
 last_arr << (@x,@y = @y,@x)
end
if arr == []
 []
end

end_time = Time.now
puts " Ended with #{Time.now}"
puts "Time Elapsed -> #{(end_time - beginning_time)}"
p last_arr
end
\$\endgroup\$
  • \$\begingroup\$ Welcome to Code Review! I edited the title of your question to say something about what the code does, as we all want to improve our code on this site. I hope you get some good answers. \$\endgroup\$ – Phrancis Apr 2 '16 at 17:10
  • \$\begingroup\$ Can you please indent that code? \$\endgroup\$ – tokland Apr 3 '16 at 11:19
2
\$\begingroup\$

Some notes:

  • Use 2 spaces for indentation.
  • mul = 0 No need to define variables in Ruby.
  • @x = x. @name is a instance variable, but there is no class here. Use only local variables.
  • (1..n).reject {|n| n == x || n == y}.inject(&:+). That's very slow, you should pre-compute the sum before, and just subtract the two elements in every loop.
  • last_arr << (@x,@y = @y,@x). Only the last pair is reversed?
  • Make functions/methods return something.
  • You can use the simple formula n * (n + 1) / 2 for the sum of (1..n).
  • Your code is very, very imperative. For mathematical problems (if not for all), favor a functional style (immutable data-structures)

I'd write:

def get_pairs(n)
  range_sum = (n * (n + 1)) / 2
  pairs = (1..n).to_a.combination(2)
  matching_pairs = pairs.select { |x, y| x * y == range_sum - x - y }
  matching_pairs.flat_map { |x, y| [[x, y], [y, x]] }
end

p get_pairs(26) #=> [[15, 21], [21, 15]]

With n = 500 it takes ~0.1s in my machine. If this is not still fast enough, you can still filter out pair values on the range that are too small to possibly match the sum range.

| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

Code:

I would say that this problem is more mathematical in nature than it is about improvements in code, but here goes:

def get_pairs(n)
  sum = (1..n).reduce(:+)
  pairs = ((n / 2)..n).map do |i|
    num = ((sum - i) / i) - 1
    [i, num] if i * num == sum - i - num
  end.compact
  pairs.flat_map { |x, y| [[x, y], [y, x]] }.sort
end

I took the time to solve the problem on Codewars and what I figured out is that we needed to reduce the number of combinations that we're looping through. It was just too many to try and go through every single combination.

I managed to achieve that by putting this code together:

pairs = ((n / 2)..n).map do |i|
  num = ((sum - i) / i) - 1
  [i, num] if i * num == sum - i - num
end.compact

First I start the loop from (n / 2) because the numbers needed to multiply and equal the sum of all numbers will not be smaller than half the number given.

I then subtract i from the sum with (sum - i) and divide it by i. This gets us close to a possible multiple, but not the exact multiple. We subtract this number by 1 to get to a number that could possibly fit the requirements.

Once we have 2 potential candidates, we return them if they fit the requirement:

i * num == sum - i - num

Explanation:

Let's go through an example to make it clearer:

We'll make n = 110. The correct multiples are 70 and 85.

sum = (1..n).reduce(:+)
# 6105

So the loop will go from 55 to 110:

pairs = ((110 / 2)..110).map do |i|

When it gets to 70 it will do:

num = ((6105 - 70) / 70) - 1
# 6105 - 70 = 6035
# 6035 / 70 = 86
# 86 - 1 = 85

Then we check it:

[70, 85] if 70 * 85 == 6105 - 70 - 85
# 70 * 85 = 5950
# 6105 - 70 - 85 = 5950
# 5950 == 5950
# true

This will then return:

[nil, nil, [70, 85], nil, etc.]

With compact we reduce it to:

[[70, 85]]

Use of flat_map turns this into:

[[70, 85], [85, 70]]

The math here is the most important aspect. We just had to find a way to reduce the number of combinations to loop through, which this does. Before I got to this solution I was stuck at the 6000ms wall.

Benchmarks:

For the number 1000003, my code takes 0.136174 seconds.

I also tested this number with the code in the other answer, but after a few minutes of waiting I terminated it.

This should be a considerably faster solution, but as I said above it is more so a mathematical issue, and not so much a question of efficient code. The code is just to implement the mathematical process after it is found.

| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

As the other posts mention this is a mathematical problem. To pass the challenge on Codewars it is necessary to reduce this from an \$\mathcal{O}(n^2)\$ when using a brute force method to an \$\mathcal{O}(n)\$ complexity.

The requirement that \$a * b = sum - (a+b)\$ would necessitate that for a given value of b and sum, \$a = \frac{\text{sum} - b}{b + 1}\$ by rearranging the equation above. Where sum = sum of all values in the sequence 1 to n.

With that in mind, we will be able to obtain the results in a single loop from 1 to n.

The following is my solution in php but it can be easily implemented in ruby as it contains minimal php functions.

function removeNb($n) {
  $result= [];
  $sum = $n * ($n + 1) / 2;
  for($i = 1; $i<=$n; $i++) {
    //sum = a * b + a + b --- This must be true to meet constraint of product ab equal to sum of all num from 1 to n excluding a and b
    //a = (sum - b) / (b + 1)
    $a = ($sum - $i) / (1+$i);
    if(is_integer($a) && $a < $n) { // a always has a value, ensure that it is an integer less than n as required by kata
      $result[] = [$i, $a];
    }    
  }  

  usort($result, 'sort_by_first');
  return $result;
}

function sort_by_first($a,$b) {
  if($a[0] < $b[0]) return -1;
  if($a[0] > $b[0]) return 1;
  return 0;
}
| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

Implementation in Ruby. Complexity is \$\mathcal{O}(n)\$.

def removNb(n)
    ans = []
    sum = n*(n+1)/2
    (1..n).each {|i| ((sum-i)%(i+1)==0 and (j=(sum-i)/(i+1))<=n) ? ans<<[i,j] : false}
    ans
end

Sample test cases

  1. Test.assert_equals(removNb(26), [[15, 21], [21, 15]])
  2. Test.assert_equals(removNb(102), [[70, 73], [73, 70]])
| improve this answer | |
\$\endgroup\$

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.