4
\$\begingroup\$

Please post your nominations for Best of Code Review 2013 — Not As Easy As It Looks category: Question that superficially appears simple but turns out to be more difficult than expected.

In your nomination post, be sure to include a link to the question, as well as a short justification (why the question seemed easy, and how it turned out to be difficult). One nomination per post, please. Questions being nominated must date from 2013.

\$\endgroup\$
4
\$\begingroup\$

Optimising Funny Marbles

Writing a program to keep track of marble counts — how hard could it be? It turns out that implementing a sufficiently fast program to store cumulative sums requires a data structure called a binary indexed tree or Fenwick tree, and the paper describing it was only published in 1994. The idea is non-obvious, but once it is revealed, it can be implemented in just a few lines of code.

I'll admit, my review suggested a naïve approach that was marginally better than the original code. Even after seeing a working solution, it took me a while to realize that the array, traversed with bit-twiddled indices, was actually a tree structure in disguise, which led me to find the name of the data structure using some Googling.

\$\endgroup\$
3
\$\begingroup\$

Is there any more optimal way to solve this idempotent equation?

This problem calls for the computation of

M(n), the largest value of a < n such that a2 mod n = a.

but to do so efficiently for many values of n requires a detour through some number theory, including a rare opportunity to use Euler's theorem to compute the modular multiplicative inverse, rather than the usual extended Euclidean algorithm.

\$\endgroup\$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .