✅✅Fastest 💯💯 Efficient 💎💎Simplest Solution 🏃‍♂️🏃‍♂️DryRun🔥🔥
Thanks for checking out my solution.This post has been made with ❤ by Alok KhansaliDo Upvote if this helped 👍🎯Approach : Greedy 🤑Intuition 🔮Leetcode walo ne wee
#### Thanks for checking out my solution. 
#### This post has been made with ❤ by [Alok Khansali](https://leetcode.com/u/TheCodeAlpha/)
### Do Upvote if this helped 👍

# 🎯Approach : Greedy 🤑
<!-- Describe your approach to solving the problem. -->
# Intuition 🔮
<!-- Describe your first thoughts on how to solve this problem. -->

##### Leetcode walo ne weekend hi hard bana diya, par agar tumne meri kl wali post dekhi hogi toh shayad itna mushkil nahi raha hoga. Aur aaj wali dekhne ke baad toh din hi set ho jayega.

##### Sawal hard hai, issi liye leetcode ne hint bhi ni di, Easy hota toh shayad 5-6 hint mil jaati, kyuki leetcode ko lagta hai hard toh ye bana hi lenge, seekhane ki jarurat toh easy wale hain.
___
#### 💡Chalo koi ni, mai koshish karta hu samjhaane ki.🤗
##### Maanlo tumhare paas koi bhi rupay💷 nahi hai, toh sabse pehli dikkat kitne rupay banane mai aayegi?
##### Sahi jawab 1✅, tez hote jaare ho nice!
##### Ab tumko 1 rupay dediye, toh ab kitne rupay banane mai dikkat aayegi? 
##### Ekdum sahi 2 rupay, kya baat back to back sahi jawab
##### Ab tumko do rupay bhi de diye, fir kis pe dikkat aayegi?
##### Arey gajab bilkul sahi 4rupay banane mai. Dekha samaj rahe ho tum..
##### Oh🤔 agar nahi samjhe toh aisa isiliye kyuki 1 + 2 = 3, toh teen rupay toh ab tum kisi ke bhi muh pe fek ke maar sakte ho.(Maarna mat😂, saamne wale ke paas sikke jyada huye toh....)
##### Ab tumko 4 rupay bhi de diye, ab batao kitne rupay pe agli dikkat aari?
##### Very nice 8 hi hai sahi sawab. 
##### Ab jo pattern ban raha hai, usko dekh ke ye mat socho ki 2 ki power mai khel denge aur crazy kar denge. Nahi❌
##### Thoda thoda idea lag gya hain humko ki ho kya raha hai, isko crystal clear💎 karte hain ab.

`nums` = [1,2,2,6,18]
#### Ab batao pehli dikkat kab aayegi?
- 1 ban jayega, kyuki diya hua hai
- 2,6,18 bhi ban jayenge upar wale reason se
- 3 banega 1 + 2 se, 4 banega 2 + 2 se, 5 banega 1+ 2 + 2 se, 7,8,9,10,11 bhi ban jayenge 6 ke saath pichle combinations ko jod kar
- Isse conclude hua ye ki hum 12 nahi bana paare hain abhi, pehla patch humko 12 pe dena hoga

#### Agar ab tumko dikha prefix sum, toh ekdum sahi raah🚉 par ho tum mitra💯. Par manzil tak pahuchne ke liye humko lagani padegi uss sum pe kuch shartein urf conditions
#### Humko values ka tokra sorted mila hai matlab ki jodne wala kaam shuru se aram se karlenge, 🧠dimag ni lagana sort karne mai. Ab agar tumne mere pehle example ko (haan voi jisme tumko power of 2 dikhra tha) dusre ke sath mix kiya hoga toh tum paaoge ki 12 par toh hum seedha aare hain....
**Pehli dikkat thi 1 rupya, humare aaray mai bhi 1 rupya, dikkat khatam, 1 ko jodo current dikkat pe, hogya 2 rupya, array ki dusri value 2 rupya, dikkat khatam, isko jodo current dikkat pe 4 rupya, array mai hai 2 rupya, koi dikkat hi ni....isi silisile ko dikhaya hai neeche maine**

**1 < 1, pehli dikkat
2 < 2, dusri dikkat
4 < 2, teesri dikkat
6 < 6, chauthi dikkat, abke sawal par
12 < 18, yaha par condition hogyi true aur humko mila pehla patch**

<details>
<summary> Sawal ko pese ke terms mai samjhane ka reason </summary>

- Ab maine rupyo ki baat isliye nahi ki kyuki mujhe pasand hain.(matlab hain par, yaha vo reason nahi hai) 
- Aisa isliye kyuki ek sawal kiya hua hai maine pehle jisko kehte hain Minimum Sum Coin, 
- uss ka saar ye hai ki aapko dediye sikke, aapko batana hai ki aisi konsi sabse choti value hai, jisko hum diye huye sikko se nahi bana payenge.
- 
</details>
.

**Ab bas is par ek cheez ka dhyaan rakhna ki jab koi value `x` currentSum se badi hogi, toh humko currentSum ko hi dugna kardena hai, iss se `currentSum` se lekar `currentSum * 2 - 1`, tak sab cover ho jayega, aisa tabtak karte rahein jabtak array ki value `x` se humara `currentSum` bada na ho jaye**

#### Bas issi Soch ke sath aage aap algorithm or dryrun ki sahayata lekar iss sawal ki chutti kar sakte hain. Meri dua lene ke liye mujhe upvote dein, tatha comment karein aur comment mai ek slightly simpler code ko bhi dekhein. Dhanyawaad!
#### Aasha karta hu aap sawal ko samaj gaye honge, aur aage isko code karne mai aapko ko koi kathinayi nahi hogi.

____
# Algorithm 👩‍💻
### 1. Initialisation:
   - `currentSum` ko 1 pe set karo. Yeh track karta hai sabse chhota number jo abhi tak nahi ban sakta.
   - `patches` ko 0 pe set karo. Yeh track karta hai kitne patches lagaye gaye hain.
   - `index` ko 0 pe set karo. Yeh `nums` array ko iterate karne ke liye hai.

### 2. Array ko Iterate karo:
   - Jab tak `currentSum` chhota ya barabar hai `n` ke:
       - Agar `index` chhota hai `nums.size()` se aur `nums[index]` chhota ya barabar hai `currentSum` ke:
           - `currentSum` mein `nums[index]` ko add karo.
           - `index` ko increment karo.
       - Agar nahi:
           1. __Patch Add karo:__
               - `patches` ko increment karo.
               - Ek patch add karo (`currentSum` ko) taaki range cover ho jaye `currentSum * 2 - 1` tak.
               - `currentSum` ko update karo (`currentSum` + `currentSum`).

### 3. Return karo Answer:
   - `patches` ko return karo jo total patches lagaye gaye hain.
