felix-felicis's blog

By felix-felicis, history, 3 years ago, In English

Problem: Integers have friends.

After seeing the tutorial of this problem, I learnt about the sparse table. The tutorial though provides the method which is sparse table construction and then using binary search, I could not completely understand it. The comment section was pretty helpful but now the older comment section has been deleted. Can someone please explain what they have done( preferably an approach using sparse table because I have spent a lot of time learning it.)

If possible, please explain it in a beginner-friendly manner as I have never used a sparse table till now. It would really be helpful to me...

  • Vote: I like it
  • 0
  • Vote: I do not like it

| Write comment?
»
3 years ago, # |
Rev. 9   Vote: I like it 0 Vote: I do not like it

Part 1 (Why GCD?):

Firstly, let's find the answer for a fixed array (not subarray). How can we do that? Let's use the fact that $$$(x + m * y) \mod m = x \mod m$$$ for every $$$x$$$, $$$y$$$ and $$$m$$$. Every difference of two numbers must be divisible by $$$m$$$ because $$$y$$$ must be an integer. What's the biggest number that divides every $$$a_i$$$? It's just their GCD! $$$m$$$ can't be equals to $$$1$$$ according to the statement, so now the problem is to find the longest subarray with GCD > 1.

Part 2 (Solving for every subarray efficiently):

Let's build GCD sparse table on differences of $$$a$$$. If you're familiar with two pointers technique (if not, there's a very nice lesson in EDU!), you will easily come up with such solution:

  1. Let's maintain two pointers — $$$L = 0$$$ and $$$R = 0$$$.

  2. While $$$R < n$$$:

    2.1. While $$$GCDQuery(L, R) = 1$$$ increase L by 1. Corner case: $$$a_i = 1$$$. Stop the movement of $$$L$$$ pointer when $$$L = R$$$.

    2.2. If $$$GCDQuery(L, R) > 1$$$, then do $$$ans = max(ans, R - L + 2)$$$. Why am I using $$$R - L + 2$$$ instead of $$$R - L + 1$$$? That's because the number of differences in $$$a$$$ equals to $$$n - 1$$$.

  1. Print $$$m$$$.

Implementation:

Code