Problem: -
When a number can be represented as x^m + y^n, where x,y >= 1, m,n >=2, it can be called as good numbers.
Ex:- 1 is not a good number as there is no way to write 1 in this above form.
2= 1^2 + 1^2. So 2 is a good number.
3 is not either.
4 is not.
5= 1^2 + 2^2. So 5 is a good number

We need to find how many numbers between 1 - N are good numbers.
Ex:- If N=1 , then return 0.
If N=2, return 1 (2 is a good number)
if N=3, return 1(only 2 is a good number)
if N=5, return 2(both 2&5 are good numbers).
......................

N can be as large as 1,000,000.

I wasn't able to solve this in my OA. Can you share on how to approach this kind of problem ?Any ideas ?