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

Question

Sample Input:

Sample Output:

Solution

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

  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.
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