Simple O(1) design with detailed explanation
IntuitionFirst, We can think of a number line with numbers from 0 to n. Now, we can divide this number line into some divisions where we can look for a number.T
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->
First, We can think of a number line with numbers from 0 to n. Now, we can divide this number line into some divisions where we can look for a number.
These divisions are created by removing the blacklisted numbers from the number line.
Each of this division covers a range of numbers. Now we can assign an id to each of this division. Now, if we want to pick a random number, we first call random function to pick a division, we want to look for a number, then again call the random function to pick a number from the range of the chosen division. 

For example : n = 10, blackList = [2, 3, 7]

Original number line :

```[0, 1, 2, 3, 4, 5, 6, 8, 9]```

Modified number line with divisions:

```[0, 1] , [4, 5, 6] , [8, 9]```
each of these divisions can be represented by their range like :

```[0 - 1] , [4 - 6] , [8 - 9]```

The id of each of these division is their index in the list.



# Approach
<!-- Describe your approach to solving the problem. -->

To implement this in code, we traverse the blacklist list and maintain a start and end pointer, marking the start and end of a range. When we process a blacklisted number, we add a corresponding range into our dividedRange list
Now, when we want to pick a number, we choose a random division by doing random() call on the size of dividedRange list. Then we again call random() to pick a random number from the range of picked division.

# Complexity
- Time complexity:
- O(n) one-time for precomputing the divisions.
- O(1) for picking the random number
<!-- Add your time complexity here, e.g. $$O(n)$$ -->

- Space complexity:
- O(n) for storing the divisons list
<!-- Add your space complexity here, e.g. $$O(n)$$ -->

# Code
```java []
class Solution {

    List <int[]> dividedRange;
    int numberOfDivisions = 0;
    Random rand;
    public Solution(int n, int[] arr) {
        Arrays.sort(arr);
        rand = new Random();
        dividedRange = new ArrayList <>();
        int start = 0, end = 0;
        for (int i = 0; i < arr.length; i++) {
            end = arr[i] - 1;
            if (start > end) {
                start = arr[i] + 1;
                continue;
            }
            dividedRange.add(new int[]{start, end});
            start = arr[i] + 1;
        }
        if (start < n) {
            dividedRange.add(new int[]{start, n-1});
        } 
        numberOfDivisions = dividedRange.size();
    }
    
    public int pick() {
        int pickedDivision = rand.nextInt(numberOfDivisions);
        int start = dividedRange.get(pickedDivision)[0];
        int end = dividedRange.get(pickedDivision)[1];
        return rand.nextInt(end - start + 1) + start;
    }
}

/**
 * Your Solution object will be instantiated and called as such:
 * Solution obj = new Solution(n, blacklist);
 * int param_1 = obj.pick();
 */
```
['Java']