C++ 39ms using a simple probability observation


  • 0
    A

    The basic observation that equal probability can be achieved by constantly doubling the modulus (i.e potential sample size) because by doing so you are always creating 50% increases in probability and sharing that across. For example:

    N -> N+1 -> N+2 -> N+3

    You start with rand() % 2

    Which means that N and N+1 have each 50% chance of being picked, next you move to N+2 and you double the modulus to 4. By doubling the modulus you make the probability of picking the next element half of what it used to be, but you increase the total number of elements by two, basically evening the probability on either side. The key point here is the second time you 'roll the dice' the first 50% has 0 probability of being selected making its total probability at the second step half.

    1:
    50%  50%
    N    N+1
    2:
    50%  50%
    0%   0%   |  25%  25%  25%  25% 
    N    N+1  |  N+2  N+3  N+4  N+5
    

    The second observation is that once we hit the end of the linked list we stop doubling the steps and just continue to loop with the current modulus. Producing a close to equal probability for all candidates.

    class Solution {
        ListNode* head;
        ListNode* current;
        int width;
        bool looped;
        
        void moveforward(int count) {
            while(count--) {
                if (current->next != NULL) {
                   current = current->next;
                } else {
                    current = head;
                    looped = true;
                }   
            }
        }
    public:
        Solution(ListNode* d) {
            head = current = d;
            width = 2;
            looped = false;
            srand(time(NULL));
        }
    
        int getRandom() {
            int r = rand() % width;
            
            moveforward(r);
            int val = current->val;
            moveforward(width-r);
            if (!looped)
               width += width;
            
            return val;
        }
    };
    

Log in to reply
 

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