C++ Tutorial Quiz - Math & Probability - 2020

There are various methods to determine whether a given number n is prime.

In the code below, we're using the most basic routine, trial division. Note that we do not need to try up to n, and sqrt(n) is enough. That's because if n is a composite number, then n=a*b. If a > sqrt(n), then b < sqrt(n), so we only need to try up to sqrt(n).

The code calculate the sum of prime numbers up to 1 million. (ans = 37,550,402,023)

#include <iostream>
#include <cmath>
using namespace std;

bool isPrime(int num);

int main()
{
   long long sum = 2; 

   for (int i = 3; i < 1000000; i += 2)   
      if (isPrime(i)) sum += i;

   cout << sum << endl;
   return 0;
}

bool isPrime(int num)
{
   if (!(num % 2))
      return false;
   for (int i = 3; i <= sqrt((double)num); i += 2) 
      if (!(num % i))
         return false;
   return true;
}

In the code below, we start with a list of numbers up to MAX_NUM. We cross off all numbers divisible by 2, then cross off more numbers divisible by the next prime number, 3, 5, 7, 11, etc. Then, in the end, we get the list of primes.

#include <iostream>
using namespace std;

#define MAX_NUM 100

void sieve(int primes[]) 
{ 
	// loop through all elements in array
	for (int p = 2; p < MAX_NUM; p++) { 
		// skip a number already crossed off
		if(primes[p] == -1) continue;
		int n = 2;
		int multiple = p * n; 
		// cross off all multiples of prime as non primes 
		while(multiple < MAX_NUM) { 
			primes[multiple] = -1; 
			n++; 
			multiple = p*n; 
		} 
		// it is a prime
		if(primes[p] == 0) primes[p] = 1;  
	} 
} 
int main()
{
	int primes[MAX_NUM] = {0}; 
	
	// get primes
	sieve(primes);
	
	// print out primes
	for(int i = 0; i < MAX_NUM; i++) {
		if(primes[i] == 1) cout << i << " ";
	}

	return 0;
}

#include <iostream>
using namespace std;

int negate(int x) 
{ 
	int ret = 0;
	int one = (x > 0) ? -1 : 1;
	while(x != 0) {
		ret = ret + one;
		x = x + one;
	}
	return ret;
} 

int main()
{
	cout << "10 + negate(5) = " << 10 + negate(5) << endl;
	cout << "10 + negate(-5) = " << 10 + negate(-5) << endl;
	return 0;
}

Output:

10 + negate(5) = 5
10 + negate(-5) = 15

Convert a*b to b times of additions of a, a+a+...+a+a. If b is negative, we can negate the result. Simply put, what we're actually doing is:
multiply(a,b) => abs(b) * a * (+/-1) : -1 if b < 0.

#include <iostream>
using namespace std;

int negate(int);

// adding a+a+..+ a : b times
int multiply(int a, int b) 
{ 
	int ret = 0;
	int btimes = abs(b);
	while(btimes--) ret = ret + a;	
	if (b < 0) ret = negate(ret);
	return ret;
} 

// if b < 0, negate the return value from multiply
int negate(int x) 
{ 
	int ret = 0;
	int one = (x > 0) ? -1 : 1;
	while(x != 0) {
		ret = ret + one;
		x = x + one;
	}
	return ret;
} 

int main()
{
	cout << "multiply(10, 5) = " << multiply(10, 5) << endl;
	cout << "multiply(10, -5) = " << multiply(10, -5) << endl;
	return 0;
}

Output:

multiply(10, 5) = 50
multiply(10, -5) = -50

For a/b=x, all we need to do is to check if x*b equals to a. In other words, repeat adding b to itself x times.

#include 
#include 

using namespace std;

int negate(int);

// adding a+a+..+ a : b times
int division(int a, int b) 
{ 
	assert(b != 0);
	int x = 0;
	int abs_a = abs(a);
	int abs_b = abs(b);
	int sum = 0;
	while(sum<= abs_a) {
		sum += abs_b;
		x++;
	}

	if(a < 0 && b > 0 || a > 0 && b < 0) return negate(x);

	return x;
} 

int negate(int x) 
{ 
	int ret = 0;
	int one = (x > 0) ? -1 : 1;
	while(x != 0) {
		ret = ret + one;
		x = x + one;
	}
	return ret;
} 

int main()
{
	cout << "division(10, 5) = " << division(10, 5) << endl;
	cout << "division(10, -5) = " << division(10, -5) << endl;
	return 0;
}

Output:

division(10, 5) = 3
division(10, -5) = -3

Coin Change is the problem of finding the number of ways of making changes for a particular amount of cents, $N$, using a given set of $m$ denominations such that $D = \{D_1, D_2, ..., D_m\}$. It is a general case of Integer Partition, and can be solved with dynamic programming.

Using denominations of
$\$100, \$50, \$20, \$10, \$5, \$1, \$0.25(quarter), \$360.10(dime), \$0.05(nickel) \text{ and }\$0.01(penny).$
Find all combinations of these denominations up to $10,000$.

The code below is based on Coin Change

1. Recursive formula
   We can divide the solution in two groups:
   
   1. One group that does not include $D_m$ $$C(N, m-1)$$
   2. The other group that has at least one $D_m$ $$C(N-D_m, m)$$
   Combining the two groups: $$C(N, m) = C(N, m - 1) + C(N - D_m, m)$$
