## A Programming Puzzle

### June 28, 2013

Today’s exercise is a delightful little programming puzzle:

Write a function `f` so that `f(f(n)) = -n` for all integers n.

When I first saw this puzzle, it took me two days before I had the necessary flash of inspiration, then about two minutes to write. Do yourself a favor and don’t peek at the suggested solution until you figure it out yourself.

Your task is to write function `f` as described above. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

### 45 Responses to “A Programming Puzzle”

1. Paul said

Is there something wrong with the solution below, or is this cheating? It works for all integers.

```def f(n):
return n * 1j

for n in range(-10, 10):
assert f(f(n)) == -n
```
2. George said

Not nearly as elegant as Paul’s – but I was happy to have my own aha moment :)

```def f(n):
return 1.0/n if abs(float(n)) >= 1.0 else int(round(-1.0/n,0)) if n else 0
```
3. […] today’s Programming Praxis exercise, our goal is to write a function such that f (f n) = -n. Let’s […]

```f :: Integer -> Integer
f n = n * (2 * mod n 2 - 1) + signum n
```
5. mvaneerde said

My Perl solution:

use strict;

# Write a function
# f
# so that
# f(f(n)) = -n
# for all integers n.

# f(0) = 0
# f(n odd and positive) = n + 1
# f(n odd and negative) = n – 1
# f(n even and positive) = -(n – 1) = -n + 1
# f(n even and negative) = -(n + 1) = -n – 1

sub f(\$);
sub sign(\$);

for my \$n (-5 .. 5) {
print “\$n => “, f(\$n), ” => “, f(f(\$n)), “\n”;
}

sub f(\$) {
my \$n = shift;

return (\$n % 2 ? 1 : -1) * \$n + sign(\$n);
}

sub sign(\$) {
my \$n = shift;

return \$n 0;
}

6. shtipki said

Definitely cheeting, but the perl state variables are so tempting ;)
``` sub fun { my \$a = shift; state \$x = 0; (\$x++ % 2) ? \$a : -\$a; } ```

7. ye said

I didn’t get the above solution, which keeps the constraint that the domain and range of f are the integers.

However, without that implied constraint, there are some other solutions:
Allowing the domain/range of f to be real (floats): f could be given by “return n+0.5 if n is integer, else return – floor(n)”
Allowing the domain/range of f to be complex: f could be given by “return n*i”, where “i” denotes the imaginary value of sqrt(-1)

8. Remember, the constraint is not to use more than 32-bits. If you change the type, then you must encode it into the 32-bit (don’t take advantage of the type-tag in dynamically typed programming languages).

9. magni- said

Ruby solution with some unnecessary monkeypatching on the Fixnum class:

```class Fixnum
def sign
if self == 0
0
elsif self > 0
1
else
-1
end
end
end

def f(n)
if n.even?
n.sign * (n.abs - 1)
else
-n.sign * (n.abs + 1)
end
end
```
10. me said

(define (f n)
(make-rectangular (imag-part n) (- (real-part n))))

11. DarkoP said

def f(n):
return -abs(n)

12. programmingpraxis said

DarkoP: f(f(1)) should return -1, and f(f(-1)) should return 1. Your function returns -1 for both.

13. JP said

My Rackety versions: A programming puzzle: f(f(n)) = -n on jverkamp.com

I coded up about four before checking out what was here and they’re all reasonably well covered. My favorites were the complex number version:

```; Rotate in the complex numbers
(define (f1 n)
(* n 0+1i))
```

And the stateful version:

```; Use a state variable
(define f4
(let ([toggle (make-parameter #t)])
(lambda (n)
(toggle (not (toggle)))
(if (toggle) n (- n)))))
```
14. DarkoP said

@programmingpraxis: yeah, I misunderstood the problem obviously. Sorry about that, I’ll try better next time.

15. Javascript solution:

`f=function(n){ return (n%2===0) ? (n+1)*-1 : n+1 };`

`f=function(n){ if( n%2===0) { return ( n*-1)+n/Math.abs(n); } else {return n+n/Math.abs(n)}};`
17. Lorenzo said

(define (f x)
(if (number? x)
(lambda () (- x))
(x)))

it does not always return a number, but I think it was not required.

18. Anonymous said

def f(n):
return 0 if n == 0 else 1 – n if n % 2 == 0 else n + 1 if n > 0 else n – 1

19. Lucas said

I don’t know if what I did is valid or not, but it works:

Import math
def f (n)
y = n*n
y = math.sqrt (y)
If ((y/n) == -1)
return x
Else
return -x

20. programmingpraxis said

