PE1 (AY21/22)

Problems

1. Herd

Note the $0\%$ and $100\%$ are valid vaccination rates. Nothing else. This is a "give-away" question.

2. Insert*

Using wishful thinking, to insert $d$ into $N$ at position $k$, it is the same as inserting $d$ into $N/10$ at position $k-1$, take the result, and append the last digit $(N\%10)$. So the function can be written as below:

long insert(long d, long N, long k) {
    if (k == 1) {
        return N * 10 + d;
    }
    return insert(d, N / 10, k ­- 1) * 10 + (N % 10);
}

There is one more complication, it does not work for negative numbers. But that can be easily fixed by changing the sign of the input digit d.

if (N >= 0) {
    answer = insert(d, N, k);
else {
    answer = ­insert(-d, ­N, k);
}

3. Fraction

This problem is an excellent example to test your ability to divide a problem into several "sub-problems" to solve.

See Prof Ooi Wei Tsang's comment. The idea is similar.

Some Useful functions

The greatest common divisor (gcd), which is also known as the greatest common factor.

long gcd(long a, long b)
{
    if (b == 0)
    {
    return a;
    }
    return gcd(b, a % b);
}

The least common multiple (lcm)

long lcm(long a, long b, long gcd)
{
    return a * b / gcd;
}

The iterative way to get the number of digtis of a given number

long num_digits(long num)
{
    long count = 0;
    while (num != 0)
    {
        count += 1;
        num /= 10;
    }
    return count;
}

When getting the simple fraction, you don't need to find the least common multiple (LCM) at first, you can just form the new denominator as the multiple of the two denominators (it may not be the LCM) and using fundamental numeric operations to form a new numerator. Then divide both the new denominator and the numerator by the gcd() of them. You will get the simplest version.

4. Almost

This problem is a variant of last year past PE1's 4. Unique*. You can easily modify the function there to get the number of all prime factors of a number.

Also nothing much to talk about. 4. Unique* is quite enough.

5. Stone

The tricker recursion question, I haven't solved it at first time because I ignore that I don't need to print 1 or 2 only. I can treate the path a number and right shift it!!!

In this problem, we just need to know how to form each "path" (treat it as a number). And the easiest way is to append the path at the last digit, which should be path * 10 + 1 or path * 10 + 2. The final code should be following:

void print_bridge(long k, long path) {
    if (k == 0) {
        cs1010_println_long(path);
        return;
    }
    print_bridge(k ­- 1, path * 10 + 1);
    print_bridge(k ­- 1, path * 10 + 2);
}

For recursion that involves numbers, which may be considered a variant of something else in the problem, like "path", always treat them as a whole number, this will make your life much easier.

Tips

1. Using a negative number modulo a positive number, the result is a negative number. i.e. $-1234~\%~10=-4$. Review the lecture on how modulo works. In C, we call the $\%$ remainder operator instead of module operator!!!