# Interview Question [duplicate]

Possible Duplicate:
solving f(f(x))=g(x)

Here is a nice interview question for computer science people:

Write a unary function f such that

f(f(x)) = -x

Constraints:

1. The function should be pure (i.e. it should have no state and every time its called it should output the same value for the "same" input.).

2. Complex number arithmetic is not allowed. So f(x) = ix is not allowed.

3. You can use plain mathematics or use a program. Choice is yours.

Although I am a student of computer science but I am unable to figure out it's mathematical aspect.

Any help ?

Divide the domain into separate sets of four, each set having the form {x,y,-x,-y}. Now, let f simply rotate within these sets one step. That is, map x to y, and y to -x, and -x to -y, and -y to x. Thus, doing it twice maps every x to -x, as desired. (Also let f(0)=0.)

• umm, sadly I can't figure out how to convert this into a programmable solution :) May be this was not intended by the interviewer. Apr 26, 2010 at 15:31
• If you intend integers, then use the sets {2n,2n+1,-2n,-(2n+1)} as the sets. That is, you map positive evens to the odd above, odds to the opposite of the previous even, negative evens to the odd below, and negative odds to the positive version of the even above. Apr 26, 2010 at 15:34
• You can split $\mathbb R_+$ into pairs $\{x,y\}$ of the form y=x+1 where $x\in(2k,2k+1]$. The program will look like this. If x>0 and ceil(x) is odd, map x to x+1. If x>0 and ceil(x) is even, map x to -(x-1). If x<0 and ceil(-x) is odd, map x to x-1. If x<0 and ceil(-x) is even, map x to -x-1. Apr 26, 2010 at 15:39
• Or, more simply, just look at the two least significant bits in the number, and pick the four groups using them. Apr 26, 2010 at 15:58
• What Mariano said, but you should take one of the bits to be the sign bit so that each number has its negative in the same set of four. Apr 26, 2010 at 17:47

Here's an example implementation I wrote up.

from math import *

def sgn(x):
if x<0: return -1
else: return 1

def f(x):
if floor(abs(x))%2 == 0:
return -sgn(x)*(abs(x)+1)
else:
return sgn(x)*(abs(x)-1)

g = lambda x: f(f(x))


The strategy is that we switch numbers between odd and even (absolute value up one and then down one), but only change the sign one direction... Thus the absolute value ends up at the same place, but the sign only changes once.

• I'm curious as to why my answer was down voted. Since this was asked in the context of computer science, I provided a python implementation. Is there something I am unaware of with regards to placing code in answers? Apr 26, 2010 at 18:03

If you're working over the integers then you can approach this problem in a kind of mindless 'lexicographic' way without having to be clever at all. (To attempt to give this a mathematical angle, I was inspired to take this approach by the way you can build the Golay codes lexicographically.)

The idea is to choose $f(x)$ as close to zero as possible consistent with all of the decisions we've made so far. It's easiest to do this by drawing a table with columns headed by $x$, $f(x)$ and $f(f(x))$.

We can choose $f(0)=0$. Now we need to choose $f(1)$. The closest integer to $0$ we can pick is $2$. That means $f(2)$ must be $-1$. Now to pick $f(3)$. The choice closest to $0$ is $4$ and now we know $f(4)=-3$. After a couple more examples it's obvious how $f$ will act on all of the positive integers. Now start working backwards from $0$. We already know $f(x)$ for all negative odd $x$. A few seconds work reveals a simple pattern for negative even $x$.

So in total I'm sorting the integers as $0, 1, 2, 3, ..., -1, -2, -3, ...$ and at each stage choosing $f(x)$ to be the earliest value that is still available.

We get $f(x) = \left\\{ \begin{array}{ll} 0 & x=0\\\\ x+1 & x > 0 \mbox{ and odd}\\\\ -(x-1) & x > 0 \mbox{ and even}\\\\ x-1 & x < 0 \mbox{ and odd}\\\\ -x-1 & x < 0 \mbox{ and even}\\\\ \end{array} \right.$

The entire function was determined for us automatically without having to pull any rabbits out of hats! This is also a fairly general method. I wonder what related problems it also works for. It's not obvious that we can always get away without having to backtrack.

• This is the same function that I mention in the comment to my answer. Apr 26, 2010 at 18:01
• @Joel Cool. So I just showed your function is a 'lexifunction' (by analogy with 'lexicode' en.wikipedia.org/wiki/Lexicographic_code). Apr 26, 2010 at 18:06
• Yes, that's interesting that it works out to be the same function. Apr 26, 2010 at 18:27
• Oops, I guess it's not exactly the same for negative numbers. Apr 26, 2010 at 20:50

You can use a higher order partial function.

f(x) = λ.(-x) if x is an integer
= x()    if x is a function evaluating to an integer


To illustrate:

f(f(-5)) = f(λ.(5))
= λ.(5)()
= 5

• On the one hand, I find this answer quite elegant. On the other, it's kind of cheating in that your expanding the functions domain/range. Finding $f^\frac{1}{2}$ of $f: S \to S$ is a trivial exercise if you are willing to expand the domain. It would be like if I solved this question by creating two parallel lines and mapping the original line to the new one and it to the negative values on the original.... Apr 26, 2010 at 19:03
• @Christopher: This satisfies all the constraints specified in the problem, so in that sense this is not cheating. :) Apr 26, 2010 at 19:11
• The same idea is used in this answer: mathoverflow.net/questions/17605/how-to-solve-ffx-cosx/… Apr 26, 2010 at 20:36
• @Rahul Back when I was a lad, Béla Bollobás used to tell students that if we found a problem easy to solve as stated, then we ought to fix the statement of the problem to make it a worthwhile challenge, and then solve that problem :-) Apr 26, 2010 at 22:44