Sort the digits to 'wxyz', where each letter is a 0-9 digit. 'wxyz' - 'zyxw' = 999(w - z) + 90(x - y) w - z is between 1 and 9, since w > z (we have ruled out

Sort the digits to 'wxyz', where each letter is a 0-9 digit. 'wxyz' - 'zyxw' = 999(w - z) + 90(x - y) w - z is between 1 and 9, since w > z (we have ruled out numbers like 1111). x - y is between 0 and 9. So there are at most 90 such numbers. In fact there are fewer because x-y <= w-z. This is why there are many collisions in the first step.