17755

94
+318  Q:

## Interview question: f(f(n)) == -n

A question I got on my last interview:

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.

Any ideas?

+37  A:

This is true for all negative numbers.

    f(n) = abs(n)


Because there is one more negative number than there are positive numbers for twos complement integers, f(n) = abs(n) is valid for one more case than f(n) = n > 0 ? -n : n solution that is the same same as f(n) = -abs(n). Got you by one ... :D

UPDATE

No, it is not valid for one case more as I just recognized by litb's comment ... abs(Int.Min) will just overflow ...

I thought about using mod 2 information, too, but concluded, it does not work ... to early. If done right, it will work for all numbers except Int.Min because this will overflow.

UPDATE

I played with it for a while, looking for a nice bit manipulation trick, but I could not find a nice one-liner, while the mod 2 solution fits in one.

    f(n) = 2n(abs(n) % 2) - n + sgn(n)


In C#, this becomes the following:

public static Int32 f(Int32 n)
{
return 2 * n * (Math.Abs(n) % 2) - n + Math.Sign(n);
}


To get it working for all values, you have to replace Math.Abs() with (n > 0) ? +n : -n and include the calculation in an unchecked block. Then you get even Int.Min mapped to itself as unchecked negation does.

UPDATE

Inspired by another answer I am going to explain how the function works and how to construct such a function.

Lets start at the very beginning. The function f is repeatedly applied to a given value n yielding a sequence of values.

    n => f(n) => f(f(n)) => f(f(f(n))) => f(f(f(f(n)))) => ...


The question demands f(f(n)) = -n, that is two successive applications of f negate the argument. Two further applications of f - four in total - negate the argument again yielding n again.

    n => f(n) => -n => f(f(f(n))) => n => f(n) => ...


Now there is a obvious cycle of length four. Substituting x = f(n) and noting that the obtained equation f(f(f(n))) = f(f(x)) = -x holds, yields the following.

    n => x => -n => -x => n => ...


So we get a cycle of length four with two numbers and the two numbers negated. If you imagine the cycle as a rectangle, negated values are located at opposite corners.

One of many solution to construct such a cycle is the following starting from n.

 n                 => negate and subtract one
-n - 1 = -(n + 1)  => add one
-n                 => negate and add one
n + 1             => subtract one
n


A concrete example is of such an cycle is +1 => -2 => -1 => +2 => +1. We are almost done. Noting that the constructed cycle contains an odd positive number, its even successor, and both numbers negate, we can easily partition the integers into many such cycles (2^32 is a multiple of four) and have found a function that satisfies the conditions.

But we have a problem with zero. The cycle must contain 0 => x => 0 because zero is negated to itself. And because the cycle states already 0 => x it follows 0 => x => 0 => x. This is only a cycle of length two and x is turned into itself after two applications, not into -x. Luckily there is one case that solves the problem. If X equals zero we obtain a cycle of length one containing only zero and we solved that problem concluding that zero is a fixed point of f.

Done? Almost. We have 2^32 numbers, zero is a fixed point leaving 2^32 - 1 numbers, and we must partition that number into cycles of four numbers. Bad that 2^32 - 1 is not a multiple of four - there will remain three numbers not in any cycle of length four.

I will explain the remaining part of the solution using the smaller set of 3 bit signed itegers ranging from -4 to +3. We are done with zero. We have one complete cycle +1 => -2 => -1 => +2 => +1. Now let us construct the cycle starting at +3.

    +3 => -4 => -3 => +4 => +3


The problem that arises is that +4 is not representable as 3 bit integer. We would obtain +4 by negating -3 to +3 - what is still a valid 3 bit integer - but then adding one to +3 (binary 011) yields 100 binary. Interpreted as unsigned integer it is +4 but we have to interpret it as signed integer -4. So actually -4 for this example or Int.MinValue in the general case is a second fixed point of integer arithmetic negation - 0 and Int.MinValue are mapped to themselve. So the cycle is actually as follows.

    +3 =>    -4 => -3 => -4 => -3


It is a cycle of length two and additionally +3 enters the cycle via -4. In consequence -4 is correctly mapped to itself after two function applications, +3 is correctly mapped to -3 after two function applications, but -3 is erroneously mapped to itself after two function applications.

So we constructed a function that works for all integers but one. Can we do better? No, we cannot. Why? We have to construct cycles of length four and are able to cover the whole integer range up to four values. The remaining values are the two fixed points 0 and Int.MinValue that must be mapped to themselves and two arbitrary integers x and -x that must be mapped to each other by two function applications.

To map x to -x and vice versa they must form a four cycle and they must be located at opposite corners of that cycle. In consequence 0 and Int.MinValue have to be at opposite corners, too. This will correctly map x and -x but swap the two fixed points 0 and Int.MinValue after two function applications and leave us with two failing inputs. So it is not possible to construct a function that works for all values, but we have one that works for all values except one and this is the best we can achieve.

Doesn't meet the criteria: abs(abs(n)) != -n
Sure it does, for all negative numbers, like he said. That was part of the question: If you can't come up with a general one, come up with one that works for the broadest range possible.
This answer is at least as good as the answer by Marj Synowiec and Rowland Shaw, it just works for a different range of numbers
You're right, but it's still deeply unsatisfying.
now some lucky guy come and combine yours and rowlands answer haha
Dude, you may as well just get rid of the "UPDATE"'s and just write one cohesive correct answer. The bottom 3/4 ("inspired by another answer") is _awesome._
+33  A:

Depending on your platform, some languages allow you to keep state in the function. VB.Net, for example:

Function f(ByVal n As Integer) As Integer
Static flag As Integer = -1
flag *= -1

Return n * flag
End Function


IIRC, C++ allowed this as well. I suspect they're looking for a different solution though.

Another idea is that since they didn't define the result of the first call to the function you could use odd/evenness to control whether to invert the sign:

