847

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?

1
  • 6
    What job was this interview for?
    – tmaj
    Commented Aug 1, 2017 at 23:17

120 Answers 120

445

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()
9
  • 23
    Cool, I love this... the same approach in JavaScript: var f = function(n) { return (typeof n == 'function') ? n() : function() { return -n; } } Commented Apr 9, 2009 at 2:17
  • 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. Commented Apr 9, 2009 at 9:31
  • 11
    Would the average interviewer even know what a lambda construct is? Commented Aug 26, 2009 at 21:00
  • 4
    Of course, such a type-cheating trick also works in Haskell, even though it's static: class C a b | a->b where { f :: a->b }; instance C Int (()->Int) where { f=const.negate }; instance C (()->Int) Int where { f=($()) }. Commented Mar 16, 2013 at 20:39
  • 4
    What? Where did you get the idea that typeof f(n) === 'function', especially, where n is a number and you expect a number returned? I don't understand how could an instance case apply here. I don't speak Python well, but in JS checking argument for a function type is plain wrong in this case. Only numeric solution applies here. f is a function, f(n) is number.
    – Harry
    Commented Apr 25, 2013 at 13:09
378

How about:

f(n) = sign(n) - (-1)ⁿ * n

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.


To make it work for real numbers you need to replace the n in (-1)ⁿ with { ceiling(n) if n>0; floor(n) if n<0 }.

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));
}
30
  • 10
    Broken for -1, because -1 * 0 is still 0 Commented Apr 8, 2009 at 21:25
  • 3
    No it isn't. f(-1) = 0. f(0) = 1 Commented Apr 8, 2009 at 21:34
  • 5
    It is broken for 1 however. f(1) = 0. f(0) = 1 Commented Apr 8, 2009 at 21:35
  • 18
    Hmm, saving state with even and odd numbers, I should've thought of that.
    – Unknown
    Commented Apr 8, 2009 at 22:25
  • 38
    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.
    – isekaijin
    Commented Apr 13, 2009 at 2:39
290

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):

We must have f(0) = 0. (Proof: Suppose f(0) = x. Then f(x) = f(f(0)) = -0 = 0. Now, -x = f(f(x)) = f(0) = x, which means that x = 0.)

Further, for any x and y, suppose f(x) = y. We want f(y) = -x then. And f(f(y)) = -y => f(-x) = -y. To summarize: if f(x) = y, then f(-x) = -y, and f(y) = -x, and 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.)

9
  • 30
    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.
    – Kyle Simek
    Commented May 10, 2009 at 15:59
  • Nice observation, that there is an odd number of nonzero integers in any n signed bits. Commented Jun 9, 2010 at 5:18
  • This would be my answer too, but beware of the edge case n = -2147483648 (minimum value); you can't abs(n) in that case, and the result will be undefined (or an exception). Commented Nov 29, 2011 at 22:50
  • 1
    @a1kmm: Sorry, -2³² above should have been -2³¹. Anyway, the case where f(0)≠0 (and so f(0)=-2³¹) is actually the easier case, as we showed these two are disconnected from the rest. The other case we need to consider is that f(0)=0, but f(x)=-2³¹ for some x≠0, x≠-2³¹. In that case, f(-2³¹)=f(f(x))=-x (note -x can't be -2³¹, because no such x exists). Further let f(-x)=y. Then f(y)=f(f(-x))=x. Again y can't be -2³¹ (as f(y)=x, but f(-2³¹)=-x, and x is not 0). So, -2³¹=f(x)=f(f(y))=-y, which is impossible. So indeed 0 and -2³¹ must be disconnected from the rest (not the image of anything else). Commented Jun 25, 2013 at 14:52
  • 1
    @will There are no signed zeros, if (as I assume) we're talking about two's-complement 32-bit integers.
    – goffrie
    Commented Jun 26, 2013 at 0:49
149

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));
}
7
  • 4
    Unfortunately, because of name mangling, the functions you call "f" actually have weirder names.
    – isekaijin
    Commented Apr 11, 2009 at 2:28
  • 1
    I've thought of something like that, but thinking in C, this was thrown away... good job! Commented May 4, 2009 at 15:47
  • @Rui Craverio: It wouldn't work in .NET 3.5+ because the author chose to use the var keyword as a variable name.
    – Kredns
    Commented Jun 3, 2009 at 21:40
  • 75
    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() ... "
    – elcuco
    Commented Aug 25, 2009 at 20:49
  • 4
    @elcuco Technically, of course, but logically it's one function with multiple overloads (you can do f(f(42)) with that). Since the definition doesn't say anything about parameters and return value, I can hardly accept it as a technical definition.
    – Mark Toman
    Commented Jun 25, 2013 at 15:04
