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.
Programming Praxis 
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)) == -nNot 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[…] today’s Programming Praxis exercise, our goal is to write a function such that f (f n) = -n. Let’s […]
My Haskell solution (see http://bonsaicode.wordpress.com/2013/06/28/programming-praxis-a-programming-puzzle/ for a version with comments):
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;
}
Definitely cheeting, but the perl state variables are so tempting ;)
sub fun {
my $a = shift;
state $x = 0;
($x++ % 2) ? $a : -$a;
}
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)
See: https://www.informatimago.com/articles/ffn=-n/index.html
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).
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(define (f n)
(make-rectangular (imag-part n) (- (real-part n))))
def f(n):
return -abs(n)
DarkoP: f(f(1)) should return -1, and f(f(-1)) should return 1. Your function returns -1 for both.
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:
And the stateful version:
; Use a state variable (define f4 (let ([toggle (make-parameter #t)]) (lambda (n) (toggle (not (toggle))) (if (toggle) n (- n)))))@programmingpraxis: yeah, I misunderstood the problem obviously. Sorry about that, I’ll try better next time.
Javascript solution:
f=function(n){ return (n%2===0) ? (n+1)*-1 : n+1 };Slight adjustment, please ignore previous entry:
f=function(n){ if( n%2===0) { return ( n*-1)+n/Math.abs(n); } else {return n+n/Math.abs(n)}};What about the following scheme?
(define (f x)
(if (number? x)
(lambda () (- x))
(x)))
it does not always return a number, but I think it was not required.
def f(n):
return 0 if n == 0 else 1 – n if n % 2 == 0 else n + 1 if n > 0 else n – 1
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
@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.
(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);
}
static run = 0
int f(n)
{
run++;
return (pow(-1,(run-1))*n);
}
int f(int n){
return (int) Math.pow(-1, n) * n + (-1) * Integer.signum(n);
}
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
f(n){
if(n is positive)
n=n*-1;
else
n=n*1;
return n;
}
int func(int n) { return (n)?pow(-1,abs(n))*n+(-1*n/abs(n)):0; }Matlab:
function y = f(n)
if size(n)==1
y(1)=-n;
y(2)=n;
else
y=n(1);
end
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)
}
i just realized that this solution will not work for zero and down below :(
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;
}
}
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; }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;
}
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)))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
Is as simple as this:
int f( int n ) { return (n>0)?-n:n;}
or
int f( int n ) { return – abs(n); }
oops!
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)) >>>6Another 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))
call = -1
def f(x):
global call
call = call + 1
return ((-1)**call ) *x
doesn’t this solve the issue? (Ruby)
NVM, misread the instructions
this works too, and its one method call simpler
@George: where in the spec did it say the calls to f(1), f(2), etc. would be made in that order?