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

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.

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

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

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

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

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

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.

DeleteThanks misof! :)

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