A function such that $f(f(n)) = -n$?

This question from somebody's job interview made me puzzled:

Design a function f, such that:

$f(f(n)) = -n$ ,

where n is a 32 bit signed integer; you can't use complex numbers arithmetic. If you can't design such a function for the whole range of numbers, design it for the largest range possible.

Do you have any idea how to tackle it?

EDIT: I removed "Real number" from the title, since it just confused readers, but it was meant just to stress that complex numbers are not allowed.

Solution 1:

I'd try to exploit even and odd numbers. You somehow need a two-stage mapping and thus two subsets of integers. For instance, $f$ could map odd numbers to even numbers, and even numbers to odd numbers with opposite sign. Like this:

$$\color{gray}{f(n)=\begin{cases}0 & n= 0\\ 2n & n\in\text{odd}\\ -n/2 & n\in\text{even} \end{cases}}$$

EDIT: A major brain leak from my part, $n/2$ can stay even, so this doesn't work. However, the idea is sound, and the next one is actually valid.

You can construct a function that doesn't have this problem. Instead of messing up the entire range, you can select the smallest possible subset that has the property $f^2(n)=-n$. The smallest subset is $4$ numbers, because $f^4(n)=n$. You can for instance do something like this

$$f: n_{odd}\mapsto (n+1)_{even} \mapsto (-n)_{odd} \mapsto {-(n+1)}_{even}\mapsto n_{odd}$$

So if you start with even, start at the second stage. Test:

0 -> 0
1 -> 2 -> -1 -> -2
2 -> -1 -> -2 -> 1
3 -> 4 -> -3 -> -4
4 -> -3 -> -4 -> 3

and so on.

Or as a function $$f(n)=\begin{cases}0 & n= 0\\ n+1 & n\in\text{odd}^+\\ -n+1 & n\in\text{even}^+\\ n-1 & n\in\text{odd}^-\\ -n-1 & n\in\text{even}^- \end{cases}$$

This procedure does overflow, but only for the very last number in the range. However, at the end of the range you have bigger problem ($-2^{31}$ exists but $2^{31}-1$ is the top of the range so there's a number without its negative). There are $3$ problematic numbers: $-2^{31}$ without its negative, and $\pm(2^{31}-1)$ that can't be a part of a cycle of $4$ numbers, because $0$ is already taken.

There's actually no way of fixing this last issue, because the problem comes from the size of the set not being a multiple of $4$ after you exclude the zero for its special property $0=-0$. The solution I give is therefore optimal.

Solution 2:

I'm reminded of a math puzzle that goes thusly:

Two mathematicians find themselves in that terrible kingdom where the king kills them unless they perform some mundane logical task. Don't move there, it's awful.

Our heroes must flip a coin each day, and at least one of them must guess correctly the other guy's coin or they both die. Naturally, they are able to live forever using one little trick (executioners hate them!)

What do they do? Well, they have one guy always guess whatever he flips, and the other guy always guess what he didn't flip. So if they end up flipping the same thing, the guy who guesses same will be correct. If they end up flipping different, the other guy will be correct.

I'm going to employ the logic used to solve this puzzle to solve our puzzle here.

Basically, we're going to use the most significant bit in the integer to store whether or not we need to flip signs. It's possible that any bit would do, but the MSB is the least damaging to the number of we end up having to sacrifice it. I'm pretty sure we don't, but I can't rule it out.

Let us say that A is our most significant bit, and S is our sign bit. The remaining bits determine the magnitude of N (As I said, I have not yet concluded if the A bit can be included in the magnitude, or if we have to sacrifice that bit's "usefulness" towards the magnitude in order to serve as data storage about the stage of the operation).

This gives 4 kinds of numbers:

S A
0 0 : N is a "small" positive number, perhaps 0.
0 1 : N is a "large" positive number
1 1 : N is a "small" negative number, perhaps -1
1 0 : N is a "large" negative number

For any number x (positive or negative), negating that number generally flips both the S bit and the A bit -- except for the special values 0 and "the weird number".

We can do this with any number of bits, so for this example we'll use 8 bit numbers.

Our 8 bit number will be 53, or 0b 0011 0101. Our mission will be to turn this into -53, or 1100 1011

Now since we're using 1 bit for sign, and 1 bit for our own purposes, the range this function holds for is only 6 bits (unless it actually DOES hold for all 7 bits, I just haven't tested that condition).

The function operates thusly:

if A == S, flip A.

else flip A and then multiply by the value negative 1.

So F(0b 0011 0101) = 0b 0111 0101. When we pass this through the function again, A will no longer equal S. So it hits the else clause, flipping the A bit (back to 53) and multiplying by negative 1.

Another example, starting with -53 == 0b 1100 1011:

F(0b 1100 1011) == 0b 1000 1011

Then F(0b 1000 1011) hits the else clause, flipping the A bit to get 0b 1100 1011 == -53, and then negating the number to get +53 == 0b 0011 0101.

So the idea is that we're sacrificing the A bit for the purposes of F(x) because it should get reversed when we run the result through F again. Note that F(x) by itself is not a particularly useful function. Also that this may not work for edge cases (I haven't tested much. 0, MAX_VALUE, MIN_VALUE, and -1 all come to mind as cases to test.)