All Possible Products

Performance

Your code is slow because your algorithm is \$O(n^4)\$, where \$n = 900\$:

• The outer x loop runs for 900 iterations (\$O(n)\$).
• For every x, the y loop runs for 900 iterations (\$O(n)\$).
• For every product, you search the array to see if the entry already exists. Since the length of the array will grow up to \$O(n^2)\$, and .include? does a linear search, the deduplication takes \$O(n^2)\$ time.

You can cut the time in half by taking advantage of the fact that \$x \cdot y = y \cdot x\$. The big win, though, would be to store the results in a Set, which performs deduplication for "free". That would bring your runtime down to \$O(n^2)\$.

Style

The standard indentation width for Ruby is two spaces.

The parentheses around (x * y) are superfluous. However, parentheses for the parameter to .include? would be considered good practice.

You are doing redundant extra work, this way you don't have to check if the item is already there :

a = [] for x in 100..999 for y in x..999 num = (x * y) a.push num end end a.uniq! p a 

A functional, concise, space-efficient implementation of the points made in @user50399's answer could be (Ruby >= 2.0):

require 'set' products = (100..999).lazy.flat_map { |x| (x..999).map { |y| x*y } }.to_set 

Here's how the answers posted to date compare in execution speed. [Edit: I updated the results to include another method.

The methods

require 'matrix' require 'set' 

elios264

def elios264(r) a = [] for x in r for y in (x..r.last) num = (x * y) a.push num end end a.uniq! end 

tokland

def tokland(r) r.lazy.flat_map { |x| (x..r.last).map { |y| x*y } }.to_set end 

cary1

def cary1(r) a = [*r] (Matrix::column_vector(a) * Matrix::row_vector(a)).to_a.flatten.uniq end 

cary2

def cary2(r) f, l = r.first, r.last fpl = f+l m = fpl/2 ml = m+1 mf = fpl.odd? ? m : m-1 arr = (f..mf).each_with_object([]) { |i,a| p = i*fpl; (i..mf).each { |j| n = i*j; a << n << p-n } } (ml..l).each { |i| p = i*fpl; (ml..i).each { |j| n = i*j; arr << n << p-n } } if (fpl).even? p = m*fpl (f..mf).each { |i| n = i*m; arr << n << p-n } arr << m*m end arr.uniq end 

The benchmark

Benchmark.bm('elios264'.size) do |bm| r = (100..999) bm.report 'elios264' do elios264(r) end bm.report 'tokland' do tokland(r) end bm.report 'cary1' do cary1(r) end bm.report 'cary2' do cary2(r) end end 

The results

 user system total real elios264 0.280000 0.010000 0.290000 ( 0.298585) tokland 0.320000 0.010000 0.330000 ( 0.322057) cary1 1.160000 0.010000 1.170000 ( 1.174107) cary2 0.210000 0.010000 0.220000 ( 0.221317) 

The results for elios264 were only slightly different when uniq! is changed to uniq.

Here are two other approaches.

#1

You could use methods from the Matrix class:

require 'matrix' def unique_products(r) a = [*r] (Matrix::column_vector(a) * Matrix::row_vector(a)).to_a.flatten.uniq end unique_products((1..4)) #=> [1, 2, 3, 4, 6, 8, 9, 12, 16] 

The class methods Matrix::column_vector and Matrix::row_vector are used to convert r1 to a column vector and r2 to a row vector. Matrix#* is then used to compute the outer product, a matrix that contains the products of all pairs of elements from the two ranges. That matrix is then converted to an array, flattened and uniq'ed, to eliminate duplicates.

Compared to approaches that do not use matrix methods, this one has some extra steps and greater memory requirements. However, the computation of the outer product, being implemented in C, should be relatively fast. Whether this method is faster than other methods is an empirical question. (Edit: the benchmark showed this method to be relatively slow.)

#2

The second approach employs a bit of fine tuning to boost performance:

def cary2(r) f, l = r.first, r.last fpl = f+l m = fpl/2 ml = m+1 mf = fpl.odd? ? m : m-1 arr = (f..mf).each_with_object([]) { |i,a| p = i*fpl; (i..mf).each { |j| n = i*j; a << n << p-n } } (ml..l).each { |i| p = i*fpl; (ml..i).each { |j| n = i*j; arr << n << p-n } } if (fpl).even? p = m*fpl (f..mf).each { |i| n = i*m; arr << n << p-n } arr << m*m end arr.uniq end 

Let f and l be the range endpoints, and let m be the average:

m = (f+l)/2 

There are two cases to consider, depending on whether f+l is even or odd. The easier of the two is when it is odd. Suppose, for example, f=1 and l=6, so m=3 and f+l is odd. In this case the range can be divided into (1..3) and (4..6). Let a be the array that will hold the products. When calculating:

(1..3).each { |i| (i..3).each { |j| a << i*j } 

we can also calculate:

(1..3).each { |i| (i..3).each { |j| a << i*(l-(j-f)) } 

which is:

(1..3).each { |i| (i..3).each { |j| a << i*(f+l) - i*j } 

We can combine these as follows:

fpl = f+l (1..3).each { |i| p = i*fpl; (i..3).each { |j| n = i*j; a << n << p-n } 

Similarly, for

(4..6).each { |i| (4..i).each { |j| a << i*j } 

we can also calculate:

(4..6).each { |i| (4..i).each { |j| a << i*(f+(l-j) } 

which is:

(4..6).each { |i| (4..i).each { |j| a << i*(f+l) - i*j } 

so we can write:

(4..6).each { |i| p = i*fpl; (4..i).each { |j| n = i*j; a << n << p-n } 

These two expressions cover all the products.

If f+l is even, the situation is slightly more complex. Suppose f=1 and l=5, so f+l = 6 and m = 3. In this case we will perform the same calculations as above, but for (1..2) and (4..5). We must then add the combinations involving the midpoint, 3. An efficient way to do this is as follows:

p = 3*(1+5) (1..2).each { |i| n = i*3; arr << n << p-n } arr << 3*3