Your purse has N distinct denominations for buying things. You are given the denominations in the array A. You have an infinite amount of each denomination available with you because you are very rich. You went to a theatre to buy a movie ticket. You don’t know the exact price of the ticket, just that it can cost anything from 1 to X inclusive. Since you hate change, you want to make sure that you can pay for the ticket without having to haggle for change. How many ticket prices from 1 to X can you buy without having to haggle for change?
1<=N<=10^3
1<=A[i]<=10^5
1<=X<=10^9
Sample Input 1:
2
3
5
10
Sample Output 1:
6’
how to solve this but contraint is high while using unbounder knapsack