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