Non-Constructible Change with Time and Space Complexity — Competitive Programming

Question — 5 (Level — Easy)

Welcome to the competitive series of Code Wrestling. Today, we are gonna solve another easy problem, Non-Constructible Change.

We will find the Time and Space complexity of the solution and will guide you to the process of finding an optimized solution.

Visit our YouTube channel for more interesting stuff Code Wrestling.

Github Repository Link: Github/Non-Constructible

Go to the previous question → Question — 4 (Tournament Winner)

Go to the next question → Question — 6 (Closest Value in BST)

Code Wrestling

Question

Given an array of positive integers representing the values of coins in your possession, write a function that returns the minimum amount of change (the minimum sum of money) that you cannot create. The given coins can have any positive integer value and aren’t necessarily unique (i.e., you can have multiple coins of the same value).

For example, if you’re given coins = [1, 2, 5], the minimum amount of change that you can’t create is 4. If you’re given no coins, the minimum amount of change that you can’t create is 1.

Sample Input:

coins = [5, 7, 1, 1, 2, 3, 22]

Sample Output:

20

STOP HERE. And read the question again. Try to solve the question on your own and then proceed further to see our solution.

Solution

The main objective here is to find the change which we cannot create from the given coins.

Approach:

We need to go through each number from 1,2,3… till we find the number, whose change we cannot create. So clearly we are starting from the smallest number and increasing it by 1. That gives us a hint that we must sort the given coins array.

So first sort the whole array and then create a flag, changeAlreadyCreated, and initialize its value as 0. So let’s satisfy the first condition, that if no coins are present, then the answer is 1.

And then loop over each element, so, the number (changeAlreadyCreated+ 1) is the next number whose change we want to create (remember, we are incrementing the number by 1?). Thus, we will check if the current element is greater than the (changeAlreadyCreated + 1), and if it’s already greater, that means, we were not able to create the change for (changeAlreadyCreated + 1), and thus that’s our answer. Otherwise, just add the current item to the changeAlreadyCreated and repeat the process.

Didn’t understand? Okay, let’s understand it step by step.

coins = [2, 5, 1]

1. Sort the array, thus coin=[1, 2, 5], and also changeAlreadyCreated = 0 (initially).
2. Now iterate over the array coins, and the current element is 1.
3. changeToBeCreated = changeAlreadyCreated+ 1 => 0 + 1 => 1;
4. Is currentElement > changeToBeCreated? No, that means we were able to create the change. Thus now changeAlreadyCreated = changeAlreadyCreated + currentElement => 0 + 1 => 1. Now changeAlreadyCreated= 1.
5. Next Iteration, now the currentElement = 2, and changeToBeCreated => changeAlreadyCreated+ 1 => 2
6. Is currentElement > changeToBeCreated? No, that means we were able to create the change. Thus now changeAlreadyCreated= changeAlreadyCreated+ currentElement => 1+ 2=> 3. Now changeAlreadyCreated= 3. (successfully created change for 1, 2 and 3).
7. Next Iteration, now the currentElement = 5, and changeToBeCreated => changeAlreadyCreated+ 1 => 3 + 1 => 4.
8. Is currentElement > changeToBeCreated? YES, that means we failed to create a change for number 4. Thus, the answer is 4.

Let’s see the code snippet:

private int NonConstructibleChange(List<int> coins)
{
   // Time complexity - O(n logn)
   // Space complexity - O(1)
   
   coins.Sort();
   int changeAlreadyCreated = 0;
   foreach (var item in coins)
   {
      int changeToBeCreated = changeAlreadyCreated + 1;
      if (item > changeToBeCreated) 
            return changeToBeCreated;
      changeAlreadyCreated += item;
   }
   
   // if empty array
   return changeAlreadyCreated + 1;
}

Here the time complexity is O(n logn) because the sorting has a time complexity of O(n logn) and the for loop has a complexity of O(n), now add both so O(n + n logn) => O(n logn) and space complexity is O(1).

Github Repository Link: Github/Non-Constructible

Go to the previous question → Question — 4 (Tournament Winner)

Solve the next question → Question — 6 (Closest Value in BST)

Thank you so much for reading till the end. See you in the next article. Till then… HAPPY LEARNING!!

Do visit our YouTube channel Code Wrestling for more interesting stuff.

Code Wrestling