2. Base cases:
   
   1. $$C(N, m) = 1, N = 0 $$ (one solution -- we have no money, exactly one way to solve the problem - by choosing no coin change, or, more precisely, to choose coin change of 0)
   2. $$C(N, m) = 0, N < 0 $$ (no solution -- negative sum of money) (no solution -- we have money, but no change available)
   3. $$C(N, m)= 0, N >= 1, m < 0$$ (no solution -- we have money, but no change available)


3. $N$: target amount, $C$: count, $m$: # of denominations, $D_m$: denomination

#include <iostream>
using namespace std;

// unit = cents
int AMOUNT = 1000;
int D[] = {1, 5, 10, 25, 50, 100, 500, 1000, 2000, 5000, 10000};


int count(int amount, int index)
{    
    // // If amount is 0 then there is only one solution
    if (amount == 0 )
        return 1;

    // If amount is less than 0 then no solution exists
    if (amount < 0)
        return 0;

    // If there are no coins and amount is greater than 0, then no solution exist
    if(index < 0 && amount >= 1) 
	return 0;

    return count(amount, index-1) + count(amount-D[index], index);
}

int main()
{
	int sz = sizeof(D)/sizeof(int);
	cout << "# of ways = " << count(AMOUNT, sz-1) << endl;
	return 0;
}

However, it slows down significantly around AMOUNT = 5000 (= $\$50$) and we have stackoverflow. So, instead of accumulating stack frames, we have to reply on dynamic programming utilizing memoization.

#include <iostream>
using namespace std;

/* Not sure how long it will take for 10-100 million which is $100,000 - 1,000,000 */
#define AMOUNT 1000000

// unit - cent
int coin[] = {1, 5, 10, 25, 50, 100, 500, 1000, 2000, 5000, 10000};

// array for memoization
long long memo[sizeof(coin)/sizeof(coin[0])][AMOUNT+1];
 
long long sum(int amount, int dIndex)
{
        // check if it's already cached
	if(memo[dIndex][amount]!=-1)
	{
		return memo[dIndex][amount];
	}

        // base cases
	if(dIndex == 1)
	{
		memo[dIndex][amount] = (amount/coin[dIndex] + 1);
		return memo[dIndex][amount];
	}
	if(amount == 0)
	{
		memo[dIndex][amount] = 1;
		return 1;
	}

        // recursion and dynamic
	long long total = 0;
	for(int a = amount; a > 0; a-= coin[dIndex])
	{		
		total += memo[dIndex - 1][amount - a] == -1 ? 
                   sum(amount - a, dIndex - 1) : memo[dIndex - 1][amount - a];
	}
	memo[dIndex][amount] = total;
	return total;	
}

int main()
{
	int sz = sizeof(coin)/sizeof(coin[0]);
        // array for memoization, initialied with -1. 
        // If it's not -1, the algorithm uses cached value
	for(int i = 0; i < sz; i++) {
		for(int j = 0; j <= AMOUNT; j++) 
			memo[i][j] = -1;
	}
	
	cout << "# of ways = " << sum(AMOUNT, sz-1) << endl;
	return 0;
}

Output:

# of ways = 4245202027051164214

Took a while to get the number. But it's still just up to $\$10,000$ which is order of 2 less than the target, $\$1,000,000$. There must be a better way!

In this problem, we need to use minimum number of coins to make a given amount for a set of denominations.

Amount = 40 cents, and denominations are $\{1, 5, 10, 25\}$.

We need to choose the smallest of the following:

1. 1 + MinChange(39) - a penny (=1) given
2. 1 + MinChange(35) - a nickel (=5) given
3. 1 + MinChange(30) - a dime (=10) given
4. 1 + MinChange(15) - a quarter (=25) given

In other words, we have the following recursive formula:

1. Define $C[j]$ to be the minimum number of coins we need to make change for $j$ cents.
2. Denominations are given as $$D = \{d_1, d_2, ..., d_k\}.$$
3. If we knew that an optimal solution for the problem of making change for $j$ cents used a coin of denomination $d_i$, we have: $$C[j] = 1 + C[j-d_i].$$
4. Recursively define the value of an optimal solution. $$C[j] = \begin{cases} \infty & \text{if }j < 0, \\ 0 & \text{if }j = 0, \\ 1 + min_{1 \le i \le k} (C[j-d_i]) & \text{if }j \ge 1 \end{cases}$$

Here is the code:

#include <iostream>
using namespace std;

int CoinChange(int amount, int d[], int size)
{
	if(amount <= 0) return 0;
	int min_coins =(int)INT_MAX;

	for(int i = 0; i < size; i++) {
		if(d[i] <= amount) 
			min_coins = min(min_coins, CoinChange(amount-d[i], d, size) + 1);
	}
	return min_coins;
}
int main()
{
	int d[] = {1, 5, 10, 25};
	int amount = 40;
	int size = sizeof(d)/sizeof(d[0]);
	int ans = CoinChange(amount, d, size);
	cout << "Minimal # of coins = " << ans << endl;

	return 0;
}

Output is:

Minimal # of coins = 3