Pages

Monday, April 23, 2012

f(f(x)) = -x, A neat Puzzle!

I found this problem in some blog that I don't remember:

The Problem:
Write a C function f(x) that takes an integer x and returns another integer such that f(f(x)) = -x
You are not allowed to use any global variables or static variables or file operations.

The Solution:
Let f(x) = y, then f(y) = -x
so f(-x) = -y                          [ -y = f(f(y)) = f(-x) ]
and f(-y) = x                          [ x = f(f(-x)) = f(-y) ]

f(x) creates a cycle of integers: (x) ==> (y) ==> (-x) ==> (-y) ==> (x)


So, we have to partition the set of natural numbers into cycles of length 4. But, 0 is a special case. f(0) = 0.
For example, one such partition can be:
(1) ==> (2) ==> (-1) ==> (-2) ==> (1)
(3) ==> (4) ==> (-3) ==> (-4) ==> (3)
(5) ==> (6) ==> (-5) ==> (-6) ==> (5)
... and so on

[Edit: the following portion has been added after misof correctly pointed out my mistake]

It is impossible to write a C function that solves the problem completely. We can represent 2^B numbers using B bits. The range is [ -(2^B) to (2^B)-1 ]. Note that, the 2^B doesn't exist in the domain, so, the problem is unsolvable for -(2^B). In fact, there will be another number for which we can't solve it. Let's see why.

Note that, 0 can't be part of a cycle of length 4.

Let, f(0) = 0. That leaves (2^B)-1 numbers to partition into cycles of length 4. But [(2^B)-1]%4 = 3. So, there will be 3 numbers left to be partitioned. We can create a partial cycle with these 3 numbers so that exactly one of them will be matched with it's negative. One of these three numbers will be -(2^B). So, there will be 2 unlucky numbers.

Let, f(0) = x, for some x != 0. If we want f to work for 0, f(x) must map x to 0. We get a cycle of length 2 where x is unlucky. It's better to chose x = -(2^B). That leaves (2^B)-2 numbers. After partitioning into cycles of length 4, 2 numbers will be left: y and -y. We can solve for exactly one of them by assigning f(y) = -y and f(-y) = -y. or vice versa. So, one of these 2 will be unlucky.

In both case, 2 numbers are unlucky!


But the following function partially works for all integers except -(2^31) and (2^31)-1:

int f(int x){
    if(x==0) return 0;

    if(x>0){
        if(x%2==1)
            return x+1;
        else
            return -(x-1);
    }else{
        if((-x)%2==1)
            return x-1;
        else
            return -(x+1);
    }
}

3 comments:

  1. Nice puzzle! But actually, your solution is wrong for both interpretations of the question :)

    If the "-x" is the mathematical "minus x", there is one input for which no program can give the correct output, so in that case the puzzle has no solution.

    The other case is that the "-x" is the C operator "unary minus". That is, the statement of the question is "for all x: (f(f(x)) == -x) must evaluate to true". In this case the puzzle is solvable, but your program does not solve it. There is exactly one x where it fails. And it's not exactly the same x as in the first interpretation, but still the reason why it fails is related. Try to find the bug and fix it :)

    ReplyDelete
    Replies
    1. Actually, I was wrong as well. The puzzle cannot be solved completely in either version. The only solvable version I can think of is the mathematical one, where the input for f is the (infinite) set of all integers. There your formula works.

      Delete
    2. Thanks misof! :)
      I was very excited and thus careless when I got the idea of the solution!

      I am trying to fix the post by showing that it is impossible to solve for B-bit numbers for any B.

      Delete