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 #70: Totient permutation
  4. Discussions

Project Euler #70: Totient permutation

Problem
Submissions
Leaderboard
Discussions

Sort 12 Discussions, By:

votes

Please Login in order to post a comment

  • layer8
    7 years ago+ 2 comments

    It seems to me that by the problem definition you can get multiple answers for the same N. For the 100 example, phi(21) is 12 and the n/phi(n) ratio is 7/4, while phi(63) is 36 and the n/phi(n) also yields 7/4. The problem statement includes no criteria for deciding ties.

    3|
    Permalink
  • kitchent
    4 years ago+ 1 comment

    I am one of those who approach the problem using the property that is minimum when it is prime. And because is never the permutation of prime , so we set our sight on being the product of two primes and . (Hint on counting: )

    For my implementation, I used a prime sieve to generate a list of primes, and feed them to a 2-level for loop afterwards. The point here is the find a balance between reducing the size of prime sieve (otherwise it would be TLE if we make a sieve of size ) and whether we have enough primes to get to the answer. For example, one of the answers is (product of and ), so we need to ensure is included in the prime sieve when is .

    Apart from that, we have one honourable candidate who is an answer, but is not the product of two prime numbers, but three! This is the frustrating Test Case #10. I don't have a strategy yet to handle this other than treating it as a special case.

    1|
    Permalink
  • Argooni
    6 years ago+ 0 comments

    My code is giving wrong answer for test case 10. Other cases are success. Does anyone have any information about test case 10?

    Ok seems this comment "it's a special case. try brute forcing values <5000 and compare." by shashank21j gave me the right answer. Thank you.

    1|
    Permalink
  • franko4don
    7 years ago+ 1 comment

    can "java.lang.OutOfMemoryError: Java heap space" make me get wrong answer for a test case?

    0|
    Permalink
  • SalvadorDali
    7 years ago+ 1 comment

    Any idea what is so special about TC_10? Yes, I read the discussion and followed a relevant thread, and in my case there were 6 numbers below 5000.

    Opinion of @shashank21j or @advancedxy would be appreciated.

    0|
    Permalink
Load more conversations

Need Help?


View top submissions
  • Blog
  • Scoring
  • Environment
  • FAQ
  • About Us
  • Support
  • Careers
  • Terms Of Service
  • Privacy Policy
  • Request a Feature