Euler Project — Bouncy Numbers
In this blog, I talk about how I approached the Bouncy numbers problem from Project Euler.
The problem description first defines what is a bouncy number — it is a positive integer where its digits from left to right are neither increasing nor decreasing. The problem description then states that bouncy numbers becomes more common as number increases, which leads to the final question and asks for a program that finds the least number for which the proportion of bouncy number is exactly 99%.
My approach breaks this problem down into 2 parts — checking if a number is bouncy or not, and then determining the least number that produces the specified proportion.
The first part can be achieved through simple string manipulation:
1. if a number is an increasing number, then it must be equal to its sorted string version.
2. Likewise, if a number is a decreasing number, then it must be equal to its reversely sorted string version.
3. If neither cases are true, then a number must be a bouncy number.
The logic above can be used to derive a helper function below, which gets called by the main function described in the second part.
The second part calculates proportion of bouncy numbers starting from 1:
1. two variable are used to keep track of counts of bouncy numbers non bouncy numbers, which are then used to calculate the proportion of bouncy numbers using:
2. Create a loop that runs indefinitely on positive integers starting from 1, and ends when a desired condition is met. In this case, the condition is met when the calculated proportion in step 1 equals to 0.99.
a. Within the loop, I’m updating the counts of bouncy numbers and non-bouncy numbers based on the output of my helper function defined above.
b. if the condition is met, I exist the loop. Otherwise, I repeat step 2.a on the next integer.
This step is implemented in the following code snippet:
The complete implementation can be found in the notebook below.
