This page is still under construction.

Parts of this page are still being built. What you see may change.

Squares

Interview

Time limit1sMemory limit128 MB

Summary
Given a number of tiles, find the largest integer side length whose square does not exceed that number.
Level

Easy2 of 10

Topics
Math, Implementation, Brute force
Solved
No attempts yet

Problem

Gigi likes to play with squares. She has a collection of equal-sized square tiles. Gigi wants to arrange some or all of her tiles on a table to form a single solid square with no gaps. What is the side length of the largest such square that Gigi can build?

For example, with 9 tiles she can use all of them to build a square of side length 3. But with only 8 tiles, the largest square she can build has side length 2.

You may assume the number of tiles is less than ten thousand.

Input

A single integer: the number of tiles. This value is less than 10000.

Output

Print the maximum side length of the square that can be built, in the following format:

The largest square has side length X.

where X is the computed maximum side length.

Examples3

  1. Example 1

    Input
    9
    Expected output
    The largest square has side length 3.

  2. Example 2

    Input
    8
    Expected output
    The largest square has side length 2.

  3. Example 3

    Input
    7535
    Expected output
    The largest square has side length 86.