[Help] N'th Super Ugly Number Leetcode

help
, , ,
1

Question : - LeetCode

I tried many approaches and it gives me TLE for some Test cases , later I found out one solution in python who passes this in 3500 ms , after that (one we AC the code we can view best submissions) , I checked one code in python and convert it into C++ , and it passed in 350 ms only , there is one condition written , please help me to understand this ,(First try with your approach then explain your and mine)

@ssjgz @cubefreak777 @nichke

class Solution {
public:
    int nthSuperUglyNumber(int n, vector<int>& primes) {
        priority_queue<long long int,vector<long long int>,greater<long long int>>pq(primes.begin(),primes.end());
        long long int p=1;
        for(int i=0;i<n-1;i++)
        {
            p=pq.top();pq.pop();
            // cout<<(p)<<" ";
            for(auto prime : primes)
            {
                pq.push(p*prime);
                if(p%prime ==0 )
                    break;
            }
        }
        return p;
    }
};

Explain me this line why we wrote ?

                if(p%prime ==0 )
                    break;

because of this line code get too much faster ?

2

(p%prime==0) makes it so that you’re only multiplying p with the required number of smallest primes instead of all the primes. You do this upto the point where you reach the next prime number in the priority queue.
Since you only need the nth super ugly number, not all of them, this is the optimization.
For example, in the first sample,
i = 0, pq = [2, 7, 13, 19]
i = 1 pq = [4, 7, 13, 19]
i = 2 pq = [7, 8, 13, 19]
Now, we start multiplying this prime (7) until we reach the next prime in pq.
i = 3 pq = [8, 13, 14, 19, 49]
i = 4 pq = [13, 14, 16, 19, 49]
Here’s a run of the 2nd sample with a larger n.
primes = [2, 3, 5]
pq: for each i
2 3 5
3 4 5
4 5 6 9
5 6 8 9
6 8 9 10 15

3

Buddy this is I know , like we are multiplying untill we get a prime which divides the p (popped element) , but I m still not able to understand why?

4

I think this condition states that if p%prime=0 then it means that p is already divisible by prime and pushing p* prime in the heap would mean that we’re adding 2 powers of prime at a single time, which is slow as we’ll anyways be considering this when we have prime*p as the top element in the priority queue

5

Let me explain with an example , Primes =[2,3]
Now pq is {2,3} initially , you see 2 , push 4 , and then break , you see 3 push 6 , push 9 then break . Here you should notice one thing that the condition if(p%prime==0) is stopping us to push a no. twice in the priority queue , hence giving correct answer and reducing time complexity by a huge amount .Actually using that condition or using a set is almost same but u should note one thing that Time complexity of Set is way more than priority queue and also that condition is stopping us from going to unwanted positions .

6

Nope , first we push p*prime , after that this statement working , means untill we got some prime who divides popped element we have to insert , after that we will break

7

exactly but like still I am not clear , I dry run this and found that bcz of this condition we never insert duplicates , I m like wowww , but why not clearly able to understand.

8

You got it wrong, I mean some future iteration of the outer loop in which we’ll be having p*prime as the top element of the priority queue

9

okey , but how will you prove , like I know this thing , by dry run I get to know , but I can’t think just like that , like I m using set , or some loop to remove duplicates , but this condition is just wow , reducing time from TLE to 350 ms is too much .

10

Say K is the size of the primes list so time complexity without the p%prime thing would be \mathcal{O}(NK\times \log (NK)) because you might end up filling a bunch of duplicates in in the priority queue, but once you add in the modulo then the time complexity reduces to \mathcal{O}(NK \log K) since our priority queue won’t blow up anymore because of duplicates.

11

I understand this thing , but Sorry to say i m not able to understand how this line stops duplicates , like if you can prove or something else , obviously suppose same question asked in Interview , how to explain him or like generally the approach using set (on GFG , previous code of LC ) , but this thing how ?

12

This is the correct argument what you’re asking for, try to understand this correctly. Correlate it with a dry run in case you don’t get the idea.

13 
int nthSuperUglyNumber(int n, vector<int>& primes) {
        set <int> s;
        
        s.insert(1);
        
        int cnt=0;
        
        while(cnt<n)
        {
            cnt++;
            
            long long val=*s.begin();
            
            
            s.erase(val);
            
            if(cnt==n)
                return val;
            
            
            for(int i=0;i<primes.size();i++)
            {
                if(val*primes[i]>INT_MAX)
                    break;
                
                if(s.size()+cnt<=n)
                    s.insert(val*primes[i]);
                else
                {
                    if(val*primes[i]>*(--s.end()))
                        break;
                    
                    s.insert(val*primes[i]);
                    s.erase(--s.end());
                }
            }
            
            while(s.size()>0 && s.size()+cnt>n)
                s.erase(--s.end());
            
        }
        return 0;
}

Time comp for this should be O(nlogn) right ?

Is this getting TLE because of large constant factor of set ?

14

correct TLE