Why my Java solution fails?


  • 0
    W

    My solution works for almost all cases, but seems to fail for one-odd cases.
    This is the input it fails for:
    n = 14669
    primes = [7,19,29,37,41,47,53,59,61,79,83,89,101,103,109,127,131,137,139,157,167,179,181,199,211,229,233,239,241,251]

    public class Solution {
        public int nthSuperUglyNumber(int n, int[] primes) {
            int[] factors = new int[n+1];
            if (n==1) return 1;
            factors[0] = 1;
            Queue<Integer> pq = new PriorityQueue<>();
            
            for (int i = 1; i < n; i++) {
                int prev = factors[i-1];
                for (int j : primes) {
                    int k = prev * j;
                    if (k > prev) pq.offer(k);
                }
                while (!pq.isEmpty() && pq.peek() <= prev) pq.poll();
                factors[i] = pq.poll();
            }
            return factors[n-1];
        }
    }
    

    Essentially, I keep a Proirity Queue of the numbers as I multiple them, then take the smallest number for the next position. The idea is that each position is obtained by multiplying one of the previous results with a prime number.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.