All possible products

Question

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 in short amount of time but when the ranges are big, it seems to take really long time. Is there any way to to shorten the time to get the result?

The problem I'm working on is:

"A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 × 99.

Find the largest palindrome made from the product of two 3-digit numbers."

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

Quantum computing, I guess. How long is "really long"? For what values of `x` and `y`? — Reinstate Monica -- notmaynard, Sep 10 '14 at 20:07
See also http://stackoverflow.com/questions/487258/plain-english-explanation-of-big-o (not really a duplicate, but that should have your answer). — Reinstate Monica -- notmaynard, Sep 10 '14 at 20:08
Range of values of x is from 100 too 999. Range of values of y is from 100 to 999.I was hoping to get the result under a minute. — sjk2426, Sep 10 '14 at 20:09
This question appears to be off-topic because it belongs on http://codereview.stackexchange.com — Reinstate Monica -- notmaynard, Sep 10 '14 at 20:15
If your problem is to find the **largest** palindrome, you should work your way down from 999. — awendt, Sep 10 '14 at 20:22

score 2 · Answer 1 · answered Sep 10 '14 at 20:09

This is going to compute 100 x 101 and 101 x 100 separately, even though they're not going to be pushed to the array since they're already in it.

I'm bad at math, but maybe every time x goes up, y's minimum range can go up since that one was just used? people who are better at math can tell me if this is going to start missing numbers.

z= 100
for x in 100..999
    for y in z..999
        num = (x * y)
        unless a.include? num
            a.push num
        end
    z = z+1
    end
end

I think doing this might make the "unless a.include? num" line unnecessary, too.

score 0 · Answer 2 · answered Sep 10 '14 at 20:16

0

What are you really trying to do, i.e. what is the original problem, and why do you need all of these products?

Are you printing every single one out? Is someone asking you for a concrete list of every single one?

If not, there is likely a better way to deal with this problem. For example, if all you wanted is to check if a number X will be an element in "that list of products", all you'd have to do is:

range = 100..999
range.any? { |i| range.include?(x / i) }

answered Sep 10 '14 at 20:16

Kache

15,647
12
51
79

this is the original question: "A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 × 99. Find the largest palindrome made from the product of two 3-digit numbers." – sjk2426 Sep 10 '14 at 20:19
Then yes, there is _definitely_ a smarter way to doing this. For one thing, you're creating _and storing_ an array of every product. Can you think of a way of just validating a product's palindrome-ness, one at a time, without needing to store a whole list of products? – Kache Sep 10 '14 at 20:22
In addition, since you're looking for the "largest palindrome", why not search backwards from 999 to 100? In fact, you can probably just do 999 to 900 and see if you find a palindrome in there. – Kache Sep 10 '14 at 20:28
To check the product's palindrome-ness I was trying to convert the integer into string, split the string in half and check if the first half matches the reverse of the second half. If the length of the string is even, I can split it evenly but if the length of the string is odd, I would leave the element in the middle and check if the first half matches the reverse of the second half. Also, since I was working with for loop, I couldn't do for x in 999..100. Also, I guessed the largest palindrome would be in the range of 900 to 999 (or somewhere up there) but I didn't want to assume too much. – sjk2426 Sep 10 '14 at 20:39
An easier way to check palindrome-ness of a string is just `my_string == my_string.reverse` – Kache Sep 10 '14 at 20:40
my_string == my_string.reverse is so much more simple and easy. I don't know why I was thinking in such a complicated manner. Thank you! – sjk2426 Sep 10 '14 at 20:42

score 0 · Accepted Answer · answered Sep 10 '14 at 20:17

Looking at your code a quick optimization you can make is to use a set rather than an array to store the already computed products.

Since a is an array, a.include?(num) will have to iterate through the entire list of elements before returning true / false.

If a were to be a set, a.include?(num) will return in sub linear time.

Example:

require 'set'
a = Set.new
for x in 100..999
    for y in 100..999
        num = (x * y)
        unless a.include? num
          a.add(num)
        end
    end
end
puts a.to_a.join(", ")

Moreover one of the nice properties of a set is that it only stores unique elements so the following would be equivalent:

require 'set'
a = Set.new
for x in 100..999
    for y in 100..999
        num = (x * y)
        a.add(num)
    end
end
puts a.to_a.join(", ")

This is perfect! I just began to self teach myself ruby and didn't read about "set" yet. Thank you so much! — sjk2426, Sep 10 '14 at 20:25

All possible products

3 Answers3