[Stack Overflow]Design a function f, such that f(f(n)) == -n

http://stackoverflow.com/a/824878

Paraphrased: defining such a function over a symmetric subset of the reals X is equivalent to partitioning the positive (>0) elements of X into disjoint pairs (a,b). This uniquely describes a satisfying function f, under whose action:

    f:  0 -> 0
    f:  a -> (-b) -> (-a) -> b -> a

There is no such partition on the set of int32_t's, because the # of nonzero int32_t's is odd.

For the set of all integers Z, the "obvious" partition is {(1,2), (3,4), (5,6)...}. This is what many of the answers are getting at with even/odd tests.

This also works for some subsets of the integers, such as {-2,1,0,1,2}. These are the symmetric ones with an even number of positive elements. These have 4n or 4n+1 elements total, depending on whether they include zero. [-2^31, 2^31] works (this has one more element than int32_t). As does [-2^31 + 2, 2^31 - 2] -- the largest such subset of int32_t.

This has a natural extension to the rationals, the reals, etc. Namely: (a,b) is a member of the partition iff (floor(a), floor(b)) is a member of the partition for integers, and their fractional parts are equal.

There is no such function on the reals that is (analytically) continuous. Any such f must be bijective (a != b implies f(a) != f(b)). If f : R -> R is both continuous and bijective, it is monotonic, and therefore so is (f . f), which is incompatible with the requirement that (f . f)(x) = -x.

Honestly, can anyone tell me exactly in what kind of a programming scenario do you have to write a function where f(f(n)) comes out to -n? This is more a math question than a programming one and unless you are expected to do a lot of complex math in your job I don't think such a question is appropriate for a programmer's interview.

    function f(n) { return -Math.abs(n) }

    function f(n) { return -n[0] || [n] }

Where i=sqrt(-1), either would do.

Without proper constraints, the problem is trivial. The fact that the variable is called 'n' means nothing.

OTOH, if f is integer-valued and of an integer variable,

    f(0)=0
    f(2n)=-(2n-1)
    f(2n-1)=2n
    f(-(2n-1))=-2n
    f(-2n)=2n-1

The difficult one is f(f(n))=n^2.

    /*
     * f(f(n)) = -n
     */

    #include <stdlib.h>
    #include <stdio.h>
    #include <stdint.h>
    
    int32_t f(int32_t n) {
        return (2 * (n & 1) - 1) * n + (2 * ((n & 1) & ((n >> 31) & 1)) - 1);
    }
    
    int main(int argc, char** argv) {
        int32_t n[] = { 1, 2, 3, -1, -2, -3, 0, 5, 6, 10, 20, 50, 0x7fffffff, 0x80000000 };
        int count = sizeof(n) / sizeof(int32_t);
        for (int i = 0; i < count; i++) {
            printf("      f(%d) = %d\n      f(f(%d)) = %d\n", n[i], f(n[i]), n[i], f(f(n[i])));
        }
    }
    

      f(1) = 0
      f(f(1)) = -1
      f(2) = -3
      f(f(2)) = -2
      f(3) = 2
      f(f(3)) = -3
      f(-1) = 0
      f(f(-1)) = -1
      f(-2) = 1
      f(f(-2)) = 0
      f(-3) = -2
      f(f(-3)) = 1
      f(0) = -1
      f(f(0)) = 0
      f(5) = 4
      f(f(5)) = -5
      f(6) = -7
      f(f(6)) = -6
      f(10) = -11
      f(f(10)) = -10
      f(20) = -21
      f(f(20)) = -20
      f(50) = -51
      f(f(50)) = -50
      f(2147483647) = 2147483646
      f(f(2147483647)) = -2147483647
      f(-2147483648) = 2147483647
      f(f(-2147483648)) = 2147483646

http://play.golang.org/p/FgZp8xNfPt

  #include <stdio.h>

  /* works for all signed integers, but isn't particularly  useful */
  int f(int n)
  {
      static int b;
      return b = !b ? n : -n;
  }

  int main()
  {
      int n=-1234;
      /* int n=1234; */
      printf("%d\n", f(f(n)));
  }

f = negate . abs

That way f always returns a negative regardless of input.

    function f(n) {
        if (typeof n == 'object')
            return -1 * n.val;
        else
            return {val: n};
    }

https://gist.github.com/richardkiss/5857101

(defmacro f (n)

  (cond ((numberp n) n)
              ((not (listp n)) (error "not a number"))
              ((equal (car n) 'f) `(* -1 ,n))
              (t n)))

  int f(int n) {
    static int timesCalled = 0;
    return ++timesCalled % 2 ? n : -n;
  }