int f(int n)
{
int sign = n>=0?1:-1;
if (abs(n)%2 == 0)
return ((abs(n)+1)*sign * -1;
else
return (abs(n)-1)*sign;
}


Add one to the magnitude of all even numbers, subtract one from the magnitude of all odd numbers. The result of two calls has the same magnitude, but the one call where it's even we swap the sign. There are some cases where this won't work (-1, max or min int), but it works a lot better than anything else suggested so far.

+1 Exact same solution as I had. Didn't notice it though until now. I've removed my answer.
It wouldn't have been here until you started typing yours- no biggy :)
+1 I'd have done the one storing state, as well.
I believe it does work for MAX_INT since that's always odd. It doesn't work for MIN_INT and -1.
It's not a function if it has side effects.
That may be true in math, but it's irrelevant in programming. So the question is whether they're looking for a mathematical solution or a programming solution. But given that it's for a programming job...
+1 I was going to post one with in C with "static int x" implementing a FIFO with negation of the output. But this is close enough.
@nos: Yes it is, it just isn't referentially transparent.
+5  A:

I could imagine using the 31st bit as an imaginary (i) bit would be an approach that would support half the total range.

This would be more complex but no more effective than the current best answer
@1800 INFORMATION: On the other hand, the domain [-2^30+1, 2^30-1] is contiguous which is more appealing from a mathematical point of view.
+4  A:

works for n= [0 .. 2^31-1]

int f(int n) {
if (n & (1 << 31)) // highest bit set?
return -(n & ~(1 << 31)); // return negative of original n
else
return n | (1 << 31); // return n with highest bit set
}

Does not work for negative numbers.
+165  A:

This works for any integer or long in Python:

def f(n):
if n == 0: return 0
if n >= 0:
if n % 2 == 1:
return n + 1
else:
return -1 * (n - 1)
else:
if n % 2 == 1:
return n - 1
else:
return -1 * (n + 1)


Python automatically promotes integers to arbitrary length longs. In other languages the largest positive integer will overflow, so it will work for all integers except that one.

Similar solution in C# (works for any double, except in overflow situations):

static double F(double n)
{
if (n == 0) return 0;

if (n < 0)
return ((long)Math.Ceiling(n) % 2 == 0) ? (n + 1) : (-1 * (n - 1));
else
return ((long)Math.Floor(n) % 2 == 0) ? (n - 1) : (-1 * (n + 1));
}


Mathematically, this function can be expressed as:

f(n) = sgn(n) - (-1)^n * n


This works for all integers. For real numbers you need to replace the n in (-1)^n with { ceiling(n) if n>0; floor(n) if n<0 }.

Broken for -1, because -1 * 0 is still 0
No it isn't. f(-1) = 0. f(0) = 1
It is broken for 1 however. f(1) = 0. f(0) = 1
AFAIK, the modulus operator is not usually defined for negative integers... that may throw a wrench into your function.
@1800: okay, he used the same technique as me but swapped when he adds/subtracts. Odd that it's voted higher when mine came first.
only by one though. My guess is that his is simpler to understand because he only has one answer in his post while you have two
huh... I just created a solution of my own and then realized that it simplifies to this one :P
@rmeador this is Python code, and modulus works on negatives. I'm trying to think of a way to fix it for 1.
@Joel Coehoorn I stopped reading your reply after the part with state stored in f, since I felt that violated the spirit of the question; thus, I saw this one with this solution first. I've now upvoted yours as well.
Fixed, I believe.
Hmm, saving state with even and odd numbers, I should've thought of that.
I was in the middle of trying to figure out a way to do it with odd and even numbers when I looked through the answers and saw that this one was already posted. Oh, well, I guess I was just a little slow.
Golf time: (JavaScript) var f = function(n){return n==0?0:n>0?(n%2!=0?n+1:-(n-1)):(n%2!=0?n-1:-(n+1))}
let me shorten your golf a little: function f(n){return !n?0:(n%2?n:-n)+(n>0?1:-1)}
This is _a_ solution, but it seems hacky. Are there no better solutions to the interview question?
This seems unnecessarily complex. It appears that the interview question is looking for the negative of the absolute value of the input. Why not just negate n if it is greater than 0, otherwise return it?
@JoshL that works for f(n) == -n. Say if(n>0) return -n; else return n; If you say n = -3, then f(n) = -3, and f(f(n)) = -3, which is incorrect.
Scratch my first sentence.
After the changes ("== 0.. return 0;" this really doesn't work for 1 or -1, or can someone explain why it does work for these two numbers?
@PintSizedCat. Look again. f(1) = 2, f(2) = -1. f(-1) = -2, f(-2) = 1.
I think the most important thing is not the actual function (there are infinitely many solutions), but the process by which you can construct such a function.
@rossfabricant: ahh, I missinterpreted the if n % 2 == 1: as if n % 2 == 0:
Does it work for all numbers in the range?
No- it fails for n=1 and int.MinValue. But that's better than only positive or negative solutions provided by most of the other posts.
It works for all values but 2^(n - 1) - 1 if you use n bit integers. It works for n = 1: 1 => 2 [= 1 + 1] => -1 [= -1 * (2 - 1)].
I have a solution that works for the more logical and practical range of -1073741823 through to 1073741822. I don't think not working for "1" is particularly practical if it were a real-world solution. But then this is an interview question, so who am I to talk!
Python doesn't overflow. It just returns a long (arbitrarily long) value.
This answer is awesome.
Equivalent in C# (works for all integers): static int F(int n) { if (n == 0) return 0; if (n < 0) return (n % 2 == 0) ? (n + 1) : (-1 * (n - 1)); else return (n % 2 == 0) ? (n - 1) : (-1 * (n + 1)); }
does the python code work as posted?i can't seem to make a java version work: static int f(int n) { if(n==0) return 0; if (n > 0) if (n % 2 == 1) return n + 1; else return -1 * (n - 1); else if (n % 2 == 1) return n - 1; else return -1 * (n + 1); }
You can use 2^32 as a carry value, since there is no -2^32 in 32 sign bit representation. Define explicitly with ifs that-1 ------> 2^32 -------> 1 and this is the best possible solution
+25  A:

The question doesn't say anything about what the input type and return value of the function f have to be (at least not the way you've presented it)...

...just that when n is a 32-bit integer then f(f(n)) = -n

So, how about something like

Int64 f(Int64 n)
{
return(n > Int32.MaxValue ?
-(n - 4L * Int32.MaxValue):
n + 4L * Int32.MaxValue);
}


If n is a 32-bit integer then the statement f(f(n)) == -n will be true.

Obviously, this approach could be extended to work for an even wider range of numbers...

Sneaky. Character limit.
Yeah, I was working on a similar approach. You beat me to it though. +1 :)
+1  A:

Doesn't fail on MIN_INT:

int f(n) { return n < 0 ? -abs(n + 1) : -(abs(n) + 1); }

Nope, still f(f(0)) == 2
@Stephan202, it seems fine to me know: f(0) = -1, f(-1) = 0
A:
f(n) { return -1 * abs(n) }


How can I handle overflow problems with this? Or am I missing the point?

you always return negative values, even if the input is negative
Given the requirements of the question, that's probably an adequate response. It doesn't say that f(n) has to return a different value. The question is a puzzle, so you look for the exploits (loopholes) that would make a feasible solution.
@Jason: The trouble is that for a negative input n, f(f(n)) should return a positive number (according to the question) which your solution fails to do since it always returns a negative number.
Oh wow, I misunderstood the original question. I thought it was supposed to always return a negative. I didn't read the dash as "opposite"
Open to interpretation I think. If the question intended that it should return "the opposite" then it should have clarified that by giving a second example where f(f(-n)) == n. d03boy's answer works correctly for the question as it was stated IMO.
In your case, f(f(-1)) = f(1) = -1. Therefore f(f(n)) = n, for n<0.
+197  A:

You didn't say what kind of language they expected... Here's a static solution (haskell). It's basically messing with the 2 most significant bits:

