Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- //This is GFG code,You won't get any practice for this problem.
- /*
- Logic is simple,We are passing the stream numbers into selectrandom function,
- storing the count of numbers into a variable count and predicting a number from
- 0 to count-1.If predicted number is count-1 then update the result or probable number
- else keep resultant number same.
- */
- #include <bits/stdc++.h>
- #include <time.h>
- using namespace std;
- int selectRandom(int x){
- static int res; // The resultant random number
- static int count = 0; // Count of numbers visited so far in stream
- count++; // increment count of numbers seen so far
- // If this is the first element from stream, return it
- if (count == 1)
- res = x;
- else{
- int i = rand() % count; // Generate a random number from 0 to count - 1
- if (i == count - 1) // Replace the prev random number with new number with 1/count probability
- res = x;
- }
- return res;
- }
- int main(){
- int stream[] = {1, 2, 3, 4};
- int n = sizeof(stream) / sizeof(stream[0]);
- srand(time(NULL));
- for (int i = 0; i < n; ++i)
- cout<<selectRandom(stream[i]) << endl;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement