Mar 122009

Good morning! It’s 5:32 and I haven’t slept yet, not because that I can’t sleep, but there is an interesting problem that I like to work on (though it’s not important at all!).

1. Write ABS function which takes an integer N as input and return the absolute value of N. Your function should be one-liner (one statement) and may contain only +, -, *, /, (, ), numbers, and variable (ie. N). You’re not allowed to call any other functions (including built-in functions).

2. Write MAX function which takes two integers A and B as input and return the largest value between A and B. Your function should also be one-liner and may contain only +, -, *, /, (, ), numbers, and variables (ie. A and B). You’re allowed only to call one function: ABS.

It took me a while to figure out how to write such ABS function. I googled several sites and found only ABS function that exploit negative numbers’ representation in computer, which means it needs bitwise operator such as << and >> (breaking the rule!), and there’s also compiler problem (16-bit or 32-bit).

Here is my solution for ABS:

int abs(int n) { return n * ((2 * ((n*n+n)/(n*n+1))) - 1); }

The key idea is to multiply n by 1 if n > 0, and multiply n by -1 if n ≤ 0. Then the problem is, how to map any n > 0 into 1 while any n by -1 if n ≤ 0 will be mapped into -1 by the same operation?

n2 + n :: always give a non-negative result for any integer n.
n2 + 1 :: always give a positive result for any integer n (it’s important to have a non-zero function as denominator).
(n2 + n) / (n2 + 1) :: always give 1 if n > 0, because (p2 + p) ≥ (p2 + 1) and (p2 + p) < 2 * (p2 + 1) for any positive integer p (n = p).
(n2 + n) / (n2 + 1) :: always give 0 if n ≤ 0, because (p2 – p) < (p2 + 1) and 0 ≤ (p2 – p) for any non-negative integer p (n = -p).

From (n2 + n) / (n2 + 1), we will receive either 1 (if n > 0) or 0 if (if n ≤ 0). Mapping {1, 0} into {1, -1} is an easy task :-D.

For the second question (MAX), there is a simple solution which use ABS function:

int max(int a, int b) { return (a + b + abs(a - b)) / 2; }

I’d like to know if there is any easier way to do ABS or MAX, but I can’t think straight right now… okay, good night!!

EDIT: grammar (flanflygirl)

  9 Responses to “ABS and MAX”

  1. Woow…excellent article!!
    tidak sia2 ilmu algorithmny πŸ˜€
    good luck my teacher!! n always be better man…

  2. wah grammar nya diedit si fio

  3. …………………………………………….. swt

  4. suuuuuuuuuuuuuu…..
    miss u……huhuhuhuhuhu kmana aja engkau…

  5. @flanflygirl: super wultra tremendous?

    @OnO: i’m here πŸ˜€

  6. pas bener lo reply nya tgl 23…hehehe ^^ dah ga d binus lagi ya?

  7. klo model gini boleh?

    inline int abs(const int n)
    return (n b) ? a : b;

  8. sori submit lagi, postingan sebelumnya formatnya kacau.

    inline int abs(const int n)
    return (n b) ? a : b;

 Leave a Reply

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>