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

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

Solution

coins = [2, 5, 1]

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;
}

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store