Product of 2 numbers equals sum of numbers between them

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

• 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. – Phrancis Apr 2 '16 at 17:10
• Can you please indent that code? – tokland Apr 3 '16 at 11:19

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.

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.

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;
}


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]])