f :: Int -> Int
f x | (testBit x 30 /= testBit x 31) = negate $complementBit x 30 | otherwise = complementBit x 30  It's much easier in a dynamic language (python). Just check if the argument is a number X and return a lambda that returns -X: def f(x): if isinstance(x,int): return (lambda: -x) else: return x()  +1 for the lambda idea Cool, I love this... the same approach in JavaScript:var f = function(n) { return (typeof n == 'function') ? n() : function() { return -n; } } nice! great idea It's probably just that my Haskell is very rusty, but have you checked that for (f 0)? It looks like that should produce the same result as (f 0x80000000), at least if we're dealing with 32-bit ints with wraparound arithmetic (on the negate operation). And that would be bad. Damn dirty trick. +1 the haskell one is great. wish i could upvote the lambda idea 10 times :D very elegant, and pragmatic Fantastic hack! Bravo! Would the average interviewer even know what a lambda construct *is*? Holy shit! This made my day. +1 Is there an equivalent implementation in C# for the lambda solution? @Alex Bagnolini - probably not - you cannot have an "int or Func<int>" return type that would compile without "dynamic". +25 A: for javascript (or other dynamically typed languages) you can have the function accept either an int or an object and return the other. i.e. function f(n) { if (n.passed) { return -n.val; } else { return {val:n, passed:1}; } }  giving js> f(f(10)) -10 js> f(f(-10)) 10  alternatively you could use overloading in a strongly typed language although that may break the rules ie int f(long n) { return n; } long f(int n) { return -n; }  The latter doesn't mean the requirement of "a"(singular) function. :) Remove the second half of the answer and this is a correct answer. @Drew which is why I mentioned that it may break the rules how about struct dummy { int n; }; int f(dummy d) { return -d.n; } dummy f(int n) { dummy d = { n }; return d; } . would be better protected against ambiguities. or using one function: variant<int, dummy> f(variant<int, dummy> v) { .... } similar to your javascript sample that is indeed better; I was trying to keep it simple to highlight the main concept. a function is not supposed to keep any state. a math function, that is. to define a math function to do this the same way is fairly easy too though, let f:ℚ→ℚ be defined as f(n) = n + 1/2 if n∈ℤ and -(n - 1/2) if n∉ℤ. Same thing really, no state being kept as they are different inputs (well, not the C one as it's 2 different functions). In JavaScript, a function is an object and so can keep a state. +11 A: For all 32-bit values (with the caveat that -0 is -2147483648) int rotate(int x) { static const int split = INT_MAX / 2 + 1; static const int negativeSplit = INT_MIN / 2 + 1; if (x == INT_MAX) return INT_MIN; if (x == INT_MIN) return x + 1; if (x >= split) return x + 1 - INT_MIN; if (x >= 0) return INT_MAX - x; if (x >= negativeSplit) return INT_MIN - x + 1; return split -(negativeSplit - x); }  You basically need to pair each -x => x => -x loop with a y => -y => y loop. So I paired up opposite sides of the split. e.g. For 4 bit integers: 0 => 7 => -8 => -7 => 0 1 => 6 => -1 => -6 => 1 2 => 5 => -2 => -5 => 2 3 => 4 => -3 => -4 => 3  A: The problem as stated doesn't require that the function must ONLY accept 32 bit ints, only that n, as given, is a 32-bit int. Ruby: def f( n ) return 0 unless n != 0 ( n == n.to_i ) ? 1.0 / n : -(n**-1).to_i end  +1 A: This will work in a very broad range of numbers:  static int f(int n) { int lastBit = int.MaxValue; lastBit++; int secondLastBit = lastBit >> 1; int tuple = lastBit | secondLastBit; if ((n & tuple) == tuple) return n + lastBit; if ((n & tuple) == 0) return n + lastBit; return -(n + lastBit); }  My initial approach was to use the last bit as a check bit to know where we'd be in the first or the second call. Basically, I'd place this bit to 1 after the first call to signal the second call the first had already passed. But, this approach was defeated by negative numbers whose last bit already arrives at 1 during the first call. The same theory applies to the second last bit for most negative numbers. But, what usually happens is that most of the times, the last and second last bits are the same. Either they are both 1 for negative numbers or they are both 0 for positive numbers. So my final approach is to check whether they are either both 1 or both 0, meaning that for most cases this is the first call. If the last bit is different from the second last bit, then I assume we are at the second call, and simply re-invert the last bit. Obviously this doesn't work for very big numbers that use those two last bits. But, once again, it works for a very wide range of numbers. +7 A: C# for a range of 2^32 - 1 numbers, all int32 numbers except (Int32.MinValue)  Func<int, int> f = n => n < 0 ? (n & (1 << 30)) == (1 << 30) ? (n ^ (1 << 30)) : - (n | (1 << 30)) : (n & (1 << 30)) == (1 << 30) ? -(n ^ (1 << 30)) : (n | (1 << 30)); Console.WriteLine(f(f(Int32.MinValue + 1))); // -2147483648 + 1 for (int i = -3; i <= 3 ; i++) Console.WriteLine(f(f(i))); Console.WriteLine(f(f(Int32.MaxValue))); // 2147483647  prints: 2147483647 3 2 1 0 -1 -2 -3 -2147483647  This also doesn't work for f(0) which is 1073741824. f(1073741824) = 0. f(f(1073741824)) = 1073741824 You can generally prove that for a two's complement integer type of any bit size, the function **has to** not work for at least two input values. +3 A: :D boolean inner = true; int f(int input) { if(inner) { inner = false; return input; } else { inner = true; return -input; } }  Might also get you a discussion on why global variables are bad if they don't kick you out of the interview right there! +6 A: Essentially the function has to divide the available range into cycles of size 4, with -n at the opposite end of n's cycle. However, 0 must be part of a cycle of size 1, because otherwise 0->x->0->x != -x. Because of 0 being alone, there must be 3 other values in our range (whose size is a multiple of 4) not in a proper cycle with 4 elements. I chose these extra weird values to be MIN_INT, MAX_INT, and MIN_INT+1. Furthermore, MIN_INT+1 will map to MAX_INT correctly, but get stuck there and not map back. I think this is the best compromise, because it has the nice property of only the extreme values not working correctly. Also, it means it would work for all BigInts. int f(int n): if n == 0 or n == MIN_INT or n == MAX_INT: return n return ((Math.abs(n) mod 2) * 2 - 1) * n + Math.sign(n)  +1 A: A bizarre and only slightly-clever solution in Scala using implicit conversions: sealed trait IntWrapper { val n: Int } case class First(n: Int) extends IntWrapper case class Second(n: Int) extends IntWrapper case class Last(n: Int) extends IntWrapper implicit def int2wrapper(n: Int) = First(n) implicit def wrapper2int(w: IntWrapper) = w.n def f(n: IntWrapper) = n match { case First(x) => Second(x) case Second(x) => Final(-x) }  I don't think that's quite the right idea though. +3 A: In PHP function f($n) {
if(is_int($n)) { return (string)$n;
}
else {
return (int)$n * (-1); } } I'm sure you can understand the spirit of this method for other languages. I explicitly casted back to int to make it more clear for people who don't use weakly typed languages. You'd have to overload the function for some languages. The neat thing about this solution is it works whether you start with a string or an integer, and doesn't visibly change anything when returning f(n). In my opinion, the interviewer is asking, "does this candidate know how to flag data to be operated on later," and, "does this candidate know how to flag data while least altering it?" You can do this with doubles, strings, or any other data type you feel like casting. Great! Not the best solution, but the easier to understand But of course, using hacks like this in real code is a terrible idea. If you need to store state with your data, create a new type like (s, a), and use a binding operator to work with only the result. (This is very similar to Haskell's state monad, but not the same.) A: Seems easy enough. <script type="text/javascript"> function f(n){ if (typeof n === "string") { return parseInt(n, 10) } return (-n).toString(10); } alert(f(f(1))); </script>  It specifically states "where n is a signed 32 bit int", not a string No, I think he's OK. You can feed in any 32 bit int. It doesn't say f(n) can't be a string. +13 A: A C++ version, probably bending the rules somewhat but works for all numeric types (floats, ints, doubles) and even class types that overload the unary minus: template <class T> struct f_result { T value; }; template <class T> f_result <T> f (T n) { f_result <T> result = {n}; return result; } template <class T> T f (f_result <T> n) { return -n.value; } void main (void) { int n = 45; cout << "f(f(" << n << ")) = " << f(f(n)) << endl; float p = 3.14f; cout << "f(f(" << p << ")) = " << f(f(p)) << endl; }  Skizz Exactly what I was thinking: overload f(). "Bending the rules"? Who knows? Perhaps "f" and "n" are really abstractions for something far more complicated. I would hope in the "real world" this is more than a silly puzzle. Good idea. As an alternative, you could probably lose the struct and instead have one function return a pointer, the other function dereference and negate. +62 A: Or, you could abuse the preprocessor: #define f(n) (f##n) #define ff(n) -n int main() { int n = -42; cout << "f(f(" << n << ")) = " << f(f(n)) << endl; return 0; }  Skizz +1, really cool; but the void main really makes my eyes bleed. So you'd be Konrad "Le Chiffre" Rudolph then? I'll get my coat. Yeah, I know about the whole "void main" thing, but adding a "return 0;" is just so much extra effort ;-) Re Skizz's comment: Now, that's taking the whole 'programmers are lazy' stereotype to a whole 'nother level! :-) @Skizz, return 0 from main isn't required in c++ even with int return value... so by doing it right you actually type one less character! Skizz always abuses preprocessor :D This is not a function ..so this is not a valid solution @smerlin: It's technically an inline function returning an inline function: the bodies of both are expanded at compile time, or rather just before. Can't get much more efficient than this. @Clark (the recent editor): return 0; can be left out for main () although some older compilers may generate a warning about this. It means that the application has no meaningful exit code. looooolzieeeeee +9 A: Uses globals...but so? bool done = false f(int n) { int out = n; if(!done) { out = n * -1; done = true; } return out; }  Not sure that this was the intention of the question asker, but +1 for "thinking out of the box". Instead of conditionally saying "done = true", you should always say "done = !done", that way your function can be used more than once. @Chris, since setting done to true is inside of an if(!done) block, it's equivalent to done=!done, but !done doesn't need to be computed (or optimized out by the compiler, if it's smart enough). This is the first thing that comes to mind for me. I thought this was cheating. @nsayer, Chris is talking about putting done = !done _outside_ the if statement. My first thought was also to solve this using a global variable, even though it kind of felt like cheating for this particular question. I would however argue that a global variable solution is the best solution given the specifications in the question. Using a global makes it very easy to understand what is happening. I would agree that a done != done would be better though. Just move that outside the if clause. A: How about int f(int n) { return -abs(n); }  Nope: f(f(-1)) == -1 != 1 I was so sure, I didn't even test it in my brain. Well, you just have to specify that it only works with positive integers (0 <= n < 2^31). Would be my favorite answer if it worked. +3 A: return x ^ ((x%2) ? 1 : -INT_MAX);  +21 A: Using complex numbers, you can effectively divide the task of negating a number into two steps: • multiply n by i, and you get n*i, which is n rotated 90° counter-clockwise • multiply again by i, and you get -n The great thing is that you don't need any special handling code. Just multiplying by i does the job. But you're not allowed to use complex numbers. So you have to somehow create your own imaginary axis, using part of your data range. Since you need exactly as much imaginary (intermediate) values as initial values, you are left with only half the data range. I tried to visualize this on the following figure, assuming signed 8-bit data. You would have to scale this for 32-bit integers. The allowed range for initial n is -64 to +63. Here's what the function does for positive n: • If n is in 0..63 (initial range), the function call adds 64, mapping n to the range 64..127 (intermediate range) • If n is in 64..127 (intermediate range), the function subtracts n from 64, mapping n to the range 0..-63 For negative n, the function uses the intermediate range -65..-128. But of course! It's so obvious if your language actually supports complex numbers (although re-reading the question, it doesn't say it has to be a program at all). Oh wait, the question says no complex numbers. I retract my upvote. @geschema, what tool did you use to create those nice graphics? Sorry, the question says explicitly no complex numbers. What program was used for the very good looking drawings? @Liran: I used OmniGraffle (Mac-only) I'm taken in by the diagrams too :) +1 I think this is the best answer. I don't think people read enough, because they all noted that the question said complex numbers could not be used. I read the entire thing, and you described the solution in complex numbers to set the stage for the non-complex solution to the question asked. Very nicely done. The images have disappeared? What diagrams are people talking about? I don't see any. +51 A: Thanks to overloading in C++ : double f(int var) { return double(var); } int f(double var) { return -int(var); } int main(){ int n(42); std::cout<<f(f(n)); }  Unfortunately, because of name mangling, the functions you call "f" actually have weirder names. ABSOLUTELY BRILLIANT!!!!!!! Also works in C#. :-D I've thought of something like that, but thinking in C, this was thrown away... good job! @Rui Craverio: It wouldn't work in .NET 3.5+ because the author chose to use the var keyword as a variable name. @Lucas: .NET 3.5 doesn't have anything to do with the var keyword, you're confusing with C# 3.0 (which can target .NET 2+). And the var keyword they added is a contextual keyword, so it wouldn't cause any problem here as "var" isn't being used as a type. technically... this is not what the question demands. you defined 2 f() functions, f(int) and f(float) and the questions asks "Design a function f() ... " FACINATING!! THIS IS THE MOST SUCCINT SOLUTION +11 A: I'm not actually trying to give a solution to the problem itself, but do have a couple of comments, as the question states this problem was posed was part of a (job?) interview: • I would first ask "Why would such a function be needed? What is the bigger problem this is part of?" instead of trying to solve the actual posed problem on the spot. This shows how I think and how I tackle problems like this. Who know? That might even be the actual reason the question is asked in an interview in the first place. If the answer is "Never you mind, assume it's needed, and show me how you would design this function." I would then continue to do so. • Then, I would write the C# test case code I would use (the obvious: loop from int.MinValue to int.MaxValue, and for each n in that range call f(f(n)) and checking the result is -n), telling I would then use Test Driven Development to get to such a function. • Only if the interviewer continues asking for me to solve the posed problem would I actually start to try and scribble pseudocode during the interview itself to try and get to some sort of an answer. However, I don't really think I would be jumping to take the job if the interviewer would be any indication of what the company is like... Oh, this answer assumes the interview was for a C# programming related position. Would of course be a silly answer if the interview was for a math related position. ;-) You are lucky they asked for 32 int, if it was 64 bit the interview will never continue after you run the tests ;-) Indeed, if I would even get to a point to actually write that test and run it during an interview. ;-) My point: I would try not to get to that point in an interview at all. Programming is more of "a way of thinking" than "how does he write lines of code" in my opinion. A: Perhaps cheating? (python) def f(n): if isinstance(n, list): return -n[0] else: return [n,0] n = 4 print f(f(n)) --output-- -4  +1 A: easy: function f($n) {
if ($n%2 == 0) return ($n+1)*-1;
else return ($n-1); }  A: Clojure solution: (defmacro f [n] (if (list? n) (- ~n) n)) Works on positive and negative integers of any size, doubles, and ratios too! +6 A: Nobody said it had to be stateless. int32 f(int32 x) { static bool idempotent = false; if (!idempotent) { idempotent = true; return -x; } else { return x; } }  Cheating, but not as much as a lot of the examples. Even more evil would be to peak up the stack to see if your caller's address is &f, but this is going to be more portable (although not thread safe... the thread-safe version would use TLS). Even more evil: int32 f (int32 x) { static int32 answer = -x; return answer; }  Of course, neither of these works too well for the case of MIN_INT32, but there is precious little you can do about that unless you are allowed to return a wider type. you can 'upgrade' it to ask about the address (yes, you must get it by ref\ as a pointer) - in C, for example:int f(intif (addr == }return n;} A: In C, int f(int n) { static int r = 0; if (r == 1) {r--; return -1 * n; }; r++; return n; }  It would have helped to know what language this was for. Am I missing something? Many "solutions" seem overly complex, and quite frankly, don't work (as I read the problem). It's a valid solution, but as I mentioned on another post it depends on how they want to define function (a true function isn't stateful, it has exactly one return value for any given input value). It's also of value to watch how you feel about implementing state in such a function (it should make you feel queasy and you should naturally try to avoid it until it was the only solution possible IMO) A: I thought the largest range possible was hinting at a modular arithmetic solution. In some modular bases M there is number which when squared is congruent to M-1 (which is congruent to -1). For example if M=13, 5*5=25, 25 mod 13=12 (= -1) Anyway here's some python code for M=2**32-3. def f(x): m=2**32-3; halfm=m//2; i_mod_m=1849436465 if abs( x ) >halfm: raise "too big" if x<0: x+=m x=(i_mod_m*x) % m if (x>halfm): x-=m return x;  Note there are 3 values it wont work for 2 ** 31-1, -(2 ** 31-1) and -(2 ** 31) A: Here's a C implementation of rossfabricant's answer. Note that since I stick with 32-bit integers at all times, f( f( 2147483647 ) ) == 2147483647, not -2147483647. int32_t f( int32_t n ) { if( n == 0 ) return 0; switch( n & 0x80000001 ) { case 0x00000000: return -1 * ( n - 1 ); case 0x00000001: return n + 1; case 0x80000000: return -1 * ( n + 1 ); default: return n - 1; } }  If you define the problem to allow f() to accept and return int64_t, then 2147483647 is covered. Of course, the literals used in the switch statement would have to be changed. Some portability issues with byte-order possible. +1 A: how about this (C language): int f(int n) { static int t = 1; return (t = t ? 0 : 1) ? -n : n; }  just tried it, and f(f(1000))  returns -1000 f(f(-1000))  returns 1000 is that correct or am i missing the point? This is not thread-safe and won't work when called multiple times. A: Really, these questions are more about seeing the interviewer wrestle with the spec, and the design, error handling, boundary cases and the choice of suitable environment for the solution, etc, more than they are about the actual solution. However: :) The function here is written around the closed 4 cycle idea. If the function f is only permitted to land only on signed 32bit integers, then the various solutions above will all work except for three of the input range numbers as others have pointed out. minint will never satisfy the functional equation, so we'll raise an exception if that is an input. Here I am permitting my Python function to operate on and return either tuples or integers. The task spec admits this, it only specifies that two applications of the function should return an object equal to the original object if it is an int32. (I would be asking for more detail about the spec.) This allows my orbits to be nice and symmetrical, and to cover all of the input integers (except minint). I originally envisaged the cycle to visit half integer values, but I didn't want to get tangled up with rounding errors. Hence the tuple representation. Which is a way of sneaking complex rotations in as tuples, without using the complex arithmetic machinery. Note that no state needs to be preserved between invocations, but the caller does need to allow the return value to be either a tuple or an int. def f(x) : if isinstance(x, tuple) : # return a number. if x[0] != 0 : raise ValueError # make sure the tuple is well formed. else : return ( -x[1] ) elif isinstance(x, int ) : if x == int(-2**31 ): # This value won't satisfy the functional relation in # signed 2s complement 32 bit integers. raise ValueError else : # send this integer to a tuple (representing ix) return( (0,x) ) else : # not an int or a tuple raise TypeError  So applying f to 37 twice gives -37, and vice versa: >>> x = 37 >>> x = f(x) >>> x (0, 37) >>> x = f(x) >>> x -37 >>> x = f(x) >>> x (0, -37) >>> x = f(x) >>> x 37  Applying f twice to zero gives zero: >>> x=0 >>> x = f(x) >>> x (0, 0) >>> x = f(x) >>> x 0  And we handle the one case for which the problem has no solution (in int32): >>> x = int( -2**31 ) >>> x = f(x) Traceback (most recent call last): File "<pyshell#110>", line 1, in <module> x = f(x) File "<pyshell#33>", line 13, in f raise ValueError ValueError  If you think the function breaks the "no complex arithmetic" rule by mimicking the 90 degree rotations of multiplying by i, we can change that by distorting the rotations. Here the tuples represent half integers, not complex numbers. If you trace the orbits on a number line, you will get nonintersecting loops that satisfy the given functional relation. f2: n -> (2 abs(n) +1, 2 sign( n) ) if n is int32, and not minint. f2: (x, y) -> sign(y) * (x-1) /2 (provided y is \pm 2 and x is not more than 2maxint+1  Exercise: implement this f2 by modifying f. And there are other solutions, e.g. have the intermediate landing points be rational numbers other than half integers. There's a fraction module that might prove useful. You'll need a sign function. This exercise has really nailed for me the delights of a dynamically typed language. I can't see a solution like this in C. +4 A: I'd like to share my point of view on this interesting problem as a mathematician. I think I have the most efficient solution. If I remember correctly, you negate a signed 32-bit integer by just flipping the first bit. For example, if n = 1001 1101 1110 1011 1110 0000 1110 1010, then -n = 0001 1101 1110 1011 1110 0000 1110 1010. So how do we define a function f that takes a signed 32-bit integer and returns another signed 32-bit integer with the property that taking f twice is the same as flipping the first bit? Let me rephrase the question without mentioning arithmetic concepts like integers. How do we define a function f that takes a sequence of zeros and ones of length 32 and returns a sequence of zeros and ones of the same length, with the property that taking f twice is the same as flipping the first bit? Observation: If you can answer the above question for 32 bit case, then you can also answer for 64 bit case, 100 bit case, etc. You just apply f to the first 32 bit. Now if you can answer the question for 2 bit case, Voila! And yes it turns out that changing the first 2 bits is enough. Here's the pseudo-code 1. take n, which is a signed 32-bit integer. 2. swap the first bit and the second bit. 3. flip the first bit. 4. return the result.  Remark: The step 2 and the step 3 together can be summerised as (a,b) --> (-b, a). Looks familiar? That should remind you of the 90 degree rotation of the plane and the multiplication by the squar root of -1. If I just presented the pseudo-code alone without the long prelude, it would seem like a rabbit out of the hat, I wanted to explain how I got the solution. Yes it's an interesting problem. You know your math. But this is a computer science problem. So you need to study computers. Sign-magnitude representation is allowable but it went out of style around 60 years ago. 2's-complement is most popular. Here's what your function does to the two bits when applied twice: (a,b) --> (-b, a) --> (-a, -b). But, we are trying to get to (-a, b), not (-a, -b). @buti-oxa, you are right. The two bits operation should go like: 00 -> 01 -> 10 -> 11 -> 00. But then my algorithm assumes sign-magnitude representation which is unpopular now, as Windows programmer said, so I think my algorithm is of little use. So can't he just do the steps twice instead of once? buti-oxa is entirely right: the function doesn't even flip the first bit after two invocations, it flips the first two bits. Flipping all the bits is closer to what 2's complement does, but it's not exactly right. A: int f(int x){ if (x < 0) return x; return ~x+1; //two's complement }  Fails for -1. f(f(-1)) is supposed to be -(-1) i.e. +1, but yours yields -1. A: This one's in Python. Works for all negative values of n: f = abs  A: Here's a variant I haven't seen people use. Since this is ruby, the 32-bit integer stuff sort of goes out the window (checks for that can of course be added). def f(n) case n when Integer proc { n * -1 } when Proc n.call else raise "Invalid input #{n.class} #{n.inspect}" end end (-10..10).each { |num| puts "#{num}: #{f(f(num))}" }  +56 A: Here's a proof of why such a function can't exist, for all numbers, if it doesn't use extra information(except 32bits of int): f(0)=0, otherwise f(0)=x. f(x)=0 (0=-) => f(f(x))=x suppose f(y)=x. we want f(x)=-y then. and f(f(x))=-x -> f(-y)=-x. So, we need to divide all integers except 0 into sets of 4, but we have an odd number of such integers, not only that, if we remove the integer that doesn't have a positive counterpart we still have 2(mod4) numbers. If we remove the 2 maximal numbers left(by abs value), we can get the function: int sign(int n) { if(n>0) return 1; else return -1; } int f(int n) { if(n==0) return 0; switch(abs(n)%2) { case 1: return sign(n)*(abs(n)+1); case 0: return -sign(n)*(abs(n)-1); } }  Of course another option, is to not comply for 0, and get the 2 numbers we removed as a bonus.(But that's just a silly if) I can't believe I had to read this far down to find a good procedural solution that handles negative numbers without resorting to global variables or tricks that obfuscate the code. If I could vote you up more than once, I would. Nice observation, that there is an odd number of nonzero integers in any _n_ signed bits. +1 A: One way to create many solutions is to notice that if we have a partition of the integers into two sets S and R s.t -S=S, -R=R, and a function g s.t g(R) = S then we can create f as follows: if x is in R then f(x) = g(x) if x is in S then f(x) = -invg(x) where invg(g(x))=x so invg is the inverse function for g. The first solution mentioned above is the partition R=even numbers, R= odd numbers, g(x)=x+1. We could take any two infinite sets T,P s.t T+U= the set of integers and take S=T+(-T), R=U+(-U). Then -S=S and -R=R by their definitions and we can take g to be any 1-1 correspondence from S to R, which must exist since both sets are infinite and countable, will work. So this will give us many solutions however not all of course could be programmed as they would not be finitely defined. An example of one that can be is: R= numbers divisible by 3 and S= numbers not divisible by 3. Then we take g(6r) = 3r+1, g(6r+3) = 3r+2. A: Easy, just make f return something that appears to equal any integer, and is convertable from an integer. public class Agreeable { public static bool operator==(Agreeable c, int n) { return true; } public static bool operator!=(Agreeable c, int n) { return false; } public static implicit operator Agreeable(int n) { return new Agreeable(); } } class Program { public static Agreeable f(Agreeable c) { return c; } static void Main(string[] args) { Debug.Assert(f(f(0)) == 0); Debug.Assert(f(f(5)) == -5); Debug.Assert(f(f(-5)) == 5); Debug.Assert(f(f(int.MaxValue)) == -int.MaxValue); } }  +2 A: The problem states "32-bit signed integers" but doesn't specify whether they are twos-complement or ones-complement. If you use ones-complement then all 2^32 values occur in cycles of length four - you don't need a special case for zero, and you also don't need conditionals. In C: int32_t f(int32_t x) { return (((x & 0xFFFFU) << 16) | ((x & 0xFFFF0000U) >> 16)) ^ 0xFFFFU; }  This works by 1. Exchanging the high and low 16-bit blocks 2. Inverting one of the blocks After two passes we have the bitwise inverse of the original value. Which in ones-complement representation is equivalent to negation. Examples: Pass | x -----+------------------- 0 | 00000001 (+1) 1 | 0001FFFF (+131071) 2 | FFFFFFFE (-1) 3 | FFFE0000 (-131071) 4 | 00000001 (+1) Pass | x -----+------------------- 0 | 00000000 (+0) 1 | 0000FFFF (+65535) 2 | FFFFFFFF (-0) 3 | FFFF0000 (-65535) 4 | 00000000 (+0)  What about byte-order across different architectures? All the arithmetic is 32-bit. I do not manipulate individual bytes, so byte order will not affect it. A: const unsigned long Magic = 0x8000000; unsigned long f(unsigned long n) { if(n > Magic ) { return Magic - n; } return n + Magic; }  0~2^31 A: int j = 0; void int f(int n) { j++; if(j==2) { j = 0; return -n; } return n; }  :D +1 A: What about following: int f (int n) { static bool pass = false; pass = !pass; return pass? n : -n; }  Not thread safe :P But not a bad answer. +3 A: int f( int n ){ return n==0?0:(n&1?n:-n)+(n<0?-1:1); }  @Dinah assuming this is C or C++, that is just fine +1 A: Mine gives the right answer...50% of the time, all the time. int f(int num) { if (rand()/(double)RAND_MAX > 0.5) return ~num + 1; return num; }  A: This will work for the range -1073741823 to 1073741822: int F(int n) { if(n < 0) { if(n > -1073741824) n = -1073741824 + n; else n = -(n + 1073741824); } else { if(n < 1073741823) n = 1073741823 + n; else n = -(n - 1073741823); } return n; }  It works by taking the available range of a 32 bit signed int and dividing it in two. The first iteration of the function places n outside of that range by itself. The second iteration checks if it is outside this range - if so then it puts it back within the range but makes it negative. It is effectively a way of keeping an extra "bit" of info about the value n. p.s. no global variables, and has the advantage of being a simple enough implementation that it can work in a large number of languages +3 A: I would you change the 2 most significant bits. 00.... => 01.... => 10..... 01.... => 10.... => 11..... 10.... => 11.... => 00..... 11.... => 00.... => 01..... As you can see, it's just an addition, leaving out the carried bit. How did I got to the answer? My first thought was just a need for symmetry. 4 turns to get back where I started. At first I thought, that's 2bits Gray code. Then I thought actually standard binary is enough. The problem with this approach is that it doesn't work with two's compliment negative numbers (which is what every modern CPU uses). That's why I deleted my identical answer. The question specified 32-bit signed integers. This solution does not work for two's-complement or one's-complement representations of the 32-bit signed integers. It will only work for sign-and-magnitude representations, which are very uncommon in modern computers (other than floating point numbers). @DrJokepu - Wow, after six months--jinx! A: PHP, without using a global variable: function f($num) {
static $mem;$answer = $num-$mem;