137

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;
}
7
  • 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 ;-)
    – Skizz
    Commented Apr 9, 2009 at 17:50
  • 25
    @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!
    – Dan Olson
    Commented Apr 10, 2009 at 9:49
  • 10
    Skizz always abuses preprocessor :D Commented Jul 29, 2009 at 15:45
  • 23
    This is not a function ..so this is not a valid solution
    – smerlin
    Commented Mar 18, 2010 at 22:47
  • 3
    @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.
    – Jon Purdy
    Commented Apr 26, 2010 at 16:11
106

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.

8
  • Doesn't meet the criteria: abs(abs(n)) != -n
    – Dan Olson
    Commented Apr 8, 2009 at 21:11
  • 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. Commented Apr 8, 2009 at 21:12
  • 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 Commented Apr 8, 2009 at 21:13
  • 20
    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. Commented Jun 9, 2010 at 5:26
  • 1
    I really like the abs-solution for negative numbers. Simple and easily understood. Commented Jan 19, 2011 at 6:47
102

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.

alt text

8
  • 4
    @geschema, what tool did you use to create those nice graphics?
    – jwfearn
    Commented Apr 12, 2009 at 17:24
  • 10
    Sorry, the question says explicitly no complex numbers.
    – user75690
    Commented Apr 13, 2009 at 18:54
  • 6
    @Liran: I used OmniGraffle (Mac-only)
    – geschema
    Commented May 5, 2009 at 10:40
  • 40
    +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.
    – jrista
    Commented Sep 26, 2009 at 2:00
  • 1
    @jrista all the solutions use a second dimension, which is all that 'complex numbers' really are (most use odd vs even, & above uses float vs int). The '4 element ring' that many answers describe necessitates 4 states, which can be represented as 2 dimensions each with 2 states. The problem with this answer is that it requires additional processing space (only 'works' for -64..63, yet needs -128..127 space) and doesn't explicitly state written formula! Commented Nov 29, 2011 at 23:01
68

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));
    }

pictorial

4
  • Not sure why this was downvoted. For what inputs does it fail? Commented Jun 27, 2010 at 9:14
  • Why don't you use the signum function?!?
    – comonad
    Commented Jul 9, 2011 at 15:52
  • 1
    The image is really good. Send 0 to 0 and -2147483648 to -2147483648 since these two numbers are fixed points for the negation operator, x => -x. For the rest of the numbers, follow the arrows in the image above. As is clear from SurDin's answer and its comments, there will be two numbers, in this case 2147483647 and -2147483647 with no other pair left to swap with. Commented Jun 28, 2013 at 21:22
  • It looks like a smiley - with lot of wrinkles
    – Anshul
    Commented Mar 14, 2014 at 7:04
50

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...

2
  • 2
    Yeah, I was working on a similar approach. You beat me to it though. +1 :) Commented Apr 8, 2009 at 21:57
  • 1
    Very clever! This is very close to (& effectively the same as) using complex numbers, which would be the obvious & ideal solution but it explicitly disallowed. Working outside the range of allowable numbers. Commented Aug 25, 2009 at 22:34
