Advertisement
imashutosh51

Select a random element from the stream of elements

Nov 8th, 2022 (edited)
58
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.09 KB | None | 0 0
  1. //This is GFG code,You won't get any practice for this problem.
  2. /*
  3. Logic is simple,We are passing the stream numbers into selectrandom function,
  4. storing the count of numbers into a variable count and predicting a number from
  5. 0 to count-1.If predicted number is count-1 then update the result or probable number
  6. else keep resultant number same.
  7. */
  8.  
  9. #include <bits/stdc++.h>
  10. #include <time.h>
  11. using namespace std;
  12. int selectRandom(int x){
  13.     static int res; // The resultant random number
  14.     static int count = 0; // Count of numbers visited so far in stream
  15.     count++; // increment count of numbers seen so far
  16.     // If this is the first element from stream, return it
  17.     if (count == 1)
  18.         res = x;
  19.     else{
  20.         int i = rand() % count;   // Generate a random number from 0 to count - 1
  21.         if (i == count - 1) // Replace the prev random number with new number with 1/count probability
  22.             res = x;
  23.     }
  24.     return res;
  25. }
  26. int main(){
  27.     int stream[] = {1, 2, 3, 4};
  28.     int n = sizeof(stream) / sizeof(stream[0]);
  29.     srand(time(NULL));
  30.     for (int i = 0; i < n; ++i)
  31.         cout<<selectRandom(stream[i]) << endl;
  32.     return 0;
  33. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement