Why can't I factor out the random number? (C++)


  • 0
    M

    In the implementation below, there are two options: (Look for "BETWEEN HERE" "AND HERE" in the code.)

    OPTION 1: Use a new randomly generated number as the basis for evaluating the probability.
    OPTION 2: Use a single randomly generated number as the basis for evaluating the probability.

    Option 1 works and option 2 doesn't. The distinction seems arbitrary to me. Can anyone shed light on why OPTION 2 is wrong?

    class Solution {
    
    private:
        ListNode* head;
        
    public:
    
        Solution(ListNode* head) {
            this->head = head;        
        }
        
        /** Returns a random node's value. */
        int getRandom() {
            
            // In the trivial case, with only one item.
            int returnedValue = head->val;
            ListNode* current = head->next;
            int randomNumber = rand();
            
            // For the non-trivial cases:
            int i = 2;
            while (current != NULL)
            {
                // --- BETWEEN HERE ---
                if (rand() % (i++) == 0)  // OPTION 1
                //if (randomNumber % (i++) == 0)  // OPTION 2
                // --- AND HERE ---
                {
                    returnedValue = current->val;
                }
                current = current->next;
            }
            return returnedValue; 
        }
    };
    

Log in to reply
 

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