@Lucas: It doesn’t work. In the first place, x is undefined; I assume you meant y. In the second place, y is always positive, so if n is negative the value returned from the “then” clause will be negative, and if n is positive the value returned from the “else” clause will be negative, so this will always return a negative number. Thus, if n is negative, f(f(n)) can never be positive.

21. Sergey said

(define (f n)
( if (number? n) (lambda() (- 0 n))
(n))

@Paul – your solution doesnt seem to be correct. We need f(f(n)= -n where as yours returns n. Or am i missing something.
My solution (C/C++ like)
static run = 0
int f(n)
{
run=1;
return (pow(-1,(run-1))*n);
}

23. ajitd said

static run = 0
int f(n)
{
run++;
return (pow(-1,(run-1))*n);
}

24. wngcsk said

int f(int n){
return (int) Math.pow(-1, n) * n + (-1) * Integer.signum(n);
}

25. Jeremy Loons said

Thanks for the puzzle! I have a different solution;

f(f(n)) = -n for every interger so I set where n the – n so that f(f(-n)) = n but -n = f(f(n)). Therefore:

f(f(n)) = -n f(f(f(f(n)))) = n

oh and the function: :P

int f(n) {
return n;
}

Could anybody inform me if its anywhere near to accepted :-P

26. ravee chauhan said

f(n){
if(n is positive)
n=n*-1;
else
n=n*1;
return n;
}

27. novatech said
```int func(int n)
{
return (n)?pow(-1,abs(n))*n+(-1*n/abs(n)):0;
}
```
28. Joe said

Matlab:

function y = f(n)
if size(n)==1
y(1)=-n;
y(2)=n;
else
y=n(1);
end

29. et said

in bc unix command line :

define f(n)
{
return -1^(2*n – 1 ) * abs(1-n)
}

where abs is defines as:
define abs(n)
{
if(n>=0) return(n)
return(-n)
}

30. et said

i just realized that this solution will not work for zero and down below :(

31. DGriffin said

Is this a valid solution? (c/c++) It works, and is likely how I would code it if I really needed something that did this in the real world.

int t=0;
int f(int n) {
if (t==0) {
++t;
return n*-1;
} else {
t=0;
return n;
}
}

32. DGriffin said

I was able to figure out a marginally simpler solution. And also the sourcecode feature.

```bool t=true;
int f(int n) {
if (t) {
t=!t;
return n*-1;
}
t=true;
return n;
}
```
33. gabriell said

My java solution :)
public static Integer function(Integer n) {
Integer moduloTwo=n % 2;

Boolean evenNumber=null;
evenNumber = moduloTwo==0 ? true: false;

Boolean positive=n>=0? true : false;

//add this number to close the number to Zero
Integer closerToZero=positive ? -1: 1;

if (evenNumber) return n+closerToZero;
else return -n+closerToZero;
}

34. fisherro said

My solution wasn’t nearly as elegant as a few of the others. I stashed the integer in a list.

```(define (f1 n)
(if (list? n)
(- (car n))
(list n)))
```
35. Vish K said

I used Clojure, which is a newer dialect of Lisp.
(defn f [n]
(if (fn? n)
(n)
(fn [] (- n)) ))

Explanation: Line 2 tests if the argument is a function. If true, the func is invoked (sans arguments) on Line3. Else (on Line4) we return a function that is a closure over n.
One can try this out at the Clojure REPL at http://tryclj.com.
> (f 5)
#
> (f (f 5))
-5
> (f (f 6))
-6

36. Fera said

Is as simple as this:

int f( int n ) { return (n>0)?-n:n;}

or

int f( int n ) { return – abs(n); }

37. Sam said

In python… not mathematical at all!

```def f(n):
if isinstance(n, int):
return str(n)
if isinstance(n, str):
return -int(n)

print f(f(3))
>>>-3
print f(f(-6))
>>>6
```
38. Josh said

Another possible python solution:
``` def f(n): try: return n() except: if n <= 0: return n else: return -n```

``` ```

```for n in xrange(-100,100): print f(f(n)) ```

39. said said

call = -1
def f(x):
global call
call = call + 1
return ((-1)**call ) *x

40. George said

doesn’t this solve the issue? (Ruby)

```def f (n)
n < 0 ? n : - n
end
```
41. George said

42. George said
```def f(n)
#my version of a ruby static method variable (similar to C++ static function variables)
\$count = \$count.nil? ? 0 : (\$count + 1)
return -n if \$count.even? || \$count == 0
n
end
```
43. George said

this works too, and its one method call simpler

```def f(n)
#my version of a ruby static method variable (similar to C++ static function variables)
\$count = \$count.nil? ? 0 : (\$count + 1)
return -n if \$count.odd?
n
end
```
44. mvaneerde said

@George: where in the spec did it say the calls to f(1), f(2), etc. would be made in that order?