CODEWITHSUNDEEP
javaperformancefor-loop
Trying
Trying

Reputation: 23

Find Number Of Square Roots Between Two Numbers

I have written this function for finding the number of Square Roots between two numbers (inclusive).

static int FindRoot(int no1, int no2) {
    int res = 0;
    for (int x = no1; x <= no2; x++) {
        for (int y = 1; y <= no2; y++) {
            if (y * y == x)
                res++;
        }
    }
    return res;
}

This will work fine, but I was thinking about it's performance. Because in this case the inner For loop will execute from starting position(1), so it'll take time if someone passes a large number range to the method.

So, my question is:

Is there any other way i can find this with better performance?

P.S.- I can't use Math.sqrt() function

Upvotes: 2

Views: 2408

Answers (4)

SamYonnou
SamYonnou

Reputation: 2068

You can get away with having a single for loop by getting rid of the outer loop

static int findRoot(int lo, int hi) {
    int numRoots = 0;

    for (int x = 0, x2 = 0; x2 <= hi; x++, x2 = x * x) {
        if (x2 >= lo) {
            numRoots++;
        }
    }    

    return numRoots;
}

here you effectively just do your inner loop once, incrementing numRoots when x2 (x-squared) is between lo and hi, and terminating the loop when x2 is greater than hi (instead of when x is greater than hi like in your code).

Upvotes: 2

Matt C
Matt C

Reputation: 4555

There are many reasons why your current algorithm is ineffecient, but the biggest one is that the inner for loop is not necessary.

The idea behind the algorithm you're looking for, is to start at the lowest perfect square higher than or equal to no1, then go to the next perfect square and the next and the next, keeping track of how many you hit, until the perfect square you're on is higher than no2.

static int FindRoot(int no1, int no2) {

    int res = 0;
    int x = 1;

    // This loop gets x to the first perfect square greater than
    // or equal to no1
    while( (x * x) < no1 ) {
        x++;
    }

    // This loop adds 1 to res and increases x
    // as long as x^2 is less than or equal to no2
    for(; (x * x) <= no2; x++, res++) { }

    return res;
}

Upvotes: 0

Trying
Trying

Reputation: 23

It'll work as well.

static int FindRoot2(int no1, int no2) {
    int res = 0;
    int inner=1;
    for (int x = no1; x <= no2; x++) {
        for (int y = inner; y <= no2; y++) {
            if (y * y == x)
            {
                inner=y;
                res++;
            }
        }
    }
    return res;
}

In this case inner loop will not start executing from 1.

Upvotes: 0

AJNeufeld
AJNeufeld

Reputation: 8695

static int FindRoot(int no1, int no2) {
    int res = 0;
    int x = 0;

    // Ignore squares less than no1
    while(x*x < no1) {
        x++;
    }

    // Count squares up to and including no2
    while(x*x <= no2) {
        res++;
        x++;
    }

    return res;
}

Upvotes: 3

Related Questions