# Missing pennies

## Weekly Challenge 201

You are given an array of unique numbers.

Write a script to find out all missing numbers in the range `0..\$n` where `\$n` is the array size.

### My solution

This is a one liner in Python, giving the list `n`, the solution I provided is:

``````missing = [i for i in range(len(n)+1) if i not in n]
``````

Breaking it down into parts:

• `range(len(n)+1)` is the range from 0 to the length of the array (inclusive).
• this is called in a `for` loop, with each iteration given the value `i`.
• the `if i not in n` part of the clause will only return numbers NOT in the original array `n`.
• the `i` after the opening bracket will return that value.

For the Perl code, I took a different approach given that it does not support `for ... if` or the `in` keyword. The first thing I do is convert `@n` an array, to `%n` a hash with the map function. Then I run this code:

``````@missing = grep { !exists( \$n{\$_} ) } ( 0 .. \$#n + 1 );
``````

Like with the Python code `( 0 .. \$#n + 1 )` is the range from 0 to to the length of the array (inclusive). The grep function iterates through the list, setting `\$_` as the current value. The `exists` function checks to see if that value exists in a hash.

### Examples

``````\$ ./ch-1.py 0 1 3
2

\$ ./ch-1.py 0 1
2
``````

You are given an integer, `\$n > 0`.

Write a script to determine the number of ways of putting \$n pennies in a row of piles of ascending heights from left to right.

### My solution

Pennies were removed from circulation in New Zealand (my birth country) in 1967, well before I was born. Even coins were removed when I was a kid.

Let me start off by acknowledging that the answer for the most efficient solution is probably already in OEIS. In previous tasks I've occasionally looked at producing the most efficient solution. Not today.

This time I'm solving the solution as it is described, and with yet another recursive function. The good thing is we don't care about what the combinations are, just how many there are.

For this solution my recursive function is called `pile`, and takes two inputs, the `remain`ing pennies, and the `minimum` number I can take. The first call to the function in the input number, and a minimum of 1 penny.

For each call, I loop from the minimum value to the remaining pennies. If the two values are the same, we have found a solution. If there are coins left over, I call the `pile` function again, with the remaining coins and the coins I took (i.e. the new minimum). The return of each call is the number of solutions found.

### Examples

``````\$ ./ch-2.py 5
7

\$ ./ch-2.py 50
204226
``````