preRAJUisation Numbers - Phonepay Online Assessment MNNIT Allahabad

Rastogi Ji observed an interesting pattern: Windows 10 came out right after Windows 8, Iphone X came right after Iphone 8. Seems like companies hate the digit 9! Like digit 9 is almost a 10 ,but not quite. He told this to professor Virus!

Enraged, prof Virus handed Rastogi Ji a list of digits which companies hate & will not use it in their product number. So in set of all natural numbers, remove all numbers that contains a digit that companies hate. Rastogi is asked to compute Nth number in this set or that he will be expelled from the College!

Rastogi is in immense pressure and is looking out for his Rancho in need, are you the one? Be wary, numbers can be bigger than ego of Virus!

Input The first line will contain an integer d, the number of digits companies hate.

The second line will contain d distinct integers in increasing order, representing the digits companies hate. (These d digits will all be positive, 0 is never a digit that companies hate)

The third line will contain an integer N, as described in problem.

Output Output a single integer: the Nth positive number that contains no digits that companies hate.Note that this number can have more than 18 digits

Example 1:

Input:[1,[5],1]

Output:[1]

Example 2:

Input:[1,[9],9]

Output:[10]

Example 3:

Input:[3,[3,6,9],15]

Output:[21]

Constraints:

1 <= d <= 8

1 <= N <=10^{18}

solution.cpp

Run code to see test results

00:00 / 69:42