WAP to Generate The Series of Ugly or Lucky Number

Question:Generate The Series of Lucky/Ugly Number or Find the First K Ugly/Lucky Number



eg. 1 2 4 8 10 16 20 25 32 64 100 125 128

Algorithm

Answer: Consider an array of first 10 ugly numbers: {1, 2, 3, 4, 5, 6, 8, 9, 10, 12, , , , }

Next ugly number can be calculated by just multiplying one of all these numbers with 2 or 3 or 5.

The least number whose double is not present in the list is 8 (any number before this has its double present in the list). So one of the candidates for next ugly number is 8*2=16

The least number whose multiple by 3 is not present in the list is 5 (any number before this has its multiplied by 3 present in the list). So other candidate for next ugly number is 5*3 = 15.

The least number whose multiple by 5 is not present in the list is 3 (any number before this has its multiplied by 5 present in the list). So other candidate for next ugly number is 3*5 = 15.

Least of these three numbers (15) is our next ugly number.

Now how to choose next ugly number is pretty simple. Since our ugly number is 15 it means now 3*5 and 5*3 are present in the list. So next numbers whose multiple by 3 and 5 respectively are not present in the list are 6 and 4 respectively. The least number whose double is not present in the list remains unchanged at 8. So next candidates are 8*2, 6*3 and 4*5. We will continue in this manner for further list.
Lucky numbers are numbers whose prime factors are just 2, 3, 5. Find the first k lucky numbers.


Algorithm: Keep 3 pointers with you and keep track whose multiple by 2,3 and 5 are present and whose are not. Choose the least number of next candidates and increase the pointer by 1 for the chosen one. If 2 candidates are same, and we chose that number, increment both the pointers as in example above.


#include
#include
using namespace std;
#define k 20 //modify it

int Lucky[k], ptr2, ptr3, ptr5;

int minimum(int x,int y,int z)
{
if (x return (y}

int nextLucky(int num)
{
int num2,num3,num5;
if(num==0)
{
Lucky[num]=1;
ptr2=ptr3=ptr5=0;
return Lucky[num];
}

num2=Lucky[ptr2]*2;
num3=Lucky[ptr3]*3;
num5=Lucky[ptr5]*5;

Lucky[num]=minimum(num2,num3,num5);

if(Lucky[num]==num2) ptr2++;
if(Lucky[num]==num3) ptr3++;
if(Lucky[num]==num5) ptr5++;

return Lucky[num];
}

int main()
{
int i;

for(i=0; i printf("Lucky number no. %d is %d\n", i+1,nextLucky(i));
}

Dynamic Programming
TC O(n)
SC O(n)
Run Here https://ideone.com/B8rCN


Variation
Google Interview Question in different Way:
Given expression E=(2^i * 5^j), increment i and j to ensure the output is sorted.
so above logic will remain same except we need multiples of 2's & 5's thats it

TC O(n)
SC O(n)
Run Here https://ideone.com/M2Bmz