Super Ugly Number ( Number whose prime factors are in given set ) | C ++ program for super ugly number ; function will return the nth super ugly number ; n cannot be negative hence return - 1 if n is 0 or - ve ; Declare a min heap priority queue ; Push all the array elements to priority queue ; once count = n we return no ; Get the minimum value from priority_queue ; If top of pq is no then don 't increment count. This to avoid duplicate counting of same no. ; Push all the multiples of no . to priority_queue ; cnt += 1 ; ; Return nth super ugly number ; Driver program to test above functions
#include <bits/stdc++.h> NEW_LINE using namespace std ; int ugly ( int a [ ] , int size , int n ) { if ( n <= 0 ) return -1 ; if ( n == 1 ) return 1 ; priority_queue < int , vector < int > , greater < int > > pq ; for ( int i = 0 ; i < size ; i ++ ) { pq . push ( a [ i ] ) ; } int count = 1 , no ; while ( count < n ) { no = pq . top ( ) ; pq . pop ( ) ; if ( no != pq . top ( ) ) { count ++ ; for ( int i = 0 ; i < size ; i ++ ) { pq . push ( no * a [ i ] ) ; } } } return no ; } int main ( ) { int a [ 3 ] = { 2 , 3 , 5 } ; int size = sizeof ( a ) / sizeof ( a [ 0 ] ) ; cout << ugly ( a , size , 10 ) << endl ; return 0 ; }