Finding the nth Super ugly number

Question

This problem is already present Super Ugly Number

Write a program to find the nth super ugly number.

Super ugly numbers are positive numbers whose all prime factors are in the given prime list primes of size k. For example, [1, 2, 4, 7, 8, 13, 14, 16, 19, 26, 28, 32] is the sequence of the first 12 super ugly numbers given primes = [2, 7, 13, 19] of size 4

But i tried to solve it without seeing the solution, but its failing on certain test cases, like this one

45
[2,3,7,13,17,23,31,41,43,47]

can anyone please point out the mistake.

int nthSuperUglyNumber(int n, vector<int>& primes) {

    int *ugly = new int[n];
    /*first number*/
    ugly[0]=1;
    int i, s=primes.size();
    /*all multiples point to start*/
    vector<int> iterators(s, 0);

    int next_ugly,j, id, t;
    for(i=1;i<n;i++){


        next_ugly=INT_MAX;
        /*find the minimum*/
        id=0;
        for(j=0;j<s;j++){

            t=ugly[iterators[j]]*primes[j];
            /*if current number is less, then it is already added*/
            if(t<=ugly[i-1]){
                iterators[j]++;
                j--; //mistake was here
            }  
            /*check for smallest*/ 
            else if(t<next_ugly){

                id=j;
                next_ugly=t;
            }
        }
        ugly[i]=next_ugly;
        cout<<ugly[i]<<" ";
        iterators[id]++;
    }
    return ugly[n-1];
}

my output

2 3 4 6 7 8 9 12 13 14 16 17 18 21 23 24 26 27 28 31 32 34 
36 39 41 42 43 46 47 48 49 51 52 54 56 62 63 64 68 69 72 78 82 84

It is missing 81

for the input

45
[2,3,7,13,17,23,31,41,43,47]

EDIT: Understood and corrected the mistake.

`int *ugly = new int[n];` -- Why are you not using a `std::vector` here? You're using it in other places, yet the most obvious place to use it, you don't use it. — PaulMcKenzie, Jul 08 '17 at 18:17
A word of advice: don't waste your time with those bogus online competition sites. Read [these fine C++ books](https://stackoverflow.com/questions/388242/the-definitive-c-book-guide-and-list) instead. — Ron, Jul 08 '17 at 18:18
To add, those coding sites don't care about quality code. Any crap that passes their tests is acceptable. In the real world, you wouldn't write code like this. — PaulMcKenzie, Jul 08 '17 at 18:19
well i thought of writing it in c, then changed, but forgot to change that @PaulMcKenzie — trim24, Jul 08 '17 at 18:19
...and you're training stuff you never need for work etc., while not learning the useful things. — deviantfan, Jul 08 '17 at 18:19

Finding the nth Super ugly number

0 Answers0