Coding flaws

exercise No. 223

Q:

We consider:

/**
 * Number of handshakes in a group of people.
 *
 * We assume a goup of <code>size</code> people mutually shaking hands with each other. The overall number of handshakes
 * not counting duplicates is then given by size * (size - 1) / 2.
 *
 * <p>Example: Given three people a, b and c we have three handshakes (a with b), (a with c) and (b with c).</p>
 *
 * @param size The group's size.
 * @return The number of mutual handshakes not counting duplicates
 */
static public int getNumberOfHandshakes(int size) {
    return size * (size - 1) / 2;
}

A Programmer examines the above code. He claims a flaw regarding the division by 2. This may lead to loosing precision, e.g. when dividing 3 / 2 truncating 1.5 to 1 as being implemented by Java int division. Answer the following questions:

  1. Is he right? State a reason.

  2. Another programmer claims yet another flaw which might be mitigated a little bit without changing the method's signature. Explain her argument and enhance the above code accordingly.

    Tip

    Consider overflow problems for larger numbers.

A:

  1. Since either of size or size + 1 is even, their product can always be divided by 2 without truncation. The argument is thus wrong.

  2. The problem is about larger group sizes: The square root of Integer.MAX_VALUE roughly equals 46340.95. Starting from 46341 + 1 we encounter overflow problems:

    Code 
    IO.println (getNumberOfHandshakes(46341));
IO.println (getNumberOfHandshakes(46341 + 1));
    Result 
    1073720970
-1073716337

    This can be mitigated by dividing prior to multiplying. However to avoid integer division truncation we must now assure selecting the even one of our two factors for division: 

    static public int getNumberOfHandshakes(int size) {
    if (0 == size % 2) {
       // size is even
       return size / 2 * (size - 1);
    } else {
       // size - 1 is even
       return (size - 1) / 2 * size;
    }
}

    Given the square root of 2 * Integer.MAX_VALUE by ~65535.99998 overflows now happen when starting from 65536 + 1. This is a considerable gain in group size limit by ~41% compared to the current implementation:

    Code 
    IO.println (getNumberOfHandshakes(65536));
IO.println (getNumberOfHandshakes(65536 + 1));
    Result 
    2147450880
-214745088

    Remark: A less elegant but otherwise fully equivalent solution uses long arithmetics internally: 

    static public int getNumberOfHandshakes(int size) {
    return (int) (size * (size - 1L) / 2);
}
Prev  Up  Next
Computing an array's average  Home  2025 winter