Designing function f(f(n)) == -n

math integer
Hrvoje Prgeša picture Hrvoje Prgeša · Apr 8, 2009 · Viewed 82.6k times · Source

A question I got on my last interview:

Design a function f, such that:

f(f(n)) == -n

Where n is a 32 bit signed integer; you can't use complex numbers arithmetic.

If you can't design such a function for the whole range of numbers, design it for the largest range possible.

Any ideas?

Answer

viraptor picture viraptor · Apr 8, 2009

You didn't say what kind of language they expected... Here's a static solution (Haskell). It's basically messing with the 2 most significant bits:

f :: Int -> Int
f x | (testBit x 30 /= testBit x 31) = negate $ complementBit x 30
    | otherwise = complementBit x 30

It's much easier in a dynamic language (Python). Just check if the argument is a number X and return a lambda that returns -X:

def f(x):
   if isinstance(x,int):
      return (lambda: -x)
   else:
      return x()

Related questions

Safest way to convert float to integer in python?

Python's math module contain handy functions like floor & ceil. These functions take a floating point number and return the nearest integer below or above it. However these functions return the answer as a floating point number. For example: import …

Read More
Mapping two integers to one, in a unique and deterministic way

Imagine two positive integers A and B. I want to combine these two into a single integer C. There can be no other integers D and E which combine to C. So combining them with the addition operator doesn't work. …

Read More
How to handle very large numbers in Java without using java.math.BigInteger

How would I go about doing arithmetic, + - / * % !, with arbitrarily large integers without using java.math.BigInteger? For instance, the factorial of 90 returns 0 in Java. I would like to be able to solve that.

Read More