All Possible Products

I'm trying to find all possible product of two 3-digit numbers. When I work with small ranges, I'm able to get an output almost instantly but when the ranges are big, it seems to take really long time. I ran the code below and still didn't get an output past 15 minutes. Is there any way to to shorten the time to get the result?

a = []
for x in 100..999
    for y in 100..999
        num = (x * y)
        unless a.include? num
            a.push num
        end
    end
end

p a

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.

StackExchange Code Review Q#62565, answer score: 6