PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: raysh07
Tester: sushil2006
Editorialist: iceknight1093
DIFFICULTY:
Cakewalk
PREREQUISITES:
None
PROBLEM:
Given N, find the largest square number that doesn’t exceed N.
EXPLANATION:
The simplest solution is to just loop over all the square numbers starting from 1, and print the largest one that doesn’t exceed N.
This takes \mathcal{O}(\sqrt N) time, since going past \sqrt N will surely result in squares larger than N.
Alternately, you can compute the square root of N (using your language’s inbuilt sqrt function), round this down to the nearest integer, and print the square of that.
TIME COMPLEXITY:
\mathcal{O}(\sqrt N) per testcase.
CODE:
Editorialist's code (PyPy3)
for _ in range(int(input())):
n = int(input())
for i in range(1, 100):
if i*i > n: # Exceeded n, so print the previous square
print((i-1)*(i-1))
break