CODEWITHSUNDEEP
algorithmnumberssequencesquareperfect-square
prolific
prolific

Reputation: 13

Efficiently computing all the perfect square numbers for very large numbers like 10**20

Examples of perfect square numbers are 1,4,9,16,25....

How do we compute all the perfect square numbers for very large numbers like 10 pow 20. For 10 pow 20 there are 10 pow 10 perfect square numbers.

So far what i have done....

Bruteforce : calucate the x**2 in range 1 to 10 pow 10. As my system accepts just 10 pow 6. This didn't work.

Two pointer approach : I have taken the upper and lower bounds....

Upper bound is 10 pow 20

Lower bound is 1

Now, i have taken two pointers, one at the start and the other at the end. Then next perfect square for lower bound will be

lower bound + (sqrt(lower bound) *2+1)

Example : for 4 next perfect square is

4 + (sqrt(4)*2+1)= 9

In the same way upper bound will be decreasing

upper bound - (sqrt(upper bound) *2-1)

Example : for 25 the previous perfect square is

25 - (sqrt(25)*2-1) =16

Both of the above mentioned approaches didn't work well because the upper bound is very very large number 10 pow 20.

How can we efficiently compute all the perfect squares till 10 pow 20 in less time ?

Upvotes: 1

Views: 159

Answers (1)

Daniel
Daniel

Reputation: 7714

It's easy to note the difference between perfect squares:

0   1   4   9   16   25   ...
|___|___|___|___|_____|
  |   |   |   |    |
  1   3   5   7    9

So we have:

answer = 0;
for(i = 1; answer <= 10^20; i = i + 2)
    answer = answer + i;
    print(answer);
}

Since you want all the perfect squares until x, the time complexity will be O(sqrt(x)), which may be slow for x = 10^20, whose square is 10^10.

Upvotes: 3

Related Questions