Recently I tried to solve a question called 'Ugly Number' from LeetCode link. Here is the description.

An ugly number is a positive integer whose prime factors are limited to 2, 3, and 5. Given an integer n, return the nth ugly number.

Here is the right answer:

public int nthUglyNumber(int n) {
    if (n < 7) return n;
    PriorityQueue<Long> heap = new PriorityQueue<>();
    Set<Long> set = new HashSet<>();
    heap.add(1L);
    long res = 1;
    for (int i = 0; i<n; i  ) {
        res = heap.poll();
        long res_2 = res*2;
        long res_3 = res*3;
        long res_5 = res*5;
        if (!set.contains(res_2)) {
            set.add(res_2);
            heap.add(res_2);
        }
        if (!set.contains(res_3)) {
            set.add(res_3);
            heap.add(res_3);
        }
        if (!set.contains(res_5)) {
            set.add(res_5);
            heap.add(res_5);
        }
    }
    return (int) res;
}

Here is my answer:

public int nthUglyNumber(int n) {
    if (n < 7) return n;
    PriorityQueue<Integer> heap = new PriorityQueue<>();
    Set<Integer> set = new HashSet<>();
    heap.add(1);
    int res = 1;
    for (int i = 0; i < n; i  ) {
        res = heap.poll();
        int res_2 = res * 2;
        int res_3 = res * 3;
        int res_5 = res * 5;
        if (!set.contains(res_2)) {
            set.add(res_2);
            heap.add(res_2);
        }
        if (!set.contains(res_3)) {
            set.add(res_3);
            heap.add(res_3);
        }
        if (!set.contains(res_5)) {
            set.add(res_5);
            heap.add(res_5);
        }
    }
    return res;
}

The right answer uses the type 'Long' while I use the type 'Integer'.

I found that when the input is 1407, the right output is 536870912, but my output is -1425014784.

536870912 is less than 2^32 - 1, but why is my output negative?

CodePudding user response：

The right answer is 2^29. As part of the exercise, this is multiplied by 2, 3, and 5. Whilst 2^29 fits in an int, 2^29 * 5 does not!

You still get uniqueness though; these numbers fall in the 2^31-2^32 range, i.e. if they 'overflow' they remain in the negative space. The explanation therefore is not that you overlap.

The storage mechanism heap is a PriorityQueue, meaning, it naturally sorts itself. That's the problem: Those negative numbers sort before. By overflowing, the natural order of that PQ gets messed up as it starts returning the higher numbers (because they overflowed and are deemed negative) when it should be returning the lower ones.

Thus, right before you get to the nth number, there are some negative numbers in the PQ, so the next loop starts returning those instead, thus you get a negative number as an answer.