Generate 0 and 1 with 25% and 75% probability
Given a function rand50() that returns 0 or 1 with equal probability, write a function that returns 1 with 75% probability and 0 with 25% probability using rand50() only. Minimize the number of calls to the rand50() method. Also, the use of any other library function and floating-point arithmetic are not allowed.
The idea is to use Bitwise OR. A bitwise OR takes two bits and returns 0 if both bits are 0, while otherwise, the result is 1. So it has 75% probability that it will return 1.
Below is the implementation of the above idea :
C++
// Program to print 1 with 75% probability and 0 // with 25% probability #include <iostream> using namespace std; // Random Function to that returns 0 or 1 with // equal probability int rand50() { // rand() function will generate odd or even // number with equal probability. If rand() // generates odd number, the function will // return 1 else it will return 0. return rand () & 1; } // Random Function to that returns 1 with 75% // probability and 0 with 25% probability using // Bitwise OR bool rand75() { return rand50() | rand50(); } // Driver code to test above functions int main() { // Initialize random number generator srand ( time (NULL)); for ( int i = 0; i < 50; i++) cout << rand75(); return 0; } |
Java
// Java program to print 1 with 75% probability and 0 // with 25% probability class GFG { // Random Function to that returns 0 or 1 with // equal probability static int rand50() { // rand() function will generate odd or even // number with equal probability. If rand() // generates odd number, the function will // return 1 else it will return 0. return ( int ) ( 10 * Math.random()) & 1 ; } // Random Function to that returns 1 with 75% // probability and 0 with 25% probability using // Bitwise OR static int rand75() { return rand50() | rand50(); } // Driver code public static void main(String[] args) { // Initialize random number generator //srand(time(null)); for ( int i = 0 ; i < 50 ; i++) { System.out.print(rand75()); } } } // This code is contributed by 29AjayKumar |
Python3
# Program to print 1 with 75% probability and 0 # with 25% probability from random import randrange # Random Function to that returns 0 or 1 with # equal probability def rand50(): # The randrange function will generate integer # between the half closed interval at end # Here by passing parameter as 0,2 # the function will generate integer between 0 and 1 return ( int )(randrange( 0 , 2 )) & 1 # Random Function to that returns 1 with 75% # probability and 0 with 25% probability using # Bitwise OR def rand75(): return rand50() | rand50() # Driver code to test above functions for i in range ( 0 , 50 ): print (rand75(), end = "") # This code is contributed by meetgor. |
C#
// C# program to print 1 with 75% probability and 0 // with 25% probability using System; public class GFG { // Instantiate random number generator static Random rand = new Random(); // Random Function to that returns 0 or 1 with // equal probability static int rand50() { // rand() function will generate 1 or 0 // with equal probability return rand.Next(0, 2); } // Random Function to that returns 1 with 75% // probability and 0 with 25% probability using // Bitwise OR static int rand75() { return rand50() | rand50(); } public static void Main( string [] args) { for ( int i = 0; i < 50; i++) { Console.Write(rand75()); } } } //this code is contributed by phasing17 |
PHP
<?php // Program to print 1 with 75% probability // and 0 with 25% probability // Random Function to that returns 0 or // 1 with equal probability function rand50() { // rand() function will generate // odd or even number with equal // probability. If rand() generates // odd number, the function will // return 1 else it will return 0. return rand() & 1; } // Random Function to that returns // 1 with 75% probability and 0 // with 25% probability using // Bitwise OR function rand75() { return rand50() | rand50(); } // Driver Code // Initialize random // number generator srand(time(NULL)); for ( $i = 0; $i < 50; $i ++) echo rand75(); // This code is contributed m_kit ?> |
Javascript
<script> // Program to print 1 with 75% probability and 0 // with 25% probability // Random Function to that returns 0 or 1 with // equal probability function rand50() { // rand() function will generate odd or even // number with equal probability. If rand() // generates odd number, the function will // return 1 else it will return 0. return Math.floor(Math.random() * 10) & 1; } // Random Function to that returns 1 with 75% // probability and 0 with 25% probability using // Bitwise OR function rand75() { return rand50() | rand50(); } // Driver code to test above functions // Initialize random number generator for (let i = 0; i < 50; i++) document.write(rand75()); // This code is contributed by gfgking </script> |
11101010110101011010000101011110100010111110101111
Time Complexity: O(1)
Auxiliary Space: O(1)
On similar lines, we can also use Bitwise AND. Since it returns 0 with 75% probability, we have to invert the result.
// Random Function to that returns 1 with 75% // probability and 0 with 25% probability using // Bitwise AND bool rand75() { return !(rand50() & rand50()); }
Below is the implementation of the above idea :
C++
#include <iostream> using namespace std; // Random Function to that returns 0 or 1 with // equal probability int rand50() { // rand() function will generate odd or even // number with equal probability. If rand() // generates odd number, the function will // return 1 else it will return 0. return rand () & 1; } // Random Function to that returns 1 with 75% // probability and 0 with 25% probability using // Bitwise AND bool rand75() { return !(rand50() & rand50()); } // Driver code to test above functions int main() { // Initialize random number generator srand ( time (NULL)); for ( int i = 0; i < 50; i++) cout << rand75(); return 0; } |
Java
class GFG { // Random Function to that returns 0 or 1 with // equal probability static int rand50() { // rand() function will generate odd or even // number with equal probability. If rand() // generates odd number, the function will // return 1 else it will return 0. return ( int ) ( 10 * Math.random()) & 1 ; } // Random Function to that returns 1 with 75% // probability and 0 with 25% probability using // Bitwise AND static int rand75() { return (rand50() & rand50())^ 1 ; } // Driver code public static void main(String[] args) { // Initialize random number generator //srand(time(null)); for ( int i = 0 ; i < 50 ; i++) { System.out.print(rand75()); } } } |
Python3
from random import randrange # Random Function to that returns 0 or 1 with # equal probability def rand50(): return (( int )(randrange( 0 , 2 )) & 1 ) def rand75(): return (rand50() & rand50())^ 1 for i in range ( 0 , 50 ): print (rand75(), end = "") |
C#
// C# program to implement the approach using System; class GFG { // Random Function to that returns 0 or 1 with // equal probability static int rand50() { // Instantiate random number generator using // system-supplied value as seed. var rand = new Random(); // rand() function will generate 0 or 1 // number with equal probability. return rand.Next(0, 2); } // Random Function to that returns 1 with 75% // probability and 0 with 25% probability using // Bitwise AND static int rand75() { return (rand50() & rand50()) ^ 1; } // Driver code public static void Main( string [] args) { // Initialize random number generator // srand(time(null)); for ( int i = 0; i < 50; i++) { Console.Write(rand75()); } } } // This code is contributed by phasing17 |
Javascript
// JavaScript program to implement the approach // Random Function to that returns 0 or 1 with // equal probability function rand50() { return (Math.floor(Math.random() * 2) & 1); } function rand75() { return (rand50() & rand50())^1; } for ( var i = 0; i < 50; i++) process.stdout.write(rand75().toString()); //This code is contributed by phasing17 |
11111111000111101111110011111110011110111111010111
We can replace Bitwise OR and Bitwise AND operators with OR and AND operators as well –
// Random Function to that returns 1 with 75% // probability and 0 with 25% probability using // OR or AND operator int rand75() { return !(rand50() && rand50()); // return rand50() || rand50() }
We can also achieve the result using the left shift operator and Bitwise XOR –
C++
// Program to print 1 with 75% probability and 0 // with 25% probability #include <iostream> using namespace std; // Random Function to that returns 0 or 1 with // equal probability int rand50() { // rand() function will generate odd or even // number with equal probability. If rand() // generates odd number, the function will // return 1 else it will return 0. return rand () & 1; } // Random Function to that returns 1 with 75% // probability and 0 with 25% probability using // left shift and Bitwise XOR int rand75() { // x is one of {0, 1} int x = rand50(); x = x << 1; // x is now one of {00, 10} x = x ^ rand50(); // x is now one of {00, 01, 10, 11} return (x > 0) ? 1 : 0; } // Driver code to test above functions int main() { // Initialize random number generator srand ( time (NULL)); for ( int i = 0; i < 50; i++) cout << rand75(); return 0; } |
Java
// Java program to print 1 with 75% probability and 0 // with 25% probability class GFG { // Random Function to that returns 0 or 1 with // equal probability static int rand50() { // rand() function will generate odd or even // number with equal probability. If rand() // generates odd number, the function will // return 1 else it will return 0. return ( int ) ( 10 * Math.random()) & 1 ; } // Random Function to that returns 1 with 75% // probability and 0 with 25% probability using // left shift and Bitwise XOR static int rand75() { // x is one of {0, 1} int x = rand50(); x = x << 1 ; // x is now one of {00, 10} x = x ^ rand50(); // x is now one of {00, 01, 10, 11} return (x > 0 ) ? 1 : 0 ; } // Driver code public static void main(String[] args) { for ( int i = 0 ; i < 50 ; i++) System.out.print(rand75()); } } // This code is contributed by 29AjayKumar |
Python3
# Program to print 1 with 75% probability and 0 # with 25% probability from random import randrange # Random Function to that returns 0 or 1 with # equal probability def rand50(): # rand range function generates a integer between # the provided ranges which is half closed interval # It will generate integer 0 or 1 if passed 0,2 as parameter return ( int )(randrange( 0 , 2 )) & 1 # Random Function to that returns 1 with 75% # probability and 0 with 25% probability using # left shift and Bitwise XOR def rand75(): # x is one of {0, 1} x = rand50() x = x << 1 # x is now one of {00, 10} x = x ^ rand50() # x is now one of {00, 01, 10, 11} return 1 if (x > 0 ) else 0 # Driver code to test above functions for i in range ( 0 , 50 ): print (rand75(), end = "") # This code is contributed by meetgor. |
C#
// C# program to print 1 with 75% probability and 0 // with 25% probability using System; public class GFG { // Random Function to that returns 0 or 1 with // equal probability static Random rnd = new Random(); static int rand50() { // Next(2) will generate 0 or 1 with equal probability return rnd.Next(2); } // Random Function to that returns 1 with 75% // probability and 0 with 25% probability using // left shift and Bitwise XOR static int rand75() { // x is one of {0, 1} int x = rand50(); x = x << 1; // x is now one of {00, 10} x = x ^ rand50(); // x is now one of {00, 01, 10, 11} return (x > 0) ? 1 : 0; } static public void Main (){ for ( int i = 0; i < 50; i++) Console.Write(rand75()); } } // This code is contributed by shruti456rawal |
PHP
<?php // Program to print 1 with // 75% probability and 0 // with 25% probability // Random Function to that // returns 0 or 1 with // equal probability function rand50() { // rand() function will // generate odd or even // number with equal // probability. If rand() // generates odd number, // the function will return // 1 else it will return 0. return rand() & 1; } // Random Function to that // returns 1 with 75% // probability and 0 with // 25% probability using // left shift and Bitwise XOR function rand75() { // x is one of {0, 1} $x = rand50(); $x = $x << 1; // x is now one // of {00, 10} $x = $x ^ rand50(); // x is now one of // {00, 01, 10, 11} return ( $x > 0) ? 1 : 0; } // Driver code // Initialize random // number generator srand(time(NULL)); for ( $i = 0; $i < 50; $i ++) echo rand75(); // This code is contributed // by ajit ?> |
Javascript
<script> // Javascript program to print 1 with 75% probability and 0 // with 25% probability // Random Function to that returns 0 or 1 with // equal probability function rand50() { // rand() function will generate odd or even // number with equal probability. If rand() // generates odd number, the function will // return 1 else it will return 0. return Math.floor((10 * Math.random())) & 1; } // Random Function to that returns 1 with 75% // probability and 0 with 25% probability using // Bitwise OR function rand75() { // x is one of {0, 1} let x = rand50(); x = x << 1; // x is now one of {00, 10} x = x ^ rand50(); // x is now one of {00, 01, 10, 11} return (x > 0) ? 1 : 0; } // Driver code for (let i = 0; i < 50; i++) { document.write(rand75()); } // This code is contributed by rag2127 </script> |
10110100111011011110111100101111110111100001111111
Time Complexity: O(1)
Auxiliary Space: O(1)
Please note above solutions will produce different results every time we run them.
Contact Us