1

I've been given a problem about finding all the possible combinations to change a 5 euro note. I've written a program that fails to result the correct number of combinations.

My approach was inspired from the following:

500 can be divided into 200, 200 and 100. 200 can be divided into 100 and 100. 100 can be divided into 50 and 50.

After I've written my code, I've realised that 100 can also be divided into 5 20's. This is a fault which I am aware of but I do not know how to fix using my approach.

My approach was a recursive one as can be seen below, it simply checks the first digit and divides it accordingly.

Here is what I tried:


public class Q1 {

    public static int counter;

    public static void main(String[] args) {

        divide(500);
        System.out.println(counter);

    }

    private static void divide(int x) {


        System.out.println("Dividing " + x);


        if(x == 1) {
            return;
        }

        counter++;

        int length = String.valueOf(x).length();

        int fd = Integer.parseInt(Integer.toString(x).substring(0, 1));
        String zeros;

        if(fd != 1) {
            zeros = Integer.toString(x).substring(1, length);
        }else {
            zeros = Integer.toString(x).substring(1, length-1);
        }


        if(fd == 5) {
            divide(Integer.parseInt(2 + "" + zeros));
            divide(Integer.parseInt(2 + "" + zeros));
            divide(Integer.parseInt(1 + "" + zeros));
        }else if(fd == 2) {
            divide(Integer.parseInt(1 + "" + zeros));
            divide(Integer.parseInt(1 + "" + zeros));
        }else if(fd == 1) {
            divide(Integer.parseInt(5 + "" + zeros));
            divide(Integer.parseInt(5 + "" + zeros));
        }


    }

}

For example using the above program misses

10 = 2 + 2 + 2 + 2 + 2

I am aware of working solutions already present like this one but I would like to maintain my approach if possible.

Using the program to finding out the combinations for 500 cents results 388 ways, where the correct answer is 6295435. Something tells me I'm forgetting something else other than the above example.

drew181
  • 333
  • 1
  • 10

1 Answers1

2

Here are some hints about why you get the wrong number:

A correct way to determine all possibilities

Try to split 5 instead of 500 for simplicity. Notice that there are 4 possibilities, namely 5 =

  1. 5
  2. 2 + 2 + 1
  3. 2 + 1 + 1 + 1
  4. 1 + 1 + 1 + 1 + 1

Now try dividing 10 instead of 500. Notice that this can be split up into 11 different ways: 10 =

  1. 10
  2. 5 + 5
  3. 5 + 2 + 2 + 1
  4. 5 + 2 + 1 + 1 + 1
  5. 5 + 1 + 1 + 1 + 1 + 1
  6. 2 + 2 + 2 + 2 + 2
  7. 2 + 2 + 2 + 2 + 1 + 1
  8. 2 + 2 + 2 + 1 + 1 + 1 + 1
  9. 2 + 2 + 1 + 1 + 1 + 1 + 1 + 1
  10. 2 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1
  11. 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1

This solution follows the following pattern: The number x you want to split is already an answer. Decrease the amount of lowest numbers by 1 by splitting one of these numbers into as many next largest numbers as possible. Always ignore ones. If there is only one number (and ones) left, split x into as many next lowest numbers as possible and continue.

For example, x = 10. Then: 10 is the lowest number -> split it up into 5 + 5 -> 5 is the lowest number ->split it up into 2 + 2 + 1 -> 2 is the lowest number since ones are ignored -> split it up into 1 + 1 -> we have another 2, split it up into 1 + 1 (this is equal to the solution 5 + 1 + 1 + 1 + 1 so now we have 5 as only one number apart from ones. Next lowest number is 2)-> split x=10 into 2 + 2 + 2 + 2 + 2 -> 2 is the lowest number; split it into 1 + 1 -> we have another 2 ...

This can be done in an recursive approach.

Things that went wrong in your code

What you code does with the example of dividing 10 is the following:

  1. 10 is divided into 5 + 5
  2. the first 5 is divided into 2 + 2 + 1
  3. one of these twos is divided into 1 + 1
  4. the other two is divided into 1 + 1
  5. Now, the second 5 from the division into 5 + 5 is divided into 2 + 2 + 1
  6. One of these twos is divided into 1 + 1
  7. The other two is divided into 1 + 1

Giving it a total score of 7 possibilities. Trying to map These 7 possibilities to the 11 above, you count 10 =

  • 10 once
  • 5 + 5 once
  • 5 + 2 + 2 + 1 twice
  • 5 + 2 + 1 + 1 + 1 twice
  • 5 + 1 + 1 + 1 + 1 + 1 twice

and missing the other 6 options.

So the assumption that this question can be solved by an approach like this one:

10 = 5 + 5 -> evaluate the first 5, then evaluate the second 5

is wrong because in both cases this leads to a distribution of 10 = 5 + evaluation of 5, counting only the options where at least one 5 is contained in the final distribution of 10 (counting it multiple times whearas distributions without fives are not evaluated).

Another mistake is that the code says there is no possible distribution of 1 where there actually exists one (1 = 1). Also, the question is unclear about

  • can x equal all possible whole numbers? -> 4 is not split up into 2 + 2 in your Code
  • is 1 + 1 + 2 a different solution from 1 + 2 + 1 and 2 + 1 + 1?

(I don't have the reputation to ask this in a comment yet).

Remaining an recursive approach can only be done with some significant changes. A possible way to do so is stated above.

R.H.
  • 98
  • 1
  • 8