Coding Games and Programming Challenges to Code Better
Send your feedback or ask for help here!
I solved them all except the ‘BIG’ case. Anybody got an idea how to optimize the algorithm? Thnx in advance.
Could you describe your current algorithm? Then we’ll see what we may advise you accordingly.
1 Like
I have a loop over all numbers smaller than r1. And add the sum it its digits to this number as long as its smaller than r1. If this equals r1 we have a match and I put my counter up, and as soon as its bigger than r1 we go to the next. I do this till the counter reaches 2, cause than we’re done. This works for all tests except the “BIG” one. I understand my algorithm has performance issues but I don’t know, yet, how to fix this.
I hope this is clear, else i can explain more.
Any help is appreciated.
Do you test the same numbers more than once?
For example, if you have tested 1 → 2 → 4 → 8 → 16 → 23 etc, do you test 2 → 4 → 8 → 16 → 23 etc? And then 4 → 8 → 16 → 23 etc?
2 Likes
I’ll try to implement this. Many thanks!
You could also think more on “what are the numbers that can give the one I get in input” .
As the river starting at the number count, you only have to find 1 single river, So just check the previous numbers 
2 Likes
Thanks i got it working now 
This doesn’t feel like it is in the spirit of the description, but I’ll take an easy code where I can! 
True, it’s not in the spirit of the description but it’s the idea that you need to use to reduce your code’s complexity to something manageable (and it can be proven that the description implies that this short-cut is correct, always).
The solution was not making that list, although it also works. For me the solution was realizing I didn’t need to loop through all number because the difference between two consecutive elements of a river can only be a certain distance of each other.
1 Like
Is there a mathematical way to show that a number is the sum of a number and the sum of its digits ?
I used some brute force, because I can’t think of some better way
I don’t see how that helps.
All I can see is that there is at most 9 * ceil(log10(n)) value to test.
But I don’t see how you can find the previous number (or a previous number, nothing says it has to be unique but maybe it is) in the sequence
well, it still gives me only one equation with several unknowns… (ok, we have constraints so that’s several equations, like a+b<=18 ; a>=0; b>=0 etc…
Or I’m missing something.
But for example 117 is the follow up of 99 and 108.
Don’t try to find the solution by solving the equation, instead loop through all possible solutions to find it.
My question was about having a solution without looping. Otherwise it’s quite easy.
It’s not about being ‘the spirit of the description’…
It solves the problem with a Log10(n) complexity, I think it is quite efficient (and won’t time out on big numbers)
That’s the point, you only have to check the few numbers before (~10*log10(n) numbers )
We are saying the same thing.
I am also failing the two “big” test cases. I have done a little memoization, avoiding to re-check all hops of previously checked rivers.
E.g. checking 3 as a possible start, if 3 → 6 → 12 → 15 → 21… doesnt meet my target number, then later I skip 6, 12, 15, 21 and all other hops of river 3. I thought this would solve it, but I am still timing out the big cases. Any ideas to help me along?