Help! TLE in Array Filling problem of August Long Challenge

I have used the same approach in Java, as the video editorial for the problem uses in CPP. Still, the outcome is a Time Limit Error, which isn’t the case in the editorial. Even my code almost matches that of the editorial line by line.

Here’s my code : Solution: 50966031 | CodeChef

Please note the following before going through the solution :

  • I have used the variable ‘next’ instead of ‘rem’(remaining) used in editorial
  • I have used the variable ‘currentSize’ instead of ‘pos’
  • I have used a HashMap to store x and y in the form of key-value pairs

Please help me out

You do know that time complexity of your implementation of finding gcd is O(N), right?

Use Euclidean algorithm for finding gcd in O(\log{N}) time.