We are given a number `n`

and an array `A`

of length `m`

where each value in `A`

is less than `n+1`

and greater than or equal to 1.

We have to create a function that executes two operations using a new array of length `n`

with initial values 0.

The array `A`

is a list of operations that we need to execute on our output array. The value indicates the 1 based index of the result array to increment and if the value is greater than n then set every element in the result array to whatever the max value in the array is. For example, given;

n = 3 A = [3, 1, 1, 2, 4, 1] The operations would be

result [0,0,0,0,0] operation 3 => result [0,0,1] operation 1 => result [1,0,1] operation 1 => result [2,0,0] operation 2 => result [2,1,1] operation 4 => result [2,2,2] operation 1 => result [3,2,2]

So the return value would be [3, 2, 2]

I probably didn’t explain this perfectly so check out the link to the formal spec.

The easiest way is to just follow the instruction and do it using the brute force method. Something like:

functionbrute_solution(N, A) {letresult =Array(N).fill(0);letmaxValue = 0for(constoperation of A) {if(operation === N + 1) { result.fill(maxValue) }else{ result[operation - 1]++if(result[operation - 1] > maxValue) { maxValue = result[operation - 1] } } }returnresult }

This solves the problem but fails a few performance tests.

To be honest this took me a minute to get a better solution. Calling `fill()`

in the loop was causing the major slow down and I couldn’t see another way to keep track.

I took a coffee break then it hit me, we don’t actually need to keep track of everything. We know that the least possible value is reset with every reset all operation, therefore we can keep track of that base and use it if we are updating an index that wasn’t the max.

The other indexes won’t need updating because they will be equal to the base and we can set then all at once at the end. Using that logic I updated the function to be:

functionsolution(N, A) {letresult =Array(N).fill(0);letmaxValue = 0letbase = 0for(constoperationofA) {if(operation === N + 1) { base = maxValue }else{ result[operation - 1] =Math.max(result[operation - 1], base) result[operation - 1] ++if(result[operation - 1] > maxValue) { maxValue = result[operation - 1] } } }returnresult.map(value => {returnMath.max(value,base) }) }

This approached passed all performance tests. I think there might be a faster way but thus far it eludes me. If I run into it, I’ll update the post, but for now, that’s all I have for today.

King Pinn: I Salute You. I’m driving halfway across the country and this song is on repeat. Rest in Peace Tonderai Makoni. You were awesome.

After a few weeks off I’m back to business. This is just an update post detailing plans for the rest of the year.

At last we finally have the great reveal, our mystery project was implementing RSA encryption in rust.

We build the final piece of our mystery project, a function that computes modular exponentiation. Come on in, we have large numbers.

We build another part of the mystery project by creating a function that calculates the modular multiplicative inverse of a number.