Generating many random numbers within a range with some exceptions in java

Question

I need to generate lots of random numbers within a range with some exceptions. Right now I'm planning to do it in this way,

public class Main
{
    static List<Integer> except = Arrays.asList(5, 6, 11, 12, 17, 18, 23, 25, 28, 29);
    
    
    public static void main(String[] args) {
        
        List<Integer> randomNums = new ArrayList<>();
        
        Random random = new Random();
        
        int z;
        for(i=0; i<20; i++) {
            z = random.nextInt(30);
            while(except.contains(z)) z = random.nextInt(30);

            randomNums.add(z);
        }           
        
        System.out.println(randomNums);
    }
}

In my case the size of "except" and "randomNums" will be much higher. So the code will spend much time in the while to avoid numbers that I don't want.

I'm curious to know can I speed up my code? If I can remove the while loop then definitely it will be an O(n). But how can I do that. Thanks.

Answer 1

My suggestion is you make a list of all the numbers you do want in your result and each time pick a random member from that list. It requires some initialization, but your loop should run fast after that.

    int maxExclusive = 30;
    Integer[] baseArr = new Integer[maxExclusive];
    Arrays.setAll(baseArr, Integer::valueOf);
    List<Integer> base = new ArrayList<>(Arrays.asList(baseArr));
    base.removeAll(except);
    
    List<Integer> randomNums = new ArrayList<>();
    
    Random random = new Random();
    
    for (int i = 0; i < 20; i++) {
        Integer z = base.get(random.nextInt(base.size()));
        randomNums.add(z);
    }
    
    System.out.println(randomNums);

Example output:

[1, 10, 27, 2, 24, 22, 7, 8, 0, 27, 19, 27, 15, 14, 21, 22, 13, 24, 2, 13]