Ethan Finds the Maximum Element

APL (Dyalog Unicode), 5 3 bytes

⍳⊥×

Try it online!

Adám gave me an inspiration to golf this further.

How it works

⍳⊥×  Monadic train. Input: n, the length of array A.
  ×  v: Signum, which always gives 1 because n ≥ 1
⍳    B: An array of 0..n-1
 ⊥   Scalar-expand v to get V, a length-n vector of ones,
       then mixed base conversion of V in base B

APL (Dyalog Unicode), 5 bytes

⍳⊥⍴∘1

Try it online!

Edited to remove modulo 107

Uses HyperNeutrino's formula, but optimized through the use of ⊥ (mixed base conversion) directly. Uses ⎕IO←0.

How the code works

⍳⊥⍴∘1  Monadic train. Input: n, the length of array A.
  ⍴∘1  V: An array of 1's of length n
⍳      B: An array of 0..n-1
 ⊥     Mixed base conversion of V in base B

How the ⊥ works

base:  0         1         2         .. n-3         n-2 n-1
digit: 1         1         1         .. 1           1   1
value: 1×..(n-1) 2×..(n-1) 3×..(n-1) .. (n-2)×(n-1) n-1 1
sum of all digit values is the answer.

Jelly, 6 bytes

RU×\S:

Try it online!

Let's analyze under which scenarios this algorithm works.

If the maximum element is at the end of the list, this obviously works, since \$A_N>A_{N-1}\$ and it is processed last. This gives \$(N-1)!\$ possibilities.

If the maximum element is at the second last position, then this obviously works, since \$A_N<A_{N-1}\$ so it is not processed, and \$A_{N-1}>A_{N-2}\$ and is processed last. This gives \$(N-1)!\$ possibilities. There is no overlap between this case and the above because the numbers are guaranteed unique.

If the maximum element is at the third last position, then it depends on the last two elements. If the last element is larger than the second last element, it is treated as the maximum, which fails. There are \$(N-1)!\$ cases, and we can match them by identical first \$(N-3)\$ elements with one case going \$\cdots,max,A,B\$ and the other going \$\cdots,max,B,A\$. Exactly one of these is valid and not the other, so there are \$\frac{(N-1)!}{2}\$ cases.

In general, if the maximum element has \$k\$ elements after it, then the rest of the list must be strictly descending. There is exactly one case for each set of last \$k\$ elements out of the \$k!\$ permutations.

Thus, the answer is \$\frac{(N-1)!}{0!}+\frac{(N-1)!}{1!}+\cdots+\frac{(N-1)!}{(N-1)!}\$. This is OEIS A000522.

This is equal to \$\frac{\frac{N!}{0!}+\frac{N!}{1!}+\cdots+\frac{N!}{(N-1)!}}{N}\$, which is \$\frac{(N\times(N-1)\times(N-2)\times\cdots\times 1+N\times(N-1)\times(N-2)\times\cdots\times 2+\cdots+N}{N}\$, which is the sum of the cumulative product of the list \$[N,N-1,\cdots,2,1]\$, divided by N.

RU×\S:
R       [1, 2, ..., N]
 U      reversed
   \    cumulative
  ×     product
    S   sum
     :  divided by (N)

Having MathJax is really nice :D

Note that the list literally does not matter. All we need to know is N.


Retina, 44 bytes

K`;
"$+"+`(.*);(.*)
$.(_$1*);$.(_$1*$2*
.*;

Try it online! Explanation:

K`;

Replace N with a counter and output (these should be decimal 0, but the empty string works here).

"$+"+`

Repeat N times...

(.*);(.*)
$.(_$1*);$.(_$1*$2*

... multiply the output by the counter and increment both.

.*;

Delete the loop counter.

Previous 47 bytes including modulo 107:

K`;
"$+"{`(i*);(j*)
i$1;j$.1*$2
)`(\w{107})*

j

Try it online! Explanation:

K`;

Replace N with a counter and output (both initially 0).

"$+"{`
)`

Repeat N times...

(i*);(j*)
i$1;j$.1*$2

... multiply the output by the counter and increment both...

(\w{107})*

... and reduce modulo 107.

j

Convert the output to decimal.

Tags:

Code Golf

Recent Posts