# Sqrt problem , my solution works perfectly but it gives error on leetcode.

• My solution below works perfectly , but leetcode gives error, i cant see the problem.
Leetcode claims that there is runtime error with:
Last executed input:
2147395599

``````public int MySqrt(int x)
{
if (x == 0) { return 0; }
if (x >= 1 && x < 3) { return 1; }
if (x >= 3 && x < 9) { return 2; }
if (x >= 9 && x < 16) { return 3; }
if (x >= 16 && x < 25) { return 4; }
if (x >= 25 && x < 36) { return 5; }

int length = x / 5;
int[] candidates = new int[length + 1];

for (int i = 0; i < length + 1; i++)
{
candidates [i] = i;
}

return findSqrt (candidates, x, 0, length);
}

public int findSqrt(int[] candidates,int x,int lo, int hi)
{
if (lo == hi) { return 0; }
int mid = lo + (hi - lo) / 2;
double pow = Math.Pow (candidates [mid], 2);

double lowDiff = pow - (candidates [mid - 1] + candidates [mid]);
double upperDiff = pow + (candidates [mid] + candidates [mid + 1]);

if (x == pow || (x > pow && x < upperDiff)){
return mid;
}

if (x < pow &&  x > lowDiff ) {
return mid - 1;
}

if (pow < x) {
return findSqrt (candidates, x, mid + 1, hi);
} else {
return findSqrt (candidates, x, lo, mid);
}

}``````

• The judger is throwing `System.OutOfMemoryException` when running your code. One line 11 you are doing:

``````int[] candidates = new int[length + 1];
``````

This is probably where the problem lies. You are trying to allocate an array of size 2147395600, no wonder it will run out of memory.

• Thank you for reminding. I used an array to investigate the all iteration printing its interval values in screen, as you reminded. Solution should not use that big array. My mistake.

• I have solved it without using array, thank you. It used binary search and calculates tests in 60ms. Thank you 1337c0d3r

`````` public int MySqrt(int x)
{
if (x == 0) { return 0; }
if (x >= 1 && x <= 3) { return 1; }
if (x >= 4 && x < 9) { return 2; }
if (x >= 9 && x < 16) { return 3; }
if (x >= 16 && x < 25) { return 4; }
if (x >= 25 && x < 36) { return 5; }

int length = x / 5;

return findSqrt (x, 0, length);
}

public int findSqrt(int x,int lo, int hi)
{
if (lo == hi) { return 0; }
int mid = lo + (hi - lo) / 2;
double pow = Math.Pow (mid, 2);

double lowDiff = pow - ((mid - 1) + mid);
double upperDiff = pow + (mid + mid + 1);

if (x == pow || (x > pow && x < upperDiff)){
return mid;
}

if (x < pow &&  x > lowDiff ) {
return mid - 1;
}

if (pow < x) {
return findSqrt (x, mid + 1, hi);
} else {
return findSqrt (x, lo, mid);
}

}``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.