## A Programming Puzzle

### June 28, 2013

The function has to do two different things on the two calls. It took me two days to figure out that I could encode the desired action by handling odd numbers and even numbers separately. The key insight is to separate the sign and magnitude of the number by the parity of the number. So there are three rules:

1) If the number is even, it keeps the same sign and moves 1 closer to 0; thus, subtract 1 from a positive even number and add 1 to a negative even number.

2) If the number is odd, it changes sign and moves 1 farther from 0; thus, multiply by -1 and subtract 1 from a positive odd number and multiply by -1 and add 1 to a negative even number.

3) As a special case, 0 is unchanged; it has no sign, so it can’t change its sign.

Here’s the function:

```(define (f n)   (cond ((and (positive? n) (even? n)) (- n 1))         ((and (negative? n) (even? n)) (+ n 1))         ((and (positive? n) (odd? n)) (- (- n) 1))         ((and (negative? n) (odd? n)) (+ (- n) 1))         (else 0)))```

And here are some examples:

```> (f (f -3)) 3 > (f (f -2)) 2 > (f (f -1)) 1 > (f (f 0)) 0 > (f (f 1)) -1 > (f (f 2)) -2 > (f (f 3)) -3```

You can run the program at http://programmingpraxis.codepad.org/OIoOHeXc.

The source where I found this question claims it was asked at a job interview. I find that hard to believe. Either you get the “Aha!” insight or you don’t, or else you’ve heard and solved the puzzle previously. In any case, the interviewer learns nothing about you. Terrible interview question.

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?