2

For example. Loop through all combinations of 1-99 and 1-99 such that the total of their multiplication goes in descending order.

99 * 99 = 9801
99 * 98 = 9702
98 * 98 = 9604
99 * 97 = 9603
98 * 97 = 9506
99 * 96 = 9504
...
 5 *  1 = 5
 2 *  2 = 4
 4 *  1 = 4
 3 *  1 = 3
 2 *  1 = 2
 1 *  1 = 1

I've tried for a few days to come up with a pattern. At this point I think it's pretty much impossible to do without performing the multiplications first. Has anyone done this?

Inaccurate-
  • 23
  • 3

2 Answers2

0

Here's a merge-sort style divide-and-conquer approach that uses O(log n) memory and O(n log n) time. It cuts the range of the first number in the product in half, and then lazily merges the results of lazily generating the products. I've used a trick of making the products negative in the generator so that the results come out in descending rather than ascending order.

import heapq

def inorder(a0, a1):
    if a1 - a0 == 1:
        return ((-a0*b, a0, b) for b in xrange(a0, 0, -1))
    am = (a0 + a1) // 2
    return heapq.merge(inorder(a0, am), inorder(am, a1))

for r, a, b in inorder(1, 100):
    print a, '*', b, '=', -r
Paul Hankin
  • 54,811
  • 11
  • 92
  • 118
0

This question is essentially a duplicate of Order (a,b) pairs by result of a*b

I've looked through all answers for the question and still believe mine is the best, although it's not the one that was accepted. :)

The key point is this:

  • assume a * b = c such that c is currently the biggest product that you can get
  • then is the next biggest product (a - 1) * b or a * (b - 1)?
  • we don't know unless we compare them, hence we need to maintain a priority queue
  • so in each iteration, we take the biggest product from the priority queue, then add to the priority queue (a - 1) * b and a * (b - 1)

But if you need to loop through ALL combinations anyway, by far the simplest solution would be to generate all products then sort. It's only 10000 items, so any efficiency gain by using the above method will be minimal.

Community
  • 1
  • 1
wookie919
  • 3,054
  • 24
  • 32
  • Thanks for that link; it's perfect. I'm not sure your algorithm is completely correct though. For instance say for a * b = c such that c is the current largest product that a is 98 and b is 98. c would be 9604. The next largest is actually `(a+1)*(b-1)`. Not either `(a-1)*b` or `a*(b-1)`. A priority queue is a great idea though that I hadn't really considered. – Inaccurate- Sep 19 '14 at 14:37
  • It's correct because `(a + 1) * (b - 1)` is already in the priority queue or have already been removed from the priority queue. (And that I've actually implemented this before.) – wookie919 Sep 21 '14 at 21:15