We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
Sweet, finally got it! I'll offer some guidance to those who are stuck (without spoilers, of course), because unfortunately this appears to be one of those problems with binary scoring, so it can be difficult to judge whether or not you're on the right track.
It is important to be able to efficiently calculate the count of bouncy numbers for any number containing between 3 and ~30 digits. I used iterative digit DP to accomplish this. (https://www.geeksforgeeks.org/digit-dp-introduction/)
When performing the search for the solution, you should increase the value of the result according to the distance between your current ratio of bouncy numbers and n/m. There is some pretty straightforward algebra that can be used to approximate the value you should increase your result by (which has been discussed in this problem's forum on the Project Euler website), but this method will overshoot the correct answer as the size of the numbers increases, so you'll need an additional step to minimize your result.
Initially I was trying to find the solution using a rather complex DFS function, loaded with branching conditionals. While this approach did produce the correct results, it was much too slow. My final solution did not require recursion or any sort of tree traversal.
As others have mentioned, some of the results will require more than 64 bits. I used Python for this reason.
Project Euler #112: Bouncy numbers
You are viewing a single comment's thread. Return to all comments →
Sweet, finally got it! I'll offer some guidance to those who are stuck (without spoilers, of course), because unfortunately this appears to be one of those problems with binary scoring, so it can be difficult to judge whether or not you're on the right track.
It is important to be able to efficiently calculate the count of bouncy numbers for any number containing between 3 and ~30 digits. I used iterative digit DP to accomplish this. (https://www.geeksforgeeks.org/digit-dp-introduction/)
When performing the search for the solution, you should increase the value of the result according to the distance between your current ratio of bouncy numbers and n/m. There is some pretty straightforward algebra that can be used to approximate the value you should increase your result by (which has been discussed in this problem's forum on the Project Euler website), but this method will overshoot the correct answer as the size of the numbers increases, so you'll need an additional step to minimize your result.
Initially I was trying to find the solution using a rather complex DFS function, loaded with branching conditionals. While this approach did produce the correct results, it was much too slow. My final solution did not require recursion or any sort of tree traversal.
As others have mentioned, some of the results will require more than 64 bits. I used Python for this reason.
========================================
Some large test cases, with solutions: