COFN19E1 - Editorial

editorial
1

PROBLEM LINK:

Practice

Author: Hemanth Kumar
Tester: Hemanth Kumar
Editorialist: Hemanth Kumar

DIFFICULTY:

SIMPLE

PROBLEM:

Given a number N, we need to subtract the nearest smaller square number from it, and repeat this process until the given number becomes 0. We need to find the number of times subtractions like these can be carried out.

QUICK EXPLANATION:

To find the largest square number smaller than a number, it is straightforward to find it by finding the integral part of the square root and squaring it.

EXPLANATION:

Say N = 90
Find int(sqrt(N)) = int(9.486832980505138) = 9
Subtract N - 9*9 = 90 - 81 = 9

Now N = 9
Find int(sqrt(N)) = int(3) = 3
Subtract N - 3*3 = 9 - 9 = 0

Process ends here. We simply need to express this process in code form.

SOLUTIONS:

Setter's Solution 
from math import sqrt

t = int(input())
for _ in range(t):
    n = int(input())
    count = 0

    while n>0:
        s = int(sqrt(n))
        n -= s*s
        count += 1

    print(count)