___
![image.png](https://assets.leetcode.com/users/images/5031dd81-7597-4530-ad09-6cd846ac7581_1718521347.2285604.png)
___

# DryRun Time🏃‍♂️🏃‍♂️

<details>
<summary> DRYRUN</summary>

### Let's perform a dry run of the minPatches function with the given inputs:

    nums = [1, 2, 31, 33]
    n = 250

### Initial Setup:
 
    currentSum = 1 (Tracks the smallest number that cannot be formed)
    patches = 0 (Tracks the number of patches added)
    index = 0 (Iterator through the nums array)

## Step-by-Step Dry Run:
### Iteration 1:

    currentSum = 1
    index = 0, nums[index] = 1

    Since nums[index] <= currentSum:

        Add nums[index] to currentSum: currentSum = 1 + 1 = 2
        Increment index: index = 1

### Iteration 2:

    currentSum = 2
    index = 1, nums[index] = 2

    Since nums[index] <= currentSum:

        Add nums[index] to currentSum: currentSum = 2 + 2 = 4
        Increment index: index = 2

### Iteration 3:

    currentSum = 4
    index = 2, nums[index] = 31

    Since nums[index] > currentSum:

        Add a patch: currentSum = 4 + 4 = 8
        Increment patches: patches = 1

### Iteration 4:

    currentSum = 8
    index = 2, nums[index] = 31

    Since nums[index] > currentSum:

        Add a patch: currentSum = 8 + 8 = 16
        Increment patches: patches = 2

### Iteration 5:

    currentSum = 16
    index = 2, nums[index] = 31

    Since nums[index] > currentSum:

        Add a patch: currentSum = 16 + 16 = 32
        Increment patches: patches = 3

### Iteration 6:

    currentSum = 32
    index = 2, nums[index] = 31

    Since nums[index] <= currentSum:

        Add nums[index] to currentSum: currentSum = 32 + 31 = 63
        Increment index: index = 3

### Iteration 7:

    currentSum = 63
    index = 3, nums[index] = 33

    Since nums[index] <= currentSum:

        Add nums[index] to currentSum: currentSum = 63 + 33 = 96
        Increment index: index = 4

### Iteration 8:

    currentSum = 96
    index = 4, nums has no more elements.

    Since index >= nums.size():

        Add a patch: currentSum = 96 + 96 = 192
        Increment patches: patches = 4

### Iteration 9:

    currentSum = 192
    index = 4, nums has no more elements.

    Since index >= nums.size():

        Add a patch: currentSum = 192 + 192 = 384
        Increment patches: patches = 5

### Summary:

#### At the end of the iterations, currentSum exceeds n = 250, and we have added 5 patches in total.
### Final State:

    currentSum = 384 (Greater than n = 250)
    patches = 5

### Thus, the minimum number of patches required to make all numbers up to 250 representable is 5.

</details>

___
# Code
```cpp []
class Solution
{
public:
    int minPatches(vector<int> &nums, int n)
    {
        ios_base::sync_with_stdio(0);
        long long int currentSum = 1; // Tracks the smallest number that cannot be formed
        int patches = 0, index = 0;   // Pathches to keep track of the patch and Index to iterate through the nums array

        while (currentSum <= n)
        {
            // If the current number in nums is within the range and can be added to currentSum
            if (index < nums.size() && nums[index] <= currentSum)
            {
                currentSum += nums[index];; // Include nums[index] in the range
                index++;
            }
            else
            {
                // Add a patch (currentSum itself) to cover the range up to currentSum * 2 - 1
                currentSum += currentSum;
                patches++;
            }
        }
        return patches;
    }
};
```
```java []
class Solution
{
public
    int minPatches(int[] nums, int n)
    {
        long currentSum = 1; // Tracks the smallest number that cannot be formed
        int patches = 0;     // Number of patches added
        int index = 0;       // Index to iterate through the nums array

        // Continue until we can form numbers up to n
        while (currentSum <= n)
        {
            // If current index lies in the array 
            //and the current value is less than equal to the currentSum
            if (index < nums.length && nums[index] <= currentSum)
            {
                // If the current number in nums can be added to currentSum
                currentSum += nums[index]; // Include nums[index] in the range
                index++;
            }
            else
            {
                // Add a patch (currentSum itself) to cover the range up to currentSum * 2 - 1
                currentSum += currentSum;
                patches++;
            }
        }
        return patches;
    }
}
```
```python []
class Solution:
    def minPatches(self, nums: List[int], n: int) -> int:
        currentSum = 1  # Tracks the smallest number that cannot be formed
        patches = 0     # Number of patches added
        index = 0       # Index to iterate through the nums array

        # Continue until we can form numbers up to n
        while currentSum <= n:
            if index < len(nums) and nums[index] <= currentSum:
                # If the current number in nums can be added to currentSum
                currentSum += nums[index]  # Include nums[index] in the range
                index += 1
            else:
                # Add a patch (currentSum itself) to cover the range up to currentSum * 2 - 1
                currentSum += currentSum
                patches += 1

        return patches
```
____
# Complexity
- Time complexity: $$O(N)$$
<!-- Add your time complexity here, e.g. $$O(n)$$ -->

- Space complexity: $$O(1)$$
<!-- Add your space complexity here, e.g. $$O(n)$$ -->
____
![upv3.jpeg](https://assets.leetcode.com/users/images/d4552272-c650-4677-85df-e5c6ed7a3486_1718521178.6483333.jpeg)

['Array', 'Math', 'Greedy', 'C++', 'Java', 'Python3']