PROBLEM LINK: Contest Practice
Author: Baban Gain
Editorialist: Baban Gain
DIFFICULTY:
EASY
PREREQUISITES:
Basic Mathematics
PROBLEM:
For a given number N, You need to find no. of perfect squares or perfect cubes from 1 to N ( both inclusive )
Note : If a number, like 64, which is both square ( 8^2 ) and cube (4^3) should be counted once only.
EXPLANATION:
Brute force solutions should fail as the question has tight time limit.
The answer is very simple and needs no explanation
ans = sqrt(N) + cbrt(N) - sqrt(cbrt(N)) for every test case.
where sqrt represents Square Root
cbrt represents Cube Root
sqrt(N) represents No. of squares upto N, cbrt(N) represents No. of cubes upto N.
But there can be numbers that can be both perfect square and perfect cube, which are considered twice.
Hence we can eliminate extra counting by subtracting sqrt(cbrt(N))
ALTERNATIVE SOLUTION:
ans = sqrt(N) + cbrt(N) - cbrt(sqrt(N))
AUTHOR’S SOLUTIONS:
Author’s solution can be found here.