The next multiple of $$$100$$$ after $$$X$$$ is $$$X + 100 - (X mod 100)$$$, so our answer is $$$100 - (X mod 100)$$$.

Time complexity: $$$O(1)$$$ My solution

Simply check if the condition given in the statement is fulfilled.

Time complexity: $$$O(|S|)$$$ My solution

We can simulate the process directly. $$$g_1(x)$$$ can be calculated by sorting the digits in $$$x$$$ in ascending order, while $$$g_2(x)$$$ can be calculated by sorting the digits in $$$x$$$ in descending order.

Time complexity: $$$O(K \times log_{10}(N))$$$ My solution

I suggest using Python for this task. We can use binary search to find the largest integer $$$n \ge d+1$$$ such that $$$X_n \le M$$$. There exists an edge case for $$$X$$$ of length $$$1$$$, as there can only be $$$0$$$ or $$$1$$$ unique values of $$$X_n$$$ in base $$$10$$$.

Time complexity: $$$O(log_2(10^18)*|X|)$$$ My solution

We can solve this problem using a modified version of Dijkstra's algorithm. Since we can only take a train $$$i$$$ at multiples of $$$K_i$$$, before taking a train, we must also add the waiting time for the next train to the "weight" of an edge. The next occurrence of train $$$i$$$ given current time $$$t$$$ is $$$K_i \lfloor \frac{t+K_i-1}{K_i} \rfloor$$$.

Time complexity: $$$O(MlogN)$$$ My solution

We can solve this problem with dynamic programming. Let $$$dp_{i,j,k}$$$ be the maximum possible initial potion magic power, where $$$i$$$ is the planned final number of materials used, $$$j$$$ is the number of materials used so far, and $$$k$$$ is the potion power modulo $$$i$$$. Our transitions are $$$dp_{i,j,k} = dp_{i,j-1,k-a_y (mod i)}$$$ for each index $$$y$$$ in the given array $$$a$$$. Our answer is the minimum of $$$X - dp_{i,i,X mod i}$$$ for all $$$1 \le i \le n$$$.

Time complexity: $$$O(n^4)$$$ My solution