# PE1 (AY20/21)

## Problems

### 1. Error\*

#### Ignore $$k$$ most significant digits in num $$n$$

Basic idea is to use num $$n$$ to modular $$10^k$$. And here is the code for implementation:

{% code lineNumbers="true" %}

```c
long ignore_first_k_digit(long n, long k)
{
    long power = 1;
    for (int i = 0; i < k; i += 1) {
        power *= 10;
    }
    return n % power;
}
```

{% endcode %}

For example, if we input `ignore_last_k_digit(1234, 2)`, the power will be raised to 100 and we will get `1234 % 100 = 34`.

#### Ignore the $$k$$ least significant digits in num

The basic idea here is to use **integer division**, so we use $$n / 10^k \cdot 10^k$$.

{% code lineNumbers="true" %}

```c
long ignore_last_k_digit(long n, long k)
{
    long power = 1;
    for (int i = 0; i < k; i += 1) {
        power *= 10;
    }
    return n / power * power;
}
```

{% endcode %}

For example, if we input `ignore_first_k_digit(1234, 2)`, then power will be raised to `100`. So, we will return `1234 / 100 * 100`, which is `12 * 100 = 1200`.

### 2. Twilight

This is a "give-away" question.

### 3. Reverse\*

#### Naive idea

The basic and and naive idea for this question is:

1. take the last digit of $$n$$
2. reverse the rest of the digits of $$n$$
3. put the last digit of $$n$$ "in front"

And the trickest part lies in **how to put the last digit of** $$n$$ **in front?** The basic idea is that if we know the digit position/ the number of digits (Let's say it's $$k$$), we can quickly put the digit in front by timing it with $$10^k$$. So now, we need to write another recursive function that can help us calculate the amount of power we should time it with the last digit of $$n$$.

{% code lineNumbers="true" %}

```c
long power(long num)
{
    if (num < 10)
    {
        return 1;
    }
    return 10 * power(num / 10);
}
```

{% endcode %}

This is known as **the recursive way to calculate the weight we need to put a digit at the front of the num** $$n$$ **in decimal.**

#### A more elegant solution

Assume that we already know how to reverse a shorter number given that part of the number is already reversed (Suppose we divide 123456 into 1234 and 65):

1. We can get a shorter number by removing the last digit (1234 -> 123)
2. We can extend the partial solution by appending the last digit (65 -> 654)
3. We just return the value returned by the recursive call!

Code Implementation:

{% code lineNumbers="true" %}

```c
long reverse(long remaining, long reversed)
{
    if (remaining == 0) {
        return reversed;
    }
    return reverse(remaining / 10, reversed * 10 + (remaining % 10));
}
```

{% endcode %}

The base case means that we there is no digit remaining, we have already reversed all the digit! And the elegant idea here is we shift the reversed digit right by one "bit", that saves us from the trouble of calculating the power! Awesome!

### 4. Unique\*

> A pretty awesome question to thinking about!!!

#### Setup (Preparation)

First thing first, we can use a `while` loop inside a `for` loop to find the how many times a factor has repeated. The implementation is below:

{% code lineNumbers="true" %}

```c
long curr = n;
for (long factor = 2; factor < n; factor += 1) {
    if (is_prime(factor)) {
        long count = 0;
        while (curr % factor == 0) {
            curr = curr / factor;
            count += 1;
        }
        if (count != 0) {
            print(factor, count);
        }
    }
}
```

{% endcode %}

Rememebr to define another variable `curr` to store the num `n`. And remember to initialize the `count` to 0 every time you start with a different factor.

#### First Optimization

Then let's think about how to improve the efficieny, first we can check the factor tilll `sqrt(n)` instead of `n`.

<details>

<summary>Proof (Why can we change the loop condition to <code>sqrt(n)</code>?)</summary>

Suppose we have checked (eliminated) all the factors that are **smaller than or equal to** `sqrt(n)`, now let's say there is a factor (let's define it to be $$k$$) of $$n$$ that is bigger than `sqrt(n)`. Since we have already elminated all the factors **smaller than or equal to** `sqrt(n)`, that means $$k$$ **cannot have** the factors smaller than or eqaul to `sqrt(k)` (we already know what $$k\<n$$). So, $$k$$ must be **a prime** and **the last factor** of our number $$n$$.$$f(x) = x \* e^{2 pi i \xi x}$$

