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