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.

About these ads

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 […]

  4. My Haskell solution (see http://bonsaicode.wordpress.com/2013/06/28/programming-praxis-a-programming-puzzle/ for a version with comments):

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

  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 };
  16. 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)}};
  17. Lorenzo said

    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.

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

  22. ad said

    @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

    NVM, misread the instructions

  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?

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 621 other followers

%d bloggers like this: