<p>You are given a <strong>0-indexed</strong> integer array <code>coins</code>, representing the values of the coins available, and an integer <code>target</code>.</p>

<p>An integer <code>x</code> is <strong>obtainable</strong> if there exists a subsequence of <code>coins</code> that sums to <code>x</code>.</p>

<p>Return <em>the<strong> minimum</strong> number of coins <strong>of any value</strong> that need to be added to the array so that every integer in the range</em> <code>[1, target]</code><em> is <strong>obtainable</strong></em>.</p>

<p>A <strong>subsequence</strong> of an array is a new <strong>non-empty</strong> array that is formed from the original array by deleting some (<strong>possibly none</strong>) of the elements without disturbing the relative positions of the remaining elements.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> coins = [1,4,10], target = 19
<strong>Output:</strong> 2
<strong>Explanation:</strong> We need to add coins 2 and 8. The resulting array will be [1,2,4,8,10].
It can be shown that all integers from 1 to 19 are obtainable from the resulting array, and that 2 is the minimum number of coins that need to be added to the array. 
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> coins = [1,4,10,5,7,19], target = 19
<strong>Output:</strong> 1
<strong>Explanation:</strong> We only need to add the coin 2. The resulting array will be [1,2,4,5,7,10,19].
It can be shown that all integers from 1 to 19 are obtainable from the resulting array, and that 1 is the minimum number of coins that need to be added to the array. 
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> coins = [1,1,1], target = 20
<strong>Output:</strong> 3
<strong>Explanation:</strong> We need to add coins 4, 8, and 16. The resulting array will be [1,1,1,4,8,16].
It can be shown that all integers from 1 to 20 are obtainable from the resulting array, and that 3 is the minimum number of coins that need to be added to the array.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= target &lt;= 10<sup>5</sup></code></li>
	<li><code>1 &lt;= coins.length &lt;= 10<sup>5</sup></code></li>
	<li><code>1 &lt;= coins[i] &lt;= target</code></li>
</ul>

class Solution:
    def minimumAddedCoins(self, coins: List[int], target: int) -> int:
        """
        coins = [1,4,10], target = 19
        dp[i] = [1 .. n]
        dp[i+1] = [1 .. n .. n+v[i]] = [1 .. k]

        if we can form all numbers from 1 to n with the first i numbers,
        then with numbers[i+1], we can form [1..n] & [0+nums[i+1] .. n + nums[i+1]]
        if [1..n] and [0+nums[i+1] .. n + nums[i+1]] not overlap, we need to add coins

        coins = [1,4,10]
        i = 0, [1]
        i = 1, -> [1] & [4, 5]: not overlap, -> add 2, coins = [1,2,4,10]
        i = 1 again -> [1] & [2,3] = [1,2,3]
        i = 2 -> [1,2,3] & [4,5,6,7] = [1..7]
        i = 3 -> [1..7] & [10 ..] -> not overlap, add 8, coins = [1,2,4,8,10]
        i = 3 again -> [1..7] & [8..15] = [1..15]
        i = 4 -> [1..15] & [10..25] = [1..25] match target = 19

        at index i:
            if maxObtained + 1 < nums[i]:
                while maxObtained + 1 < nums[i]:
                    add new coin = maxObtained + 1
                    maxObtained += coin
            if maxObtained + 1 >= nums[i]:
                maxObtained += num[i]
        """


        """
        coins = [1,1,1], target = 20
        """

        n = len(coins) #3
        coins.sort()
        added = 0
        maxObtained = 0

        # loop through all coins, stop if target is reached
        for i in range(n):
            while maxObtained < target and maxObtained + 1 < coins[i]:
                newCoin = maxObtained + 1
                added += 1
                maxObtained += newCoin
            
            if maxObtained >= target:
                break
            
            maxObtained += coins[i]
        
        # if target not reached, keep adding new coins
        while maxObtained < target:
            newCoin = maxObtained + 1
            added += 1
            maxObtained += newCoin
        
        return added

441