Project Euler 822 - Square the Smallest
Official link: https://projecteuler.net/problem=822
Thought Process
I continued the original problem to see if I could find some sort of patterns. I found that for the original array [2, 3, 4, 5] the following pattern worked. First we square the first element then:
Square second element
Square first element
Square rest of the elements
Repeat steps 1-3
But using this trick did not work for finding the solution to S(10, 100), after investigating more I realised it is because the array goes up to 10, crucially it includes 9. This means at some point Step 3 above fails, because we will square 3^2 instead of 9 first breaking the cycle.
At this point it is clear that the problem has something to do with finding the exact cycle with square numbers.
Knowing the above I deduce the following
Basically, this tells us that once we have a found a turn where the smallest element squared becomes the largest, we enter a cycle where we can simply square every element of the sorted array in order. I illustrate this with S(10, 100)
A = [2, 3, 4, 5, 6, 7, 8, 9, 10]
2^2 < 10
A = [3, 4, 4, 5, 6, 7, 8, 9, 10]
3^2 < 10
A = [4, 4, 5, 6, 7, 8, 9, 9, 10]
4^2 = 16 > 10, we have found our critical point, k = 2
Notice that now we will square the first element every turn.
Since we have 98 turns left, and 98 = 9*10 + 8, we know we have the square every element in our final A, 10 times, then we square the first 8 elements again to get our final answer. Don't forget to use Euler's Theorem to do the squaring since conveniently 1234567891 is a prime.
Interactive Code
Input 2 integers separated by a space (a, b)
Code will output S(a, b) mod 1234567891