/*
 * Copyright (C) 2014 Pedro Vicente Gómez Sánchez.
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 * http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
package com.github.pedrovgs.problem47;

import java.util.List;

/**
 * Given an array of available money and a value as input, can you write a method to return all
 * that change using the less money as possible.
 *
 * @author Pedro Vicente Gómez Sánchez.
 */
public class ReturnChange {
  public List<Integer> calculate(int[] moneys, int billAmount) {
    return null;
  }
}

@@ -645,16 +645,45 @@
 lem47;%0A%0A
+import java.util.LinkedList;%0A
 import j
@@ -926,89 +926,977 @@
 e %7B%0A
-  public List%3CInteger%3E calculate(int%5B%5D moneys, int billAmount) %7B%0A    return null;
+%0A  /**%0A   * Iterative solution to this algorithm. This algorithm has a complexity order equals to O(N)%0A   * where N is the billAmount/maxMoneyValue. At the end, linear to the value passed as parameter.%0A   */%0A  public List%3CInteger%3E calculate(int%5B%5D moneys, int billAmount) %7B%0A    validateInputData(moneys, billAmount);%0A    List%3CInteger%3E change = new LinkedList%3CInteger%3E();%0A    while (billAmount %3E 0 && moneys.length %3E 0) %7B%0A      for (int i = moneys.length - 1; i %3E= 0; i--) %7B%0A        if (billAmount - moneys%5Bi%5D %3E= 0) %7B%0A          change.add(moneys%5Bi%5D);%0A          billAmount -= moneys%5Bi%5D;%0A          break;%0A        %7D%0A      %7D%0A    %7D%0A    return change;%0A  %7D%0A%0A  private void validateInputData(int%5B%5D moneys, int billAmount) %7B%0A    if (moneys == null %7C%7C moneys.length == 0 %7C%7C billAmount %3C= 0) %7B%0A      throw new IllegalArgumentException(%0A          %22Review your parameters used as input, you can't use a null or empty array of moneys or a bill amount equals or less than zero.%22);%0A    %7D
 %0A  %7D

Add iterative solution to problem 47