1

If I have an array of sorted numbers and every object is one of the numbers or multiplication. For example if the sorted array is [1, 2, 7] then the set is {1, 2, 7, 1*2, 1*7, 2*7, 1*2*7}. As you can see if there's n numbers in the sorted array, the size of the set is 2n-1.

My question is how can I find for a given sorted array of n numbers all the objects in the set so that the objects is in a given interval. For example if the sorted array is [1, 2, 3 ... 19, 20] what is the most efficient algorithm to find the objects that are larger than 1000 and less than 2500 (without calculating all the 2n-1 objects)?

  • 1
    Sharing your research helps everyone. Tell us what you've tried and why it didn’t meet your needs. This demonstrates that you’ve taken the time to try to help yourself, it saves us from reiterating obvious answers, and most of all it helps you get a more specific and relevant answer. Also see How to Ask – gnat May 30 '14 at 13:40
1

To search for a "sweet spot" such as this, you generally use a priority queue. The idea being is that you have a list sorted by a specific requirement. The more similar a solution is to a requirement, the more likely it will be chosen from the priority queue to search for more solutions.

In this case, your solution would be a series of indices in which each pertains to a number in your array. So in other words for the solution 2*7, you'd have an array [1,2]. You could also use a binary number with n bits if you prefer. The priority queue, in order to determine which is best, it should mulitply all numbers referred to by the indices together. The sweet spot in this case is going to be the place where you are likely to find most solutions, so in this case it would be the average between the maximum and the minimum, 1750.

The algorithm goes as follows:

Add each number in its own solution array and add it to the priority queue.

Then, starting with the first (the closest to (maximum+minimum)/2), remove it from the priority queue and for each index not included in the solution, add it to the solution and reinsert into the priority queue.

If you find that the current product times each new number exceeds the maximum, you don't even add it to the queue. If it is less than the minimum, then you do nothing with it.

If it is within the minimum and the maximum, do something with it.

Continue until you have them all.

In this way, you're reducing your solution search for values near your average. You should be getting most of your solutions immediately this way, but in order to get them all, you will have to search the entire solution space 2^n-1.

Lets do a quick test for a small range of values [1,2,3,4]. I want to find all solutions whose values are between 10 and 12, then I'd first by adding all numbers in their own solution and putting them in the priority queue. The priority would then look like: [[4],[3],[2],[1]].

I take the first [4], and I append 3, 2, and 1 in their own solutions and add it to the priority queue. The priority queue then becomes:

[[4, 3], [4, 2], [4, 1], [4], [3], [2], [1]]

I see that I've already got my first value [4, 3]! Lets continue and see what happens:

[[4, 3, 1], [4, 2], [4, 1], [4], [3], [2], [1]]

Notice that [4, 3, 2] was too large and was not added. I found another solution [4, 3, 1]!

If something isn't clear ask and I'll try to clarify.

Hope that helps.

  • This question has some similarities to Project Euler #5 in which prime factorization was one approach. For this case, would getting the prime factorization of the numbers be of any use? – user40980 May 30 '14 at 13:58
  • @MichaelT I think for problem #5, you would likely be better off getting all primes of all numbers from 1 to 20 and multiplying them together simply. – Neil May 30 '14 at 14:47
  • That approach would give you a number that is 9699690. However, this number does not evenly divide by 9 or 16 (or 4, or 8, or 12, or 18, or 20). Consider it for the range [1 .. 4] which would suggest the answer is 6 rather than 12. – user40980 May 30 '14 at 15:04
  • @MichaelT If it is divisible by 3 (and it is, because 3 is a prime factor) but not divisible by 9, then multiply by 9. Same for 16. Multiply by 8. I have to check how I resolved it, but I may not have even needed to write a program for it. – Neil May 30 '14 at 15:17
0

The brute force solution to this problem should take only seconds on a modern CPU, given that there are only about a million numbers to check. But that would be too easy.

I am assuming that each product contains each integer once only. [You didn't say.]

Allocate a stack of integers. TOS is the top value. P is the product of integers on the stack.

It would be possible to ignore the number 1. It could be trivially added at the end if needed, but why bother? Pseudocode:

Push 1 on the stack.
Forever do
  If P > 1000 and P < 2500
    Found one: save stack contents
  If TOS == 20
    Pop while TOS == 20
    End if stack is empty
    Increment TOS
  Elsif P >= 2500
    Pop
    Increment TOS
  Else 
    Push TOS+1

Looks like it should work (assuming I understood the problem correctly.) I leave the code as an exercise.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.