</details>

Now, we can change our code to below

{% code lineNumbers="true" %}

```c
long curr = n;
for (long factor = 2; factor <= sqrt(n); factor += 1) {
    if (is_prime(factor)) {
        long count = 0;
        while (curr % factor == 0) {
            curr = curr / factor;
            count += 1;
        }
        if (count != 0) {
            print(factor, count);
        }
    }
}
if (curr != 1)
{
    print(curr, 1);
}
```

{% endcode %}

Remember the part outside the loop, see [#proof-why-can-we-change-the-loop-condition-to-sqrt-n](#proof-why-can-we-change-the-loop-condition-to-sqrt-n "mention").

#### Second Optimization

Next let's think about it deeper. Since we are dealing with `curr` every time in the loop, so actually we are finding the factors of `curr` instead of `n`. So, we can change the condition of our loop to `...sqrt(curr)...`. Below is the further optimized version:

{% code lineNumbers="true" %}

```c
long curr = n;
for (long factor = 2; factor <= sqrt(curr); factor += 1) { // <-- Changed here
    if (is_prime(factor)) {
        long count = 0;
        while (curr % factor == 0) {
            curr = curr / factor;
            count += 1;
        }
        if (count != 0) {
            print(factor, count);
        }
    }
}
if (curr != 1)
{
    print(curr, 1);
}
```

{% endcode %}

#### Third Optimization

Can we do it even better? Since now we still cannot pass the test case 5, which is when the input is $$2^{62}$$. Actually, we can stop our loop is the `curr == 1` and when our `curr` is a prime. So, we can optimize our code further to below:

<details>

<summary>Proof (Why we can stop when <code>curr == 1</code> or <code>curr</code> is a prime?</summary>

The first case is easy to understand. No more explanation is needed. The second case is actually easy to understand also. Think about it, `curr` is the number remaining for you to check whether it will have factors or not. So, it your `curr` is already a prime, it confirms cannot have any factors. So, you can stop!

</details>

{% code lineNumbers="true" %}

```c
long curr = n;
if (is_prime(curr))
{
    print(curr, 1);
    return;
}
for (long factor = 2; factor <= sqrt(curr) && curr != 1; factor += 1) { // <-- Changed here
    if (is_prime(factor)) {
        long count = 0;
        while (curr % factor == 0) {
            curr = curr / factor;
            count += 1;
        }
        if (count != 0) {
            print(factor, count);
        }
        if (is_prime(curr) && curr != 1)
        {
            print(curr, 1);
            return ;
        }
    }
}
```

{% endcode %}

#### Fourth Optimization

Before we check whether the factor is a prime or not, we can check whether the factor is indeed a factor or not. If not, then we don't need to check whether it's prime or not. This will also improve the efficiency. (This is the **short-circuiting** we have learend in the lecture!)

{% code lineNumbers="true" %}

```c
long curr = n;
if (is_prime(curr))
{
    print(curr, 1);
    return;
}
for (long factor = 2; factor <= sqrt(curr) && curr != 1; factor += 1) { // <-- Changed here
    if ((curr % factor == 0) && is_prime(factor)) {
        long count = 0;
        while (curr % factor == 0) {
            curr = curr / factor;
            count += 1;
        }
        if (count != 0) {
            print(factor, count);
        }
        if (is_prime(curr) && curr != 1)
        {
            print(curr, 1);
            return ;
        }
    }
}
```

{% endcode %}

#### Fifth Optimization

But, see how, the most interesting part now comes! We can do this even without using `is_prime()`!!! Think about it – we are starting with the smallest factor, and we divide the input with the factor as many times as we can. So at the end of the for loop, we can assert that, `curr` is not divisible by anything between 2 and `factor`. Consequently, the next factor for `curr` has to be prime! Similar to this [#proof-why-can-we-change-the-loop-condition-to-sqrt-n](#proof-why-can-we-change-the-loop-condition-to-sqrt-n "mention") right? So, we've freed `is_prime()` and the following code works just fine!

{% code lineNumbers="true" %}

```c
long curr = n;
for (long factor = 2; factor <= sqrt(n) && curr != 1; factor += 1) {
    long count = 0;
    while (curr % factor == 0) {
        curr = curr / factor;
        count += 1;
    }
    if (count != 0) {
        print(factor, count);
    }
}
if (curr != 1) {
    print(curr, 1);
}
```

{% endcode %}

Note that in the **loop condition**, we set the terminating factor to be **`sqrt(n)`.**

<details>

<summary>Proof (Why is the last factor the only one factor remaining?)</summary>

It's quite easy if you think about it. Since we now exit the loop, which means the last factor must be bigger than `sqrt(n)`, so let's say if you have two such factors remaining, you times them up and your result will definitely be greater than `n` right? That's impossible! Proof.

</details>

#### Sixth Optimization

Continue thinking about it? Can we optimize further? The answer is **yes**!!! Using the idea of narrowing down the loop condition from `n` to `curr` in the [#second-optimization](#second-optimization "mention"), we can apply this idea here too.

<details>

<summary>Proof (Why we can change <code>n</code> to <code>curr</code> here?)</summary>

First, let's clarify our goal. Remember that the reason we can update `n` to `curr` is because that we only need to find the factors of `curr`. So, after every iteration, we have already eliminated all the factors that are smaller than `sqrt(curr)`. This ensures that when we reach the termination of the loop, the remaing `curr` must be the last remaining prime one.

</details>

So, now our most succinct code should be:

{% code lineNumbers="true" %}

```c
long curr = n;
for (long factor = 2; factor <= sqrt(curr) && curr != 1; factor += 1) {
    long count = 0;
    while (curr % factor == 0) {
        curr = curr / factor;
        count += 1;
    }
    if (count != 0) {
        print(factor, count);
    }
}
if (curr != 1) {
    print(curr, 1);
}
```

{% endcode %}

### 5. Look-N-Say

> As the hardest question in PE1, this question is actually not that hard. It is quite similar to the last year's PE1 about [/pages/SFzPqZbjJTII1WqqTeKW#id-4.-digits](https://wenbo-notes.gitbook.io/cs1010-notes/past-year-exam/midterm-pe/pages/SFzPqZbjJTII1WqqTeKW#id-4.-digits "mention").

The first part if "look", which is implemented as below:

{% code lineNumbers="true" %}

```c
long count = 0;
long last_digit = n % 10;
do {
    n = n / 10;
    count += 1;
} while (last_digit == n % 10);
```

{% endcode %}

The most important part, as you have seen in AY18/19's PE1 [/pages/SFzPqZbjJTII1WqqTeKW#id-4.-digits](https://wenbo-notes.gitbook.io/cs1010-notes/past-year-exam/midterm-pe/pages/SFzPqZbjJTII1WqqTeKW#id-4.-digits "mention"), is the use of `do-while` loop here.

The second part is "say", which is implemented as below:

{% code lineNumbers="true" %}

```c
say = say + (count * 10 + last_digit) * factor;
factor *= 100; // factor is used to shift right
```

{% endcode %}

Now, combining these two parts, we can get our "main" function:

{% code lineNumbers="true" %}

```c
long look_and_say(long n)
{
    long say = 0;
    long factor = 1;
    while (n != 0) {
        // look
        long count = 0;
        long last_digit = n % 10;
        do {
            n = n / 10;
            count += 1;
        } while (last_digit == n % 10);
        // say
        say = say + (count * 10 + last_digit) * factor;
        factor *= 100;
    }
    return say;
}
```

{% endcode %}

The function above perform one step of look and say. To find the $$k$$-th look-n-say number, we simply do this:

{% code lineNumbers="true" %}

```c
for (long i = 1; i < k; i += 1) {
    n = look_and_say(n % 100000000);
}
```

{% endcode %}

`% 100000000` here is to get the last 8 digits only for generating the next number.

## Tips

1. Marks won't be deducted if you use `break/continue` statement [correctly](https://nus-cs1010.github.io/2425-s1/notes/02-algo.html#bugs) in the loop.
2. The `is_prime()` and [/pages/SFzPqZbjJTII1WqqTeKW#id-3.-goldbach](https://wenbo-notes.gitbook.io/cs1010-notes/past-year-exam/midterm-pe/pages/SFzPqZbjJTII1WqqTeKW#id-3.-goldbach "mention") will be very very useful! Include in the cheatsheet!
3. The use of `return` statement in the loop is allowed in the loop. It will cause the current stack frame to the function to be destroyed.


---

# 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-ay20-21.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.