I don’t know which algorithm you used but there are basically two methods for this problem.
I’ll try to explain both by keeping it as vague as possible.
Method 1: You can find your digits from left to right:
Basically every time you increase a digit by 1 it brings 9 * 9 * 9 * … new possibilities (as many factors as the number of following digits). So while you increase your digits you can add powers of 9 to a “control number” and stop when you reach n.
Obviously there are subtleties to take into account but the main idea is here and I think where your numbers come from is pretty self explanatory if you do this method.
So more likely you went for:
Method 2: You can find your digits from right to left
There’s an algorithm that looks like base 9 conversion and you might wonder why it works. Basically a number n converted in base 9 is the (n+1)-th number you can write with only 9 symbols (0-8).
Here you’re looking for the n-th number you can write with only 9 symbols (1-9).
Hence the similarities.
(And it also explains why method 1 looks like this cause base 9 conversion is about “putting as many powers of 9 as you can”.)
Could someone explain what was happening with the last test case?
I solved it by a gimick that I don’t understand (after making a division method for strings because I interpreted “out of memory” as integer overflow for some reason. That wasn’t the problem.)
The number you must output in the last test takes more than 64 bits.
It’s not really a problem as you find the digits one by one so you can store them in an array for example (I solved the puzzle in C to make sure that it works and it does).
As for the number n, a long long will do, and you can use the required operations on it without overflow.
I presume i’m completely on the wrong way. I always end up on counting upwards and this will eventually end in a timeout. I just can’t find a mathematical solution.
I wrote a program in JavaScript and couldn’t figure out why I was getting
33646585979948395194
And expected was:
33646585979948395414
Of course the same program worked just fine when I rewrote it in C#. This will teach me not to be a JS junkie.
Erf, I’m getting the same problem ! Can’t figure out what makes this result in JavaScript, even with using BigInt instead of Integer.
Does someone have an idea ?
Edit : I found my error. I was doing somewhere in my code BigInt(9 ** myNumber) which produce an integer which is cast to BigInt, so it does nothing. I change it by BigInt(9) ** BigInt(myNumber)
That part I figured out, but for whatever reason i’m off by 1 for 747 and 531441. I get 920 and 900000 instead of 919 and 899999. Any thoughts what does that ? The other small numbers work just fine.
i’ve written two versions of the algorithm. both produce 920 and 9000000. All i’m doing is converting a 9-base number to a 10 base number, right ? no other considerations ?
If it were remainders that I’m dropping, wouldn’t my number be too low ? Mine a 1 too high.
got it, but why is the answer for n = “4503599627370496” => 23776826742147167. When I do this, I get
21776826742147167. No zeros in the number and only the second digit differs. Both very large numbers have this issue; all the smaller ones work fine. What am i missing ?
Finding this one quite tough. I see the algorithm descriptions here and they make some sense, I’ll have to try again sometime when my brain is not so fried.
I have a brute force solution in place but of course my solution doesn’t finish for the multi-quadrillion+ values within the time constraints. Even with some low-hanging numerical pruning in place it’s not nearly fast enough, at least with Python…
I am not very good at Number Theory but am comfortable with many of its fundamentals. This one feels too much like “figure out this obscure trick in order to calculate faster” to me, but is there one or more concepts that would have helped me figure out a non-brute-force method on my own?
Absolutely no theory needed, knowing the algorithm to convert from base 10 to another base helps but it’s not even necessary.
I think the best way to figure out is to work on an example (say n=100) and try to understand how you could find the digits of the n-th solid number one by one instead of listing all solid numbers.
Hello guys,
I have solved all of the 9 tests, but for the validator there’s only the 7th (another small validator) that prevent me from getting the 100%.
Do you have any idea, clues ?.. Cause I’m running out of it.
Thanks !
