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.
I have one idea in mind that would lower the complexity, but I don't think it'll lower it enough.
I am thinking to reformulate numbers under the following forms:
(number) = a*1 + b*2 + ... i*9
In other words, what really matters is the number of times each digit is repeated. So every number between 1 - 10^K can be reformulated as such. Many numbers in there will in fact be just reformulation of the same pattern (e.g. 227788, 728827, etc are identical "paths" to 89 or to 1).
So the problems then becomes about elaborating each combinaisons (keeping in mind we have at most: a + b + ... i <= 200), figuring out if it leads to 89 or 1. This is still a lot (around 22^9, or 1.2 trillions) though...
There has to be a mathematical pattern, but can't find it yet....
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Project Euler #92: Square digit chains
You are viewing a single comment's thread. Return to all comments →
Not that easy.
I have one idea in mind that would lower the complexity, but I don't think it'll lower it enough.
I am thinking to reformulate numbers under the following forms:
(number) = a*1 + b*2 + ... i*9
In other words, what really matters is the number of times each digit is repeated. So every number between 1 - 10^K can be reformulated as such. Many numbers in there will in fact be just reformulation of the same pattern (e.g. 227788, 728827, etc are identical "paths" to 89 or to 1).
So the problems then becomes about elaborating each combinaisons (keeping in mind we have at most: a + b + ... i <= 200), figuring out if it leads to 89 or 1. This is still a lot (around 22^9, or 1.2 trillions) though...
There has to be a mathematical pattern, but can't find it yet....