Category: Math

rand7 given rand5

admin / / Math

© Parineeth M R

Question 51. Suppose you are given a random number generator that generates numbers uniformly in the range 1 to 5. How will you generate numbers uniformly in the range 1 to 7?

Let’s us say that we are provided with the rand5() function that generates values uniformly from 1 to 5. We can generate values uniformly from 0 to 4 by subtracting 1 from the result of rand5(). Now using rand5() we can uniformly generate numbers in the range 0 to 24 using the following formula

(rand5() – 1) + 5 * (rand5() – 1)

Now to generate numbers uniformly from 1 to 7, we use rejection sampling. If the above formula generates a random number in the range 0 to 20, we accept the number. If the formula generates a number in the range 21 to 24, then we reject the number and re-try the formula till we get a number in the range 0 to 20. We then find the remainder when the number in range 0 to 20 is divided with 7. The remainder will be uniformly distributed in the range 0 to 6. We then add 1 to the remainder to get the result which will be uniformly distributed in the range 1-7.

The rejection sampling in this case can be visualized with a 5 * 5 grid, where in if we throw a dart and the dart randomly lands on a cell, the number in the grid is accepted for some cells and rejected for others.

C/C++


int rand7() {
	int result;
	while(1) {
		result = (rand5() - 1) + (5 * (rand5() - 1) );
		if (result <= 20)
			break;
	}
	result = 1 + (result % 7);
	return result;
}

Java


public static int rand7() {
	int result;
	while(true) {
		result = (rand5() - 1) + (5 * (rand5() - 1));
		if (result <= 20)
			break;
	}
	result = 1 + (result % 7);
	return result;
}

Python


def rand7() :
	while(True) :
		result = (rand5() - 1) + (5 * (rand5() - 1))
		if (result <= 20):
			break

	result = 1 + (result % 7)
	return result

Generate all prime numbers up to N

admin / / Math

© Parineeth M R

Question 50. Generate all the prime numbers that are less than or equal to N

To generate all prime numbers <= N, we make use of the sieve of Eratosthenes where we do the following 1. We generate the numbers from 2 to N and for each number X, we mark all multiples of X up to N to indicate that these multiples can’t be primes 2. If a number is not a multiple of any of the numbers preceding it, then it is a prime

We skip 0 and 1 as they are not considered to be prime. 2 is the first prime number. Then all multiples of 2 up to N are marked to indicate that these multiples can’t be primes. The next number is 3. Since 3 is not a multiple of any number before it (note that we have skipped 1 and so we ignore the fact that 3 is a multiple of 1), 3 is a prime. We then mark all multiples of 3. The next number is 4. Since 4 has been marked to be a multiple, it can’t be prime. We then mark all the multiples of 4 and this process continues till N

C/C++


/*sets the bit at position pos to 1 in the bitmap*/
void set_bit(unsigned char bitmap[], int pos)
{
	int byte_pos = pos / 8;
	int bit_pos = pos % 8;

	bitmap[byte_pos] |= 1u << bit_pos;	
}

/*Returns the bit at position pos in the bitmap*/
int get_bit(unsigned char bitmap[], int pos)
{
	int byte_pos = pos / 8;
	int bit_pos = pos % 8;

	if (bitmap[byte_pos] & (1u << bit_pos) )
		return 1;
	else 
		return 0;
} 

 
/*
n: Upto what number the primes should be generated
*/
void generate_primes(int n)
{
	int i, j;
	int total_num_bytes = 1 + (n / 8);

	/*is_multiple_bmp will be initialized with zeroes since we have not yet 
	identified the multiples*/
	unsigned char *is_multiple_bmp = (unsigned char*) calloc(1, 
								total_num_bytes);

	/*We don't consider 0 and 1 as prime. Start from 2*/
	for (i = 2; i <= n; ++i) {
		if (get_bit(is_multiple_bmp, i)) 
			continue; /*i is a multiple, so it can't be prime*/
		
		printf("%d is prime\n", i);

		/*Mark all multiples of i (2i, 3i, 4i, etc) starting from 2*i */
		for (j = 2*i; j <= n; j += i) {
			set_bit(is_multiple_bmp, j);
		} 
	}

	free(is_multiple_bmp);
}

Java


/*
n: Upto what number the primes should be generated
*/
public static void generatePrimes(int n) {
	/*isMultiple will be initialized with false since we have not yet 
	identified the multiples*/
	boolean[] isMultiple = new boolean[n+1];

	/*We don't consider 0 and 1 as prime. Start from 2*/
	for (int i = 2; i <= n; ++i) {
		if (isMultiple[i]) 
			continue; /*i is a multiple, so it can't be prime*/
	
		System.out.println(i + " is prime ");

		/*Mark all multiples of i (2i, 3i, 4i, etc) starting from 2i */
		for (int j = 2*i; j <= n; j += i) {
			isMultiple[j] = true;
		} 
	}

}

Python


