Sum of Co-prime Numbers of an Integer

Problem

Given a number $N$, find the sum of all numbers less than or equal to $N$ that are co-prime with $N$.

In case you forgot, a number $x$ is co-prime with $N$ if $gcd(x,N) = 1$.

For example, if $N = 10$, then the following numbers are co-prime with it: $[1, 3, 7, 9]$. Therefore, sum of co-prime numbers will be $1 + 3 + 5 + 7 + 9 = 20$.

Solution

Let us define a function $f(n)$, which gives us sum of all numbers less than or equal to $n$ that are co-prime to $n$. Then we can calculate the value of $f(n)$ with the following formula:

$$\bbox[yellow,5px]{
f(n) = \frac{\phi(n)}{2}n
}$$

where $\phi(n)$ is Euler Phi Function.

For example, for $n = 10$, then we get the sum of co-prime as:

$$\begin{align}
f(10) & = \frac{\phi(10)}{2} \times 10 \\
& = \frac{4}{2} \times 10 \\
& = 20
\end{align}
$$

Read More

My Interview Experience with Shopee / Garena / Sea Group

Recently, lots of fresh graduates are applying to Shopee/Garena from Bangladesh. As one of the first Bangladeshi to be working in Shopee Singapore, many people ask me about my interview experience with them. Hopefully, this post will be useful for them.

I worked as a Software Engineer at Shopee from July 2018 to October 2018. I interviewed with Shopee/Garena last year (August 2017), so it has been a while. But from what I heard, the process did not change much since then.

Before we look into the interview process, first let us look into the company itself.

What is SeaGroup?

Disclaimer

All information provided here are my opinions and interpretations only. I will advise you to validate the correctness of this information yourself.

SeaGroup is an internet company based in Singapore. It has three products:

  1. Garena (a gaming platform where you can buy/sell games; kind of like Steam).
  2. Shopee (e-commerce site like Amazon, Daraz, Pickaboo, Alibaba, Lazada)
  3. Airpay (kind of like Bkash, Upay, Ipay).

Garena was once considered a Unicorn. Garena then rebranded itself into SeaGroup and went for IPO last year September 2017.

Many people get confused between Garena and Shopee. For example, I was hired by Garena and on my S-Pass (Legal ID of Singapore) it was written that I was employed by “Garena Online Private Ltd”. Yet, I was assigned as Engineer at Shopee. Since Shopee and Garena are sister companies, don’t be surprised if you get shuffled.

So, without loss of generality, I will be just saying “Shopee” instead of “Shopee/Garena/SeaGroup” from now on.

Read More

GCD Sum Function

Problem

Given a positive integer $N$, find the value of $g(N)$, where $$g(n) = gcd(1,n) + gcd(2,n) + gcd(3,n) + \dots + gcd(n,n) = \sum_{i=1}^n gcd(i,n)$$

For example,
$$ \begin{align}
g(6) & = gcd(1,6) + gcd(2,6) + g(3,6) + gcd(4,6) + gcd(5,6) + gcd(6,6) \\
& = 1 + 2 + 3 + 2 + 1 + 6 \\
& = 15
\end{align}$$

The function $g(n)$ is called GCD Sum Function for obvious reasons.

There is a paper on this topic, “The gcd-sum Function” and in this post, I will attempt to explain it as simply as possible.

GCD Sum Function – $g(n)$

In short, there is a direct formula for calculating the value of $g(n)$.

If the prime factorization of $n$ is $p_{1}^{a_1} \times p_2^{a_2}\times \dots p_k^{a_k}$, then $$g(n) = \prod_{i=0}^k (a_i + 1)p_i^{a_i} – a_ip^{a_i-1}$$

For example, we know that $6 = 2 \times 3$. So using the formula above, we get:
$$ \begin{align}
g(6) & = \big((1+1)2 – 2^{1-1} \big) \big((1+1)3 – 3^{1-1}\big) \\
& = (4-1)(6-1) \\
& = 15
\end{align}$$

Very neat formula. So, as long as we can prime factorize $n$, we can easily calculate gcd-sum for $n$.

For the curious minds who want to know how we got the formula above, please proceed to next section.

Read More