DAY 7- Minimum number of Coins

Hello to anyone reading this. I am still relatively new to coding and this platform as well, so please feel free to drop any corrections/advice for me.
I am trying to do the 100 Day-Challenge of consistent coding and this is Day 7.Looking forward to a positive interaction with all of you.

DAY 7 Problem 1: Minimum number of Coins

Given an infinite supply of each denomination of Indian currency { 1, 2, 5, 10, 20, 50, 100, 200, 500, 2000 } and a target value N.

_Find the minimum number of coins and/or notes needed to make the change for Rs N. You must return the list containing the value of coins required. _

Example 1:

Input: N = 43
Output: 20 20 2 1
Explanation:
Minimum number of coins and notes needed to make 43.

Intuition:

The problem is very direct. Here we have to find the minimum number of coins such that we can make the required number.
Another way we can look at this problem is that we need to find the coins with maximum value that exactly add up to this number.

Approach:

• So what we will do in this case, is apply greedy theorem. It basically comes in handy where we make the locally best choice and reach the global optimum solution from there.
• We will take the number N and run it through the array of currencies starting from the largest till we find a value that is not greater than the existing number.
• It will be the largest number in currencies that satisfies the condition.
• Then we shall subtract that number from our currency and add the number to our list of answers.
• Running this loop till the number is 0, we get our required result.

*Code: *

vector<int> minCoins(int N)
    {
        int currency[10] = {1,2,5,10,20,50,100,200,500,2000};
        vector<int> ans;
        int i = 9;
        while(i >= 0)
        {
            if(N >=currency[i])
            {
                ans.push_back(currency[i]);
                N = N - currency[i];
            }
            else
            {
                i--;
            }
        }
    return ans;    
    }

Complexity Analysis

Time Complexity: O(V)
Space Complexity: O(1)

Since the space is only used to store the output our space complexity shall remain 1.

Here we saw today an approach of greedy algorithm. Until now, I have been doing questions randomly but I will be trying to make it in more of learning matter now.