Internet Problem Solving Contest

Minus x equals x

For the easy data set, your task was to find a non-zero number that is equal to its negation.

The key trick is that for signed integer data types the set of possible values is asymetric. For example, the smallest possible int is -2³¹ and the largest is 2³¹ - 1. This leaves us with 2³¹ - 1 pairs (x,-x), and two special values: 0 and -2³¹.

The negation of -2³¹ would be 2³¹. However, this does not fit into an int. More precisely, 2³¹ is one larger than the largest allowed value, and this overflows to the smallest allowed value: -2³¹ again.

(Essentially, all computations with b-bit integers are done modulo 2^b in the sense that results that differ by a multiple of 2^b will, due to overflow, be represented by the same bit pattern.)

Note that when comparing less-than-32 bit integer variables in Java, they get promoted to ints. This causes our solution to work only for ints and longs.

The two solutions to this problem are: int x = -2147483648 and long x = -9223372036854775808.

Equality is not transitive

If comparing variables of different types, they are usually first both promoted to the larger of those two types. For example, when comparing a short and an int, the short is cast to an int, and then they are compared.

The problem is that sometimes there is no good choice – the two types can have incomparable ranges of possible values. In that case, the language designers have to pick one of them.

For example, this often happens when comparing an integer data type to a floating point one.

In Java and many other languages, floating point types get precedence. To quote the reference: If either operand is of type double, the other is converted to double. Otherwise, if either operand is of type float, the other is converted to float.

The problem here is that a long is a 64-bit integer, whereas a double only has 53 bits to store the digits. Thus there are values that can be stored in a long but can not be represented exactly in a double. For the same reason, we may lose precision when converting an int into a float.

This can cause two different ints to be converted into the same float. For example, the ints 1234567890 and 1234567891 will.

We can use this to construct a solution to the hard problem. One possible solution is: int x = 1234567890, float y = 1234567890, and int z = 1234567891. Both for x==y and y==z the int is converted to a float, and thanks to the precision loss equality holds. However, with x==z we are comparing two ints, and find that they differ.