Product of an Integer Array with Limit

Question

How can I get the product of an integer array with a specific limit in Java?

Lets say:

• array is not sorted
• array may contain any number from -99 to 99.
• the limit specified is 1000.(maxProduct<=1000)

e.g

int[] array = {-5,1,-1,0,10,-10,9,-2,1001};

int maxProduct = arr[0]*arr[2]*arr[4]*arr[5]*arr[6]*arr[7];

Answer 1

if the array have neg numbers then you should have a negative (minimal) value too...

You can interate the array element by element in versions where no streams are avaliable...

int res = 1;
int max = 1000;
for(int i : array){
   res *= i;
   if(res>max) res = max;
}
System.out.println("Product: " +  res);

Answer 2

int max = 1000;
int res = 1;
for (int i : array) {
    if (i >= 0)
        res *= i;
    if (res >= max)
        res = max;
}

this will exclude negative numbers but takes in 0

Answer 3

OptionalInt reduce = Arrays.stream(array).
                     filter(i -> i != 0).
                     reduce((a, b) -> a * b > 1000 ? 1000 : a * b);

System.out.println(reduce.getAsInt());

you can extend or remove the filte. Depending on your requirements ...

Answer 4

If i get it right you are looking for a subset of that array with a maximal product under a given limit and the output to be something like

arr[1]*arr[5]*arr[6]*arr[10]

is the subset with the max. product.

In order to do this you need first to get the powerset of your array, i.e. all possible subsets of your array and calculate the product of each subset checking if it is the maximal under a given limit. Beleow is an example how to do so:

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.List;

public class NewClass {

    public static void main(String[] args) {
        Integer[] array = {-5,1,-1,0,10,-10,9,-2,1001};
        List<Integer> list = Arrays.asList(array);
        Integer limit = 1000;

        List<List<Integer>> powerset = getPowerset(list);
        List<Integer> maxProdList = getMaxProduct(powerset,limit);
        Integer prod =1;
        for(Integer i : maxProdList){
           prod*=i; 
        }
        System.out.println("List: " + maxProdList );
        System.out.println("max product: " + prod );
    }

    //returns all possible subsets [[-5],[-5,1,9],[1,-1,1001][-5,1,-1,0,10] ... and so on]
    // see also http://stackoverflow.com/questions/1670862/obtaining-a-powerset-of-a-set-in-java
    public static List<List<Integer>> getPowerset(Collection<Integer> list) {
        List<List<Integer>> ps = new ArrayList<>();
        ps.add(new ArrayList<>());
        for (Integer item : list) {
          List<List<Integer>> newPs = new ArrayList<>();

          for (List<Integer> subset : ps) {
            newPs.add(subset);
            List<Integer> newSubset = new ArrayList<>(subset);
            newSubset.add(item);
            newPs.add(newSubset);
          }
          ps = newPs;
        }
        return ps;
    }

    public static List<Integer> getMaxProduct(List<List<Integer>> listOfLists, Integer limit){
        List<Integer> listOfMax = new ArrayList<>();
        Integer max = 1;
        for(List<Integer> list : listOfLists){
            Integer prod =1;
            for(Integer i : list){
               prod*=i; 
            }
            if(prod>max && prod<=limit){
                max=prod;
                listOfMax = list;
            }
        }
        return listOfMax;        
    }
}

Answer 5

Here is an idea, roughed out in pseudocode. I haven't tested it:

maxProduct <- 1000
maxRand <- 99
lowLimit <- 5

repeat
  num <- random(1, maxRand)
  add num to array
  maxProduct <- maxProduct DIV num
  maxRand <- minimum(maxRand, maxProduct)
until (maxRand < lowLimit)

if (maxRand > 0) add maxRand to array

I use DIV for integer division and maxRand is added to the array to get the final product closer to the original maxProduct. You can adjust lowLimit as needed. I was feeling lazy so I didn't bother with negative numbers, possibly pick 2, 4 or 6 array elements and switch their signs. As long as there is an even number of negatives then the final product will be positive.