# 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:

{% code lineNumbers="true" %}

```c
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);
}
```

{% endcode %}

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`.

{% code lineNumbers="true" %}

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

{% endcode %}

### 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.**

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

The **least common multiple (lcm)**

```c
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**

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

{% hint style="info" %}
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.
{% endhint %}

### 4. Almost

> This problem is a variant of last year past PE1's [/pages/oHoyQF5Y7ZvqfpGfOMNu#id-4.-unique](https://wenbo-notes.gitbook.io/cs1010-notes/past-year-exam/midterm-pe/pages/oHoyQF5Y7ZvqfpGfOMNu#id-4.-unique "mention"). You can easily modify the function there to get the number of all prime factors of a number.

Also nothing much to talk about. [/pages/oHoyQF5Y7ZvqfpGfOMNu#id-4.-unique](https://wenbo-notes.gitbook.io/cs1010-notes/past-year-exam/midterm-pe/pages/oHoyQF5Y7ZvqfpGfOMNu#id-4.-unique "mention") 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:

{% code lineNumbers="true" %}

```c
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);
}
```

{% endcode %}

{% hint style="info" %}
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.
{% endhint %}

## Tips

1. Using a negative number modulo a positive number, the result is a negative number. i.e. $$-1234\~%\~10=-4$$. Review the [lecture](https://nus-cs1010.github.io/2425-s1/notes/07-arithmetic-ops.html?h=modulo#the-operator) on how modulo works. In C, we call the $$%$$ **remainder** operator instead of **module** operator!!!


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://wenbo-notes.gitbook.io/cs1010-notes/past-year-exam/midterm-pe/pe1-ay21-22.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.