#n: Upto what number the primes should be generated
def generate_primes(n) :
	#is_multiple will be initialized with False since we have not yet 
	#identified the multiples
	is_multiple = [False] * (n+1)

	#We don't consider 0 and 1 as prime. Start from 2
	for  i in range(2, n+1):
		if (is_multiple[i]) :
			continue #i is a multiple, so it can't be prime
	
		print('{} is prime '.format(i) )

		#Mark all multiples of i (2i, 3i, 4i, etc) starting from 2i 
		for  j in range(2*i, n+1, i):
			is_multiple[j] = True

Find the missing integer

admin / / Math

© Parineeth M R

Question 49. An unsorted array contains all integers from 1 to N except one integer. All the elements in the array are unique. Find the missing integer in O(n) time and O(1) space. For instance in the array {5, 1, 3, 2}, the missing element is 4

All integers from 1 to N are present in the array except one integer. To find the missing integer we do the following

1. Calculate the expected_sum of integers from 1 to N. We know that the sum of integers from 1 to N is given by the formula N * (N+1) / 2

2. Calculate the total_sum of the N-1 elements in the array.

3. The difference between expected_sum and the total_sum will give the missing element.

So if N = 5, and array is {5, 1, 3, 2}, then expected sum = 5 (5 + 1) / 2 = 15. The total sum of elements in the array = 5 + 1 + 3 + 2 = 11. So missing number = 15 – 11 = 4.

C/C++


/*
a: array of unique numbers. A number can have a value between 1 to n.
n: maximum value that can be stored in array. array has n-1 elements
Return value: missing element in the array
*/
int find_missing(int a[], int n)
{
	int i, total_sum, expected_sum;
	int missing_num;

	/*Since 1 element is missing, there are only n-1 elements in the array*/
	total_sum = 0;
	for (i = 0; i < n - 1; ++i) { 
		total_sum += a[i];
	}

	expected_sum = n * (n+1) / 2;

	missing_num = expected_sum - total_sum;

	return missing_num;
}

Java


/*
a: array of unique numbers. A number can have a value between 1 to n.
n: maximum value that can be stored in array. array has n-1 elements
Return value: missing element in the array
*/
public static int findMissing(int[] a, int n) {
	/*Since 1 element is missing, there are only n-1 elements in the array*/
	int totalSum = 0;
	for (int i = 0; i < n - 1; ++i) { 
		totalSum += a[i];
	}

	int expectedSum = n * (n+1) / 2;

	int missingNum = expectedSum - totalSum;

	return missingNum;
}

Python


#a: list of unique numbers. A number can have a value between 1 to n
#n: maximum value that can be stored in the list. list has n-1 elements
#Return value: missing element in the list
def find_missing(a, n) :
	#Since 1 element is missing, there are only n-1 elements in the list
	total_sum = 0
	for  i in range(0, n - 1):
		total_sum += a[i]
	
	expected_sum = n * (n+1) // 2

	missing_num = expected_sum - total_sum
	return missing_num

Swap two variables without using temporary variable

admin / / Math

© Parineeth M R

Question 48. Swap two variables without using a temporary variable

There are two ways to solve this problem. The first uses XOR and the second uses addition and subtraction. The XOR technique can be used for swapping any two variables whereas the addition and subtraction technique can only be used for numbers. The two techniques are described below

Greatest Common Divisor

admin / / Math

© Parineeth M R

Question 47. Find the Greatest Common Divisor of two numbers

The Greatest Common Divisor (GCD) of two numbers a and b is the largest number that divides a and b without leaving a remainder. For instance, the GCD of 12 and 20 is 4. It is also called Greatest Common Factor, Highest Common Factor, etc. To find the GCD we use Euclid’s algorithm which is as follows:
gcd(a, 0) = a

gcd(a, b) = gcd(b, a mod b)

So, suppose we have to calculate gcd(12, 20) then we get

gcd(12, 20) = gcd(20, 12 mod 20) = gcd(20, 12)

gcd(20, 12) = gcd(12, 20 mod 12) = gcd(12, 8)

gcd(12, 8) = gcd(8, 12 mod 8) = gcd(8, 4)

gcd(8, 4) = gcd(4, 8 mod 4) = gcd(4, 0) = 4

C/C++


/*
a, b: Two integers. a may be greater than, equal to or less than b
Return value: Greatest common divisor
*/
int gcd(int a, int b)
{
	if (b == 0)
		return a;

	/*Find the GCD of b and the remainder of a/b*/
	return gcd(b, a%b);
}

Java


/*
a, b: Two integers. a may be greater than, equal to or less than b
Return value: Greatest common divisor
*/
public static int gcd(int a, int b) {
	if (b == 0)
		return a;

	/*Find the GCD of b and the remainder of a/b*/
	return gcd(b, a % b);
}

Python


#a, b: Two integers. a may be greater than, equal to or less than b
#Return value: Greatest common divisor
def gcd(a, b) :
	if (b == 0):
		return a

	#Find the GCD of b and the remainder of a/b
	return gcd(b, a % b)