Get random int are not in a particular array


  • 0
    N

    You are given a method
    int getRandom(int n){
    return [0,n)
    }

    please write a special get random method returns a number not in a given array.
    int getSpecialRandom(int n, int[] array){

    }


  • 0
    M
    public class Solution {
        private static final int NOT_FOUND = -1;
        public int getSpecialRandom(int n, int[] array) {
            if (array == null || array.length == 0 || n < 0) {
                return NOT_FOUND;
            }
            byte[] bitVectorOfInts = createBitVectorOfInts(array);
            int numberOfMissingInts = getNumberOfMissingInts(n, bitVectorOfInts);
            if (numberOfMissingInts == 0) {
                return NOT_FOUND;
            }
            int randomIndex = getRandom(numberOfMissingInts); //Provided method
            return getRandomValue(randomIndex, bitVectorOfInts);
        }
        private byte[] createBitVectorOfInts(int[] array) {
            long totalSize = ((long) Integer.MAX_VALUE) + 1;
            byte[] bitVectorOfInts = new byte[(int) (totalSize / Byte.SIZE)];
            for (int number : array) {
                bitVectorOfInts[number / Byte.SIZE] |= 1 << (number % Byte.SIZE);
            }
            return bitVectorOfInts;
        }
        private int getNumberOfMissingInts(int exclusiveTop, byte[] bitInts) {
            int numberOfMissingInts = 0;
            int index = 0;
            for (int i = 0; i < bitInts.length; i++) {
                for (int j = 0; j < Byte.SIZE; j++) {
                    if (index >= exclusiveTop) {
                        return numberOfMissingInts;
                    }
                    if ((bitInts[i] & (1 << j)) == 0) {
                        numberOfMissingInts++;
                    }
                    index++;
                }
            }
            return numberOfMissingInts;
        }
        private int getRandomValue(int randomIndex, byte[] bitVectorOfInts) {
            int index = 0;
            for (int i = 0; i < bitVectorOfInts.length; i++) {
                for (int j = 0; j < Byte.SIZE; j++) {
                    int intBlock = bitVectorOfInts[i];
                    if ((intBlock & (1 << j)) == 0) {
                        if (index == randomIndex) {
                            return i * Byte.SIZE + j;
                        }
                        index++;
                    }
                }
            }
            return NOT_FOUND;
        }
    }
    

  • 0
    P

    The idea is -
    Put all the unique numbers of the array in a set. Then start from 0 (or Integer.MIN_VALUE as is the case) till just one more than the length of the array. Why array.length + 1 ? Because of Pigeonhole Principle. If array has only n elements, I need to find at maximum, n + 1 elements before I come across an element I haven't found previously in the set.

    public int getSpecialRandom(int n, int[] array){
    
    Set<Integer> set = new HashSet<Integer>();
        
        for(int i = 0; i < array.length; i++){
            set.add(array[i]);
        }
        
        for(int i = 0; i < array.length + 1; i++){
            if(!set.contains(i))
                return i;
        }
        
        return 0;
    }
    

    Please let me know how I can format the code better. This is my first time posting on this forum


  • 0
    S

    @pratik.joshi.56808 Thank you for posting a solution! However, the question implies (although worded in an unclear way) that:

    1. A random number is expected as the returned value. and thus:
    2. getRandom() should be called somewhere in your solution.

    Your code, unfortunately, does not satisfy the above requirements. It only returns "the smallest element that is not in the set", which is not a random number.

    You may want to consider an alternative solution.


  • 0
    R
    from array import array
    from random import randint
    
    def special_random(n, nums):
       bits = array.array('b', (0 for _ in range(n)))
       for value in nums:
           if value < n:
              array[value] = 1
       value = randint(0, n + 1)
       while array[value]:
          value = randinr(0, n + 1)
       return value

  • 0
    R

    @riccardo The problem of my solution is that if array contains all the lements in the target range it will get stuck in a loop; if the array contains most of the elements it would get pretty slow.

    from array import array
    from random import randint
    
    def special_random(n, nums):
       if len(nums) == n:
          return None
       nums = [num
               for num in range(n)
               if num nor in set(nums)]
       return nums[randint(0, len(nums) - 1)]

  • 0
    U

    @needCoffee I am not clear with the question. The int we random get, does it have a range? like [0, n)?


  • 0
    N

    @user913 Yes. It should be in the rang from 0(inclusive) to n(exclusive). But the getSpecialRandom should make sure the returning number is not in the given array.


  • 0
    U

    @needCoffee Thank you, now I am clear. Some other questions: is the given array fixed? are we going to use the getSpecialRandom() a lot?


  • 0
    N

    @user913 Yes. The given array is fixed. I did not get a chance to ask if "getSpecialRandom() " will be called a lot though.


  • 0
    U

    @needCoffee Thanks, now its more clear :) my first thought, is to build a hashmap, with key: [0, N - ParticularArray.length()) (ParticularArray has no duplicates?), value: all the numbers not in ParticularArray. After this it is O(1) to getSpecialRandom().

    To build the hashmap, first sort ParticularArray low to high, which is log(length)*length.

    Then build 2 pointers, A from 1~N, B from left of ParticularArray to right. which is N.


  • 0
    N

    @user913 I think that might work. It would be nice if you can show your code. Thanks.


  • 1
    U

    @needCoffee

    int getSpecialRandom(int n, int[] array){
            Arrays.sort(array);
    
            int left, right, hashIndex;
            HashMap hashMap = new HashMap();
    
            right = 0;
            hashIndex = 0;
            for(left = 0; left < n; ++left) {
    
                if (left == array[right])
                    ++right;
                else
                    hashMap.put(hashIndex++, left);
            }
    
            Random ran = new Random();
            return (int) hashMap.get(ran.nextInt(n - array.length));
        }
    

  • 0
    U

    @user913

    Oh, I forgot to check array.length >= n. If so it should return null.


  • 0

    C#

    int random = getRandom(n);
    while (!array.Contains(random))
    {
       random = getRandom(n);
    }
    
    return random;
    
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.