if ($mem == 0) {$mem = $num*2; } else {$mem = 0;
}

return $answer; }  Works with integers, floats AND numeric strings! just realized this does some unnecessary work, but, whatever A: void f(int x) { Console.WriteLine(string.Format("f(f({0})) == -{0}",x)); }  Sorry guys... it was too tempting ;) Bad, nasty cheater ;) A: C++ solution; long long f(int n){return static_cast <long long> (n);} int f(long long n){return -static_cast <int> (n);} int n = 777; assert(f(f(n)) == -n);  A: Using static variables in C functions to remember previously returned (random) value: int f(int n) { int not_n; static int ori_n; static int prev_ret; static int first_call = 1; if (n == prev_ret && ! first_call) return -ori_n; ori_n = n; not_n = rand(); while (not_n == n) not_n = rand(); first_call = 0; prev_ret = not_n; return not_n; }  This ought to work for any n. A: Another cheating solution. We use a language that allows operator overloading. Then we have f(x) return something that has overloaded == to always return true. This seems compatible with the problem description, but obviously goes against the spirit of the puzzle. Ruby example: class Cheat def ==(n) true end end def f(n) Cheat.new end  Which gives us: >> f(f(1)) == -1 => true  but also (not too surprising) >> f(f(1)) == "hello world" => true  +1 A: int f(const int n) { static int last_n; if (n == 0) return 0; else if (n == last_n) return -n; else { last_n = n; return n; } }  Hackish, but correct. A: Isn't remembering your last state a good enough answer? int f (int n) { //if count static int count = 0; if (count == 0) { count = 1; return n; } if (n == 0) return 0; else if (n > 0) { count = 0; return abs(n)*(-1); } else { count = 0; return abs(n); } } int main() { int n = 42; std::cout << f(f(n)) }  Depends on the interviewers definition of "Function". That's a method--a function doesn't really have state. But maybe they didn't mean function that literally. A: Assuming f must take and return a 32-bit signed integer and that function state cannot be stored, I'm pretty sure one can prove that it is impossible to cover all values and as a corollary, the maximum coverage is all possible integers in range except for one of them. Could someone please show me why this is wrong? +1 A: Some were similar but just thought I would write down my first idea (in C++) #include <vector> vector<int>* f(int n) { returnVector = new vector<int>(); returnVector->push_back(n); return returnVector; } int f(vector<int>* n) { return -(n->at(0)); }  Just using overloading to cause f(f(n)) to actually call two different functions A: JavaScript one-liner: function f(n) { return ((f.f = !f.f) * 2 - 1) * n; }  sadly not threadsafe thread-what? JavaScript is single-threaded, on browsers at-least A: I haven't looked at the other answers yet, I assume the bitwise techniques have been thoroughly discussed. I thought I'd come up with something evil in C++ that is hopefully not a dupe: struct ImplicitlyConvertibleToInt { operator int () const { return 0; } }; int f(const ImplicitlyConvertibleToInt &) { return 0; } ImplicitlyConvertibleToInt f(int & n) { n = 0; // The problem specification didn't say n was const return ImplicitlyConvertibleToInt(); }  The whole ImplicitlyConvertibleToInt type and overload is necessary because temporaries can't be bound to a non-const reference. Of course, looking at it now it's undefined whether f(n) is executed before -n. Perhaps a better solution with this degree of evil is simply: struct ComparesTrueToInt { ComparesTrueToInt(int) { } // implicit construction from int }; bool operator == (ComparesTrueToInt, int) const { return true; } ComparesTrueToInt f(ComparesTrueToInt ct) { return ComparesTrueToInt(); }  C++ gets a bad rep because of people like you. This is a horrible practice... and while it somewhat solves the comparison f(f(x)) == -x, it's completely useless and destructive for any other use. You're right that it is evil; but that is not in any way a good thing. Besides... what are you going to do if someone tests your function like this: cout << x << (f(f(x)) == -x ? " works." : " doesn't work.") << endl; The result is undefined. In my version of GCC it prints zero every line. Caught red-handed! A: int f(int n) { static long counter=0; counter++; if(counter%2==0) return -n; else return n; }  Thanks & Regards, calvin A: Another way is to keep the state in one bit and flip it with care about binary representation in case of negative numbers... Limit is 2^29 int ffn(int n) {  n = n ^ (1 << 30); //flip the bit if (n>0)// if negative then there's a two's complement { if (n & (1<<30)) { return n; } else { return -n; } } else { if (n & (1<<30)) { return -n; } else { return n; } } }  +4 A: x86 asm (AT&T style): ; input %edi ; output %eax ; clobbered regs: %ecx, %edx f: testl %edi, %edi je .zero movl %edi, %eax movl$1, %ecx
movl %edi, %edx
andl $1, %eax addl %eax, %eax subl %eax, %ecx xorl %eax, %eax testl %edi, %edi setg %al shrl$31, %edx
subl %edx, %eax
imull %ecx, %eax
subl %eax, %edi
movl %edi, %eax
imull %ecx, %eax
.zero:
xorl %eax, %eax
ret


Code checked, all possible 32bit integers passed, error with -2147483647 (underflow).

+4  A:

How about this?

int nasty(int input)
{
return input + INT_MAX/2;
}

How is this supposed to work....?
Hmm... I believe I made a typo. Essentially the point is to overflow the integer variable until it is in negative territory. But I believe I screwed something up here.. ignore.
A:
number f( number n)
{
static count(0);
if(count > 0) return -n;
return n;
}

f(n) = n

f(f(n)) = f(n) = -n

I think you somewhere miss a count++
@sth - lol! yeah, must be time for my cup of tea! and chocolate biscuit!
A:
int f(int n) {
return ((n>0)? -1 : 1) * abs(n);
}

Works for all int values, except MIN_INT (since MIN_INT * -1 > MAX_INT), so there is no valid return value for it.
surely this just returns f(n)=-n ?then f(f(n)) = n, not -n as the question asks
+8  A:

This Perl solution works for integers, floats, and strings.

sub f {
my $n = shift; return ref($n) ? -n : \$n; }  Try some test data. print$_, ' ', f(f($_)), "\n" for -2, 0, 1, 1.1, -3.3, qw(foo -bar), 'There is more than one way to do it!', '-Perl', '+Rules', ;  Output: -2 2 0 0 1 -1 1.1 -1.1 -3.3 3.3 foo -foo -bar +bar There is more than one way to do it! -There is more than one way to do it! -Perl +Perl +Rules -Rules  +4 A: Nobody ever said f(x) had to be the same type. def f(x): if type(x) == list: return -x[0] return [x] f(2) => [2] f(f(2)) => -2  Clever, although works only for defined constraints. +1 A: Although the question said n had to be a 32 bit int, it did not say the parameter or return type had to be a 32 bit int. This should compile in java--in c you could get rid of the != 0 private final long MAGIC_BIT=1<<38; long f(long n) { return n & MAGIC_BIT != 0 ? -(n & !MAGIC_BIT) : n | MAGIC_BIT; }  edit: This actually makes for a really good interview question. The best ones are ones difficult or impossible to answer because it forces people to think it through and you can watch and look for: • Do they just give up? • Do they say it's stupid? • Do they try unique approaches? • Do they communicate with you while they are working on the problem? • Do they ask for further refinements of the requirements? etc. Never just answer behavioral questions unless you have a VERY GOOD answer. Always be pleasant and try to involve the questioner. Don't get frustrated and don't give up early! If you really aren't getting anywhere, try something totally illegal that could work, you'll get nearly full credit. A: How about this: do local function makeFunc() local var return function(x) if x == true then return -var else var = x return true end end end f = makeFunc() end print(f(f(20000)))  +3 A: Here is a solution that is inspired by the requirement or claim that complex numbers can not be used to solve this problem. Multiplying by the square root of -1 is an idea, that only seems to fail because -1 does not have a square root over the integers. But playing around with a program like mathematica gives for example the equation (18494364652+1) mod (232-3) = 0. and this is almost as good as having a square root of -1. The result of the function needs to be a signed integer. Hence I'm going to use a modified modulo operation mods(x,n) that returns the integer y congruent to x modulo n that is closest to 0. Only very few programming languages have suc a modulo operation, but it can easily be defined. E.g. in python it is: def mods(x, n): y = x % n if y > n/2: y-= n return y  Using the equation above, the problem can now be solved as def f(x): return mods(x*1849436465, 2**32-3)  This satisfies f(f(x)) = -x for all integers in the range [-231-2, 231-2]. The results of f(x) are also in this range, but of course the computation would need 64-bit integers. +1 A: f(n) { return IsWholeNumber(n)? 1/n : -1/n }  +1 A: C++ struct Value { int value; Value(int v) : value(v) {} operator int () { return -value; } }; Value f(Value input) { return input; }  A: Similar to the functions overload solution, in python: def f(number): if type(number) != type([]): return [].append(number) else: return -1*number[0]  ALernative: static datamembers A: Python 2.6: f = lambda n: (n % 2 * n or -n) + (n > 0) - (n < 0)  I realize this adds nothing to the discussion, but I can't resist. +1 A: I have another solution that works half of the time: def f(x): if random.randrange(0, 2): return -x return x  +1 A: This is also a solution (but we are bending the rules a little bit): def f(n): if isinstance(n,int): return str(n) else: return -int(n)  +2 A: int f(int n) { static int x = 0; result = -x; x = n; return result; }  This is a one entry FIFO with negation. Of course it doesn't work for the max negative number. +1 quite an answer! A: In Python f=lambda n:n[0]if type(n)is list else[-n]  A: I believe this meets all the requirements. Nothing says that the parameters have to be 32 bit signed integers, only that the value 'n' you pass in is. long long f(long long n) { int high_int = n >> 32; int low_int = n & 0xFFFFFFFF; if (high_int == 0) { return 0x100000000LL + low_int; } else { return -low_int; } }  +1 A: Great question! This took me about 35 secs to think about and write: int f(int n){ static int originalN=0; if (n!=0) originalN=n; return n-originalN; }  Definitely cheating... but definitely works for all values of n, and is simple. x)At first I thought it would only work the first time you called f(f(n)) (because of the static initialization), but it actually works for each successive time as well. +1 Thanks :)Essentially the idea with this answer is that it's a cheeky response to an equally cheeky question. Should one really going hire (or not hire) computer scientists/software engineers based on a question like this? A: Scala : def f(x: Any): Any = x match { case i: Int => new { override def hashCode = -i } case i @ _ => i.hashCode }  Same thing in Java : public static Object f(final Object x) { if(x instanceof Integer) { return new Object() { @Override public int hashCode() { return -(Integer)x; } }; } return x.hashCode(); }  A: C# overloading: string f(int i) { return i.ToString(); } int f(string s) { return Int32.Parse(s) * -1; }  Or object f(object o) { if (o.ToString.StartsWith("s")) return Int32.Parse(s.Substring(1)) * -1; return "s" + i.ToString(); }  +1 A: Another Javascript solution utilizing short-circuits. ​function f(n) {return n.inv || {inv:-n}} f(f(1)) => -1 f(f(-1)) => 1  A: Tcl: proc f {input} { if { [string is integer$input] } {
return [list expr [list 0 - $input]] } else { return [eval$input]
}
}

