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:

(999999999999996604 1000000000000000000) = 27115965547703180212015
(999999999999998764 1000000000000000000) = 75283765372168284789645
(999999999999997593 1000000000000000000) = 38415085583714167012880
(999999999999998242 1000000000000000000) = 52651358930602957906713
(999999999999991948 1000000000000000000) = 8205762543467461500249
(999999999999999241 1000000000000000000) = 169299150197628458498024
(999999999999991578 1000000000000000000) = 7739998337687010211352
(999999999999991565 1000000000000000000) = 7727886899822169531714
(999999999999999387 1000000000000000000) = 209622115823817292006526
(999999999999997840 1000000000000000000) = 42808060185185185185186

can someone explain the better apporach to solve the problem? i've tried the brute force method, but it only worked for default test case. Rest are timed out.

There has to be an approach better than . Iterating through every number takes forever for input like 9999999 1000000. Perhaps a formula for that? A clever DP?

EDIT: I have two pieces of clues that could be hit or miss.

Firstly, on proportion . We are looking for the least number for which the proportion of bouncy numbers is at least . That means we would stop at the first occurrence of answer.

It is clear that every intermediate proportion can also be expressed as a rational fraction , and that because the numerator is at most incremented by one for each step, we should first encounter an answer that is exactly the same as before it is greater than that (EDIT 2: Not True). This is similar to how we would come across zero on the number line when sliding from negative integers to positive integers.

As a result, it is guaranteed that our answer would be divisible by , assuming and have no common divisor other than (when they have, manipulate them). If we have a method to quickly count the occurrences of bouncy numbers below the number , we would save a lot of time by only checking the multiples of .

Secondly, on counting the occurrences of -digit bouncy numbers. This could be a sub-problem of this problem. We can think of it as a stars and bars problem distributing the increase-by-one operators or decrease-by-one operators over the "wall" of the digit placeholders. This reminds me of Google Code Jam Qualification Round 2017 Problem B: Tidy Numbers.

Anyway, by counting all increasing -digit numbers and decreasing -digit numbers separately, we could easily find the number of occurrences that are neither increasing or decreasing (and don't forget about their intersection).

The problem here is that, we could not yet easily count the occurrences of bouncy numbers that is JUST BELOW certain . Perhaps some sort of messy queue can do? Performing some kind of binary search does not work either, as the proportion of bouncy numbers given by, for example, , is definitely not greater than that of .

EDIT 2: Although I've figured out a way to count the occurrences of bouncy numbers below certain (generating the positions of original stars and bars first, and count the posibilities of moving the nine bars left or right, depending on increasing or decreasing numbers and whether you want to do it inclusively or subtractively. I chose to be inclusive for increasing numbers and subtractive for decreasing numbers, both moving the bars to the right), now that I think it through, it is not necessarily true that the proportion has to be equivalent to before exceeding it (e.g. the answer for 50 101 is 519, which is not a multiple of ).

It appears to be true for a lot of input, though. It's somewhat alluring when you see that is a multiple of . For those where this is true, it's also funny to discover the result for 394 395 and 395 396 are sharing the same multiplier , and the same for 396 397 and 397 398. The multiplier has an increasing trend. You might work your way up to see if a sequence is out there.

are 11, 22 or 66666 or numbers of this kind bouncy numbers??

For the case n = 90 and m = 100 (given in sample input) n/m == 0.9 right So the number of No of BouncyNos / Total Numbers should be 0.9

But the output given as the answer -> 21780 (for which No of BouncyNos / Total Numbers = 0.857414 ) where as my output is occuring is 71980 (for this No of BouncyNos / Total Numbers = 0.9)...Correct me if i am wrong