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.
  • Hackerrank Home
  • Prepare
    NEW
  • Certify
  • Compete
  • Career Fair
  • Hiring developers?
  1. All Contests
  2. ProjectEuler+
  3. Project Euler #92: Square digit chains
  4. Discussions

Project Euler #92: Square digit chains

Problem
Submissions
Leaderboard
Discussions

    You are viewing a single comment's thread. Return to all comments →

  • FranckV
    7 years ago+ 1 comment

    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....

    1|
    Permalink
  • Contest Calendar
  • Blog
  • Scoring
  • Environment
  • FAQ
  • About Us
  • Support
  • Careers
  • Terms Of Service
  • Privacy Policy
  • Request a Feature