% f [f 1]
-1


Along the lines of some of the other answers... if it's an integer, return a command that returns the negative of that number. If it's not a number, evaluate it and return the result.

A:

## In Less than 50 characters (C#)

int f(int n) { return (n <= 0) ? n : f(-n); }


### Or easier to read:

static int f(int n) {
if (n <= 0)
return n;
else
return f(-n);
}


### To Test

static void Main(string[] args) {
for (int n = int.MinValue; n < int.MaxValue; n+=1) {
Console.Out.WriteLine("Value: " + n + " Result: " + f(f(n)));
}
}


And it works ( assuming I understand the question properly )

That only works when n is initially positive (or zero). The question clearly states Where n is a 32 bit *signed integer*, meaning n can also start out negative.
A:

This is a C/C++ solution that doesn't utilize any bitwise operators, and doesn't require any math libraries, though it's kind of cheating...

double f(double n)
{
if (n == (double)(int)n)
return n + 0.5;
else
return -(n - 0.5);
}


This works for all 32-bit integers with the single exception of 0x80000000 (since its opposite cannot be stored in the 32-bit integer system). f(f(n)) == -n will always be true except in that one case.

I'm sure there's a simpler and faster way to implement it, though. This was just the first thing that came to mind.

A:

Thought I'd try this one without looking at other people's answers first:

