18
$\begingroup$

Inspired by my struggles with a certain open-source online learning platform's grading system:

You are working in a computer language with a limited set of built-in functions. You have a set of $m$ real numbers $x_1, x_2, \dots x_m$. These numbers are in some arbitrary, unknown order (i.e., they do not necessarily monotonically increase or decrease.)

You wish to write a function that returns the "second-smallest" of these numbers, where duplicate entries are treated as distinct. In other words, if we were to list the numbers from smallest to largest, this function would return the second number in that ordered list. For example, if the numbers are $\{ 2, 6, 1, 7\}$, the function should return $2$. If the numbers are $\{ 4, 5, 4, 4, 4, 5 \}$, the function should return $4$.

The functions that are you can use are:

  • max(x1, x2, ...) and min(x1, x2, ...): Accepts any number of real-number arguments. Returns the largest one or the smallest one, respectively.
  • sum(x1, x2, ...): Accepts any number of real-number arguments. Returns the sum of all of them.

In addition, you may use the standard arithmetic operations +, -, *, /, and ^.

BONUS QUESTION:

Extend your method to return the $n$th smallest number among the set.

My intended answers for both questions use only max, sum, and arithmetic operations. However, if you can come up with a more elegant answer that uses other built-in functions on this list, it would also be of interest to me. :-)

$\endgroup$
  • 1
    $\begingroup$ If the numbers are {4,5,4,4,4,5}, the function should return 4 Shouldn't the function return 5 here, since 4 is the smallest number? $\endgroup$ – kaitlynmm569 Aug 20 at 14:38
  • 1
    $\begingroup$ From my understanding, duplicates seem to count, so the ordered list would be {4,4,4,4,5,5} not {4,5} $\endgroup$ – Oliver Aug 20 at 14:41
  • 2
    $\begingroup$ @kaitlynmm569: Oliver's understanding is correct. I'll try to edit this to make it clearer. $\endgroup$ – Michael Seifert Aug 20 at 15:13
  • 1
    $\begingroup$ Dear @Michael Seifert, does the intended solution for 2nd-in-order use $O(m^2)$ instances of $x_i$ as in the two answers so far, whose numbers of instances are $m^2\!{-}m$ and $m^2$? $\endgroup$ – humn Aug 20 at 20:58
  • 2
    $\begingroup$ Do you know the value of $m$ before writing the program? $\endgroup$ – melfnt Aug 21 at 9:15
25
$\begingroup$

The best I can come up is this:

$$min((x_1+x_2),(x_1+x_3),\cdots,(x_{m-1}+x_m)) - min(x_1,x_2,\cdots,x_m)$$

i.e.

Finding the minimum sum of two numbers, then subtract it with the smallest one.

So for the $n$-th smallest:

Try to find the minimum sum of $n$ numbers, then subtract it with the minimum sum of $n-1$ numbers.

| improve this answer | |
$\endgroup$
  • 3
    $\begingroup$ The problem is that the construction of the list of sums of pairs is an operation... This will be obvious if one thinks about a real implementation (i.e. writing down a piece of code that works). Namely, one should write down a formula without the $\cdots$ symbol. Of course the issue already exists in the question itself. $\endgroup$ – WhatsUp Aug 24 at 0:19
17
$\begingroup$

Maybe I don't get it (I mean, it is a solution, I just don't know if it is allowed), but:

$max(min(set_1)min(set_2)…min(set_m))$ where each $set_k$ contains all numbers, except $x_k$ (and number of sets equals $(m)$ )

and for $3$rd smallest number it would be similar

just each "set" would contain all numbers except two - and every combination of that, so number of sets would be something like $(m)$x$(m-1)/2$.

and for $4$th smallest number it would be similar

just each "set" would contain all numbers except three - and every combination of that, so number of sets would be something like $(m)$x$(m-1)$x$(m-2)/(3!)$.
Divided by 3! because I just take one combination of certain $x_i$, $x_j$, $x_k$, and ignoring ($x_j$, $x_i$, $x_k$), ($x_k$, $x_i$, $x_j$), ($x_j$, $x_k$, $x_i$), ($x_k$, $x_j$, $x_i$), ($x_i$, $x_k$, $x_j$).

and so on

| improve this answer | |
$\endgroup$
  • $\begingroup$ This is a good variation of answer! Doesn't use any operator, only max and min. So depending on whether the operation or function is more expensive, we can choose to use either this or athin's answer. $\endgroup$ – justhalf Aug 21 at 2:39
  • $\begingroup$ This answer hadn't occurred to me. Cool! $\endgroup$ – Michael Seifert Aug 23 at 18:55
9
+100
$\begingroup$

This solution was originally inspired by athin's solution, but with an improved way of generating the sum of the two smallest numbers. Now, it is a variant on Bass's solution since, as suggested by them in the comments, we can change the sum to a max, and then we don't need to subtract the smallest number at the end.

