### 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.

```
a) Find minimum among current multiples of primes in nextMultiple[] array and insert it in the list of the sequence.
b) Then find this current minimum is multiple of which prime .
c) Increase iterator by 1 i.e; ++multipler[i], for next multiple of current selected prime and update nextMultiple for it.
```

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)

```
= Min(2, 3, 5)
= 2
```

sequence[] = | 1 | 2 |

i2 = 1, i3 = i5 = 0 (i2 got incremented )

Second iteration

```
sequence[2] = Min(sequence[i2]*2, sequence[i3]*3, sequence[i5]*5)
= Min(4, 3, 5)
= 3
sequence[] = | 1 | 2 | 3 |
i2 = 1, i3 = 1, i5 = 0 (i3 got incremented )
```

Third iteration

```
sequence[3] = Min(sequence[i2]*2, sequence[i3]*3, sequence[i5]*5)
= Min(4, 6, 5)
= 4
sequence[] = | 1 | 2 | 3 | 4 |
i2 = 2, i3 = 1, i5 = 0 (i2 got incremented )
```

Fourth iteration

```
sequence[4] = Min(sequence[i2]*2, sequence[i3]*3, sequence[i5]*5)
= Min(6, 6, 5)
= 5
sequence[] = | 1 | 2 | 3 | 4 | 5 |
i2 = 2, i3 = 1, i5 = 1 (i5 got incremented )
```

Fifth iteration

```
sequence[4] = Min(sequence[i2]*2, sequence[i3]*3, sequence[i5]*5)
= Min(6, 6, 10)
= 6
sequence[] = | 1 | 2 | 3 | 4 | 5 | 6 |
i2 = 3, i3 = 2, i5 = 1 (i2 and i3 got incremented )
```

### AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution can be found here.