49

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;
}
9
  • The latter doesn't mean the requirement of "a"(singular) function. :)
    – Drew
    Commented Apr 8, 2009 at 23:26
  • Remove the second half of the answer and this is a correct answer. Commented Apr 8, 2009 at 23:59
  • @Drew which is why I mentioned that it may break the rules
    – cobbal
    Commented Apr 9, 2009 at 0:09
  • 2
    In JavaScript, a function is an object and so can keep a state.
    – Nosredna
    Commented Jun 3, 2009 at 21:00
  • 1
    IMO: function f(n){ return n.passed ? -n.val : {val:n, passed:1} } is more readable and shorter.
    – SamGoody
    Commented Jun 25, 2013 at 9:44
46

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.

6
  • 1
    I believe it does work for MAX_INT since that's always odd. It doesn't work for MIN_INT and -1. Commented May 5, 2009 at 13:22
  • 9
    It's not a function if it has side effects.
    – nos
    Commented Aug 7, 2009 at 16:47
  • 12
    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...
    – Ryan Lundy
    Commented Aug 26, 2009 at 20:47
  • +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.
    – phkahler
    Commented Feb 15, 2010 at 2:39
  • 2
    @nos: Yes it is, it just isn't referentially transparent. Commented Sep 11, 2010 at 3:49
27

Exploiting JavaScript exceptions.

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

f(f(0)) => 0

f(f(1)) => -1

2
  • I doubt exceptions have been used like this before... :)
    – NoBugs
    Commented Apr 6, 2013 at 2:57
  • +1 Out of the box thinking. Cool! But in production code I would use typeof just to be safe.
    – user235273
    Commented Jun 25, 2013 at 10:44
23

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
21

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;
}
1
  • 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.
    – Imbue
    Commented Apr 10, 2009 at 9:39
20

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).

19

Uses globals...but so?

bool done = false
f(int n)
{
  int out = n;
  if(!done)
  {  
      out = n * -1;
      done = true;
   }
   return out;
}
7
  • 3
    Not sure that this was the intention of the question asker, but +1 for "thinking out of the box". Commented May 4, 2009 at 15:40
  • 5
    Instead of conditionally saying "done = true", you should always say "done = !done", that way your function can be used more than once.
    – Chris Lutz
    Commented Jul 27, 2009 at 5:27
  • @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).
    – nsayer
    Commented Apr 26, 2010 at 16:06
  • 1
    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.
    – Alderath
    Commented Jul 12, 2010 at 7:45
  • 3
    Technically, anything that maintains state is not a function, but a state machine. By definition, a function always gives the same output for the same input.
    – Ted Hopp
    Commented Dec 19, 2011 at 7:14
19

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, 'foo' '-bar';

Output:

-2 2
0 0
1 -1
1.1 -1.1
-3.3 3.3
foo -foo
-bar +bar
3
  • But it doesn't keep it an int. You are essentially storing global variable data in the int "n" itself... except it's not an int otherwise you couldn't do that. For example if n was a string I could make 548 becomes "First_Time_548" and then the next time it runs through the function... if (prefix == First_Time_") replace "First_Time_" with "-" Commented Jul 13, 2014 at 4:49
  • @AlbertRenshaw Not sure where you get those ideas. (1) There are definitely no global variables involved here. (2) If you give the function an int, you'll get an int back -- or a reference to an int, if you call the function an odd number of times. (3) Perhaps most fundamentally, this is Perl. For all practical purposes, ints and strings are fully interchangeable. Strings that like look like numbers will function perfectly well as numbers in most contexts, and numbers will happily stringify whenever asked.
    – FMc
    Commented Jul 13, 2014 at 14:50
  • Sorry I don't know much perl it seemed you were using a global array haha Commented Jul 13, 2014 at 17:50
18

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
0
16

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.

