SQCB Editorial

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.

1 Like
//