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

    HackerRank

  • |
  • Prepare
  • Certify
  • Compete
  • Hiring developers?
  1. All Contests
  2. ProjectEuler+
  3. Project Euler #64: Odd period square roots

Project Euler #64: Odd period square roots

Problem
Submissions
Leaderboard
Discussions

This problem is a programming version of Problem 64 from projecteuler.net

All square roots are periodic when written as continued fractions and can be written in the form:

For example, let us consider :

If we continue we would get the following expansion:

The process can be summarised as follows:

It can be seen that the sequence is repeating. For conciseness, we use the notation , to indicate that the block repeats indefinitely.

The first ten continued fraction representations of (irrational) square roots are:










Exactly four continued fractions, for , have an odd period.

How many continued fractions for have an odd period?

Input Format

Input contains an integer

Constraints

Output Format

Print the answer corresponding to the test case.

Sample Input

13

Sample Output

4

Author

shashank21j

Difficulty

Easy

Max Score

100

Submitted By

1370

Need Help?


View discussions
View top submissions

rate this challenge

MORE DETAILS

Download problem statement
Download sample test cases
Suggest Edits

Choose a translation


  • Blog
  • Scoring
  • Environment
  • FAQ
  • About Us
  • Support
  • Careers
  • Terms Of Service
  • Privacy Policy