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:

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;
}

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

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;
}

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

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

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:

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

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:

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

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.

Proof (Why can we change the loop condition to sqrt(n)?)

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}$

Now, we can change our code to below

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

Remember the part outside the loop, see Proof (Why can we change the loop condition to sqrt(n)?).

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:

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

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:

Proof (Why we can stop when curr == 1 or curr is a prime?

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!

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 ;
        }
    }
}

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!)

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 ;
        }
    }
}

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)?) right? So, we've freed is_prime() and the following code works just fine!

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

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

Proof (Why is the last factor the only one factor remaining?)

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.

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, we can apply this idea here too.

Proof (Why we can change n to curr here?)

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.

So, now our most succinct code should be:

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

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 4. Digits*.

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

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

The most important part, as you have seen in AY18/19's PE1 4. Digits*, is the use of do-while loop here.

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

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

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

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;
}

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

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

% 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 in the loop.
2. The is_prime() and 3. Goldbach* 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.