#include <stdio.h>
#include <limits.h>
#include <stdlib.h>

int f(int n) {
if(n > 0) {
if(n % 2)
return -(++n);
else {
return (--n);

}
}
else {
if(n % 2)
return -(--n);
else {
return (++n);

}
}
}

int main(int argc, char* argv[]) {
int n;
for(n = INT_MIN; n < INT_MAX; n++) {
int N = f(f(n));

if(N != -n) {
fprintf(stderr, "FAIL! %i != %i\n", N, -n);
}
}
n = INT_MAX;
int N = f(f(n));
if(N != -n) {
fprintf(stderr, "FAIL! n = %i\n", n);
}
return 0;
}


Output: [nothing]

A:

Lua:

function f(n)
if type(n) == "number" then
return (-number) .. ""
else
return number + 0
end
end

+1  A:

Exploiting JavaScript exceptions.

function f(n) {
try {
return n();
}
catch(e) {
return function() { return -n; };
}
}


f(f(0)) => 0

f(f(1)) => -1

i like it... very clever!
+1  A:

Works except int.MaxValue and int.MinValue

    public static int f(int x)
{

if (x == 0) return 0;

if ((x % 2) != 0)
return x * -1 + (-1 *x) / (Math.Abs(x));
else
return x - x / (Math.Abs(x));
}


Not sure why this was downvoted. For what inputs does it fail?
A:
int func(int a)
{
static int p = 0;
int ret = a;

if ( p ) ret *= -1;
p ^= 1;

return ret;
}
`