PROBLEM LINK:Author: D. Vishnu Vardhan reddy Tester: D. Vishnu Vardhan reddy Editorialist: D. Vishnu Vardhan reddy DIFFICULTY:Easy PREREQUISITES:PROBLEM:Given an array P of prime numbers , find the Nth number that has its prime factors in P. EXPLANATION:We can generate the sequence by multiplying the prime factors with the numbers in the sequence itself and finding the minmum in each step. for example consider prime factors P = [2,3,5], and the quantity to find n = 5 Let k be size of given array of prime numbers. Declare a list for sequence. 1)Insert first number (which is always 1) into list. 2)Initialize array multipler[k] of size k with 0. Each element of this array is iterator for corresponding prime in primes[k] array. 3)Initialize nextMultipe[k] array with primes[k]. This array behaves like next multiple variables of each prime in given primes[k] array i.e; nextMultiple[i] = primes[i] * sequence[++multiple_of[i]]. 4)Now loop until there are n elements in sequence.
Example tracing: p=[2,3,5], n = 5 Let for easy understanding ,multiplier[]= i2,i3,i4 initialize sequence[] =  1  i2 = i3 = i5 = 0; First iteration sequence[1] = Min(sequence[i2]2, sequence[i3]3, sequence[i5]*5)
sequence[] =  1  2  i2 = 1, i3 = i5 = 0 (i2 got incremented ) Second iteration
Third iteration
Fourth iteration
Fifth iteration
AUTHOR'S AND TESTER'S SOLUTIONS:Author's solution can be found here. asked 13 Sep, 20:53