5
  • 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. Commented Nov 23, 2009 at 16:25
  • 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). Commented Nov 23, 2009 at 17:11
  • 1
    @DrJokepu - Wow, after six months--jinx! Commented Nov 23, 2009 at 17:12
  • Don't you just need to convert the numbers to sign-and-magnitude representation inside the function, perform the transformation, then convert back to whatever the native integer representation is before returning it? Commented Nov 23, 2010 at 23:43
  • I like that you basically implemented complex numbers by introducing an imaginary bit :)
    – jabirali
    Commented Dec 7, 2011 at 9:14
16

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.

15

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. ;-)

4
  • 7
    You are lucky they asked for 32 int, if it was 64 bit the interview will never continue after you run the tests ;-)
    – alex2k8
    Commented Apr 13, 2009 at 12:39
  • 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.
    – peSHIr
    Commented Apr 14, 2009 at 9:26
  • 7
    Don't follow this advice in an actual interview. The interviewer expects you to actually answer the question. Questioning the relevance of the question won't buy you anything but it may annoy the interviewer. Designing a trivial test does not bring you any step closer to the answer, and you can't run it in the interview. If you get extra information (32 bit), try to figure out how that could be useful. Commented Jun 25, 2013 at 8:23
  • 1
    An interviewer that gets annoyed when I ask for more information (while possibly questioning the relevance of his question in the process) is not an interviewer I necessarily want to be working for/with. So I will keep asking questions like that in interviews. If they don't like it, I'll probably end the interview to stop wasting both of our time any further. Don't like the "I was only following orders" mind set one bit. Do you..?
    – peSHIr
    Commented Aug 16, 2013 at 11:08
13

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
2
  • This also doesn't work for f(0) which is 1073741824. f(1073741824) = 0. f(f(1073741824)) = 1073741824
    – Dinah
    Commented Aug 26, 2009 at 16:02
  • 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.
    – slacker
    Commented Aug 27, 2010 at 16:15
12

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)
0
12

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 peek 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.

1
  • 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(int& n) { static int* addr = &n; if (addr == &n) { return -n; } return n; } Commented Jun 28, 2010 at 8:27
11

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

2
  • This would be more complex but no more effective than the current best answer Commented Apr 8, 2009 at 21:15
  • 1
    @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. Commented Apr 9, 2009 at 11:19
10

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
}
0
10

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)
3
  • 1
    What about byte-order across different architectures?
    – Steven
    Commented Aug 25, 2009 at 21:02
  • 1
    All the arithmetic is 32-bit. I do not manipulate individual bytes, so byte order will not affect it.
    – finnw
    Commented Aug 25, 2009 at 22:01
  • This sounds pretty close. You can assume the input is 2-complement. So you convert to the sign bit representation. Now depending on the last bit, you flip the first bit and the last bit or just the last bit. Basically you negate only even numbers and cycle even/odd all the time. So you get back from odd to odd and even to even after 2 calls. At the end you convert back to 2-complement. Have posted the code for this somewhere below. Commented Jun 25, 2013 at 8:29
9

:D

boolean inner = true;

int f(int input) {
   if(inner) {
      inner = false;
      return input;
   } else {
      inner = true;
      return -input;
   }
}
1
  • 5
    Might also get you a discussion on why global variables are bad if they don't kick you out of the interview right there!
    – palswim
    Commented Aug 12, 2010 at 22:49
9
return x ^ ((x%2) ? 1 : -INT_MAX);
0
7

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.

5
  • 6
    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. Commented Apr 21, 2009 at 3:41
  • 5
    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
    Commented May 31, 2009 at 15:30
  • @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.
    – Yoo
    Commented Jun 1, 2009 at 7:13
  • So can't he just do the steps twice instead of once?
    – Nosredna
    Commented Jun 3, 2009 at 21:02
  • 4
    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.
    – redtuna
    Commented Jun 22, 2010 at 20:40

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