Let's index the inputs as $x_0, x_1, \dots, x_{m-1}$. Write the numbers $0, 1, \dots, m-1$ in binary. For each $k=1,2,\dots,\lceil\log_2 m\rceil$, let $A_k$ be the min of all $x_i$ such that $i$ has a $0$ in the $k$-th position; let $B_k$ be the min of all $x_i$ such that $i$ has a $1$ in the $k$-th position. Then our solution is $$\min(\max(A_1,B_1),\max(A_2,B_2),\dots,\max(A_k,B_k)).$$ The number of $x$'s in this expression is $m \lceil \log_2 m \rceil$.

Here's why this works:

Each $\max(A_k,B_k)$ will be the max of two elements, so it's at least the second-smallest element. On the other hand, if $x_i$ and $x_j$ are the two smallest $x$'s, then there has to be some position $k$ where the binary representations of $i$ and $j$ differ; say, $i$ has a $0$ in the $k$-th position, and $j$ has a $1$. Then we'll get $A_k = x_i$ and $B_k = x_j$, so $\max(A_k,B_k) = \max(x_i,x_j)$ will definitely show up in the min we take. No other $\max(A_{k'}, B_{k'})$ can be smaller, so $\max(x_i,x_j)$, the second-smallest element, is our final answer.

Here's an example of the finished formula for $m=8$:

$$\min\Big(\max(\min(x_0,x_2,x_4,x_6),\min(x_1,x_3,x_5,x_7)), \max(\min(x_0,x_1,x_4,x_5),\min(x_2,x_3,x_6,x_7)), \max(\min(x_0,x_1,x_2,x_3),\min(x_4,x_5,x_6,x_7))\Big).$$

And here is a diagram of that solution drawn by humn:

diagram


We can sort of generalize this to an $O(m \log m)$ solution for finding the $k^{\text{th}}$ smallest element, by relying on a Math.SE answer written a year ago by a clever and handsome individual.

I say "sort of" because this is only a random construction. Not in the sense that it works only on some random inputs. It's random in the sense that I'll describe a method for generating a formula with some randomness in the method; with positive probability, it'll give us a formula that always works for all inputs.

Here's how.

A "clause" in our formula looks like the following. We split $\{1,2,\dots,m\}$ into $k$ sets $S_1, S_2, \dots, S_k$, and then take $$\max\{\min\{x_i : i \in S_1\}, \min\{x_i : i \in S_2\}, \dots, \min\{x_i : i \in S_k\}\}.$$ The value this generates is always a max of $k$ distinct elements, so it's at least the $k^{\text{th}}$ smallest. And if the $k$ smallest elements happen to be distributed evenly between $S_1, \dots, S_k$, then the value of the clause is the $k^{\text{th}}$ smallest element.

To make sure this always happens, we generate many clauses at random: for each $i \in \{1,2,\dots,m\}$, we choose (independently and uniformly at random) to put it in one of $S_1, \dots, S_k$. As shown in the Math.SE answer I linked to, if we generate $\frac{k^k}{k!} \ln \binom mk \approx k e^k \ln m$ clauses, then with positive probability it will be true that for any $k$ variables, there's a clause that separates them. When this happens, our final formula will be the min of all these clauses.

| improve this answer | |
$\endgroup$
  • $\begingroup$ The reasoning doesn't work if the two smallest elements are the same, right? 2ndMin(4,4,4,5,5) should be 4, not 5. (I haven't checked whether your solution as a whole has this correct, but the reasoning at least is faulty) $\endgroup$ – justhalf Aug 21 at 2:48
  • 2
    $\begingroup$ @justhalf Oh, I see what you were confused by now. There was a (partial) typo in the reasoning; we never compare $x_i$ to $x_j$ to see where they differ, we only compare $i$ and $j$ to see where they differ (and they always will, even if the two smallest elements are the same). $\endgroup$ – Misha Lavrov Aug 21 at 4:21
  • 3
    $\begingroup$ $\sim m\log m$ is fantastic! $\endgroup$ – humn Aug 21 at 4:32
  • $\begingroup$ Ah, right, I misunderstood. Thanks for clarification! And, great algorithm! $\endgroup$ – justhalf Aug 21 at 5:50
  • 1
    $\begingroup$ If you replace every addition with a two-argument max(), you can skip the final subtraction. $\endgroup$ – Bass Aug 21 at 20:47
6
$\begingroup$

Here's yet another approach. It kind of sits between @athin's and @Jan Ivan's methods.

It's based on the observation that the second smallest number is

the smallest number that is bigger than (or equal to) some other number.

This means we can do

a min() over all the possible pairwise max()es: $$\min\left(\max(x_1, x_2), \max(x_1,x_3),\ldots, \max(x_{m-1}, x_m)\right)$$

To double check that this works, we only have to notice that

the smallest number will never show up as one of the max()es, unless there's a tie for the smallest, which is exactly the special case when we do want it to show up.

| improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.