CODEWITHSUNDEEP
calgorithmmath
mustafalinan
mustafalinan

Reputation: 13

Write a function gets number of squares and will return how many integer numbers are used as square

Write a function getNumberOfSquares(int n) (C) / get_number_of_squares that will return how many integer (starting from 1, 2...) numbers raised to power of 2 and then summed up are less than some number given as a parameter.

e.g 1: For n = 6 result should be 2 because 1^2 + 2^2 = 1 + 4 = 5 and 5 < 6 E.g 2: For n = 15 result should be 3 because 1^2 + 2^2 + 3^2 = 1 + 4 + 9 = 14 and 14 < 15

For the function above I wrote a program but the test program gave an error that is when input is getNumberOfSquares(100000) function should return 66 but mine returns 403.

Here is my solution:

int getNumberOfSquares(int n){

    int sum=0;
    int limit=0;
    for (int i = 1; i < n && n>sum; ++i)
    {
        sum += i*i;
        ++limit;
        if(sum>=n){
            sum -= i*i;
            --limit;
        }
    }
    return limit;
}

Upvotes: 0

Views: 684

Answers (2)

anotherOne
anotherOne

Reputation: 1573

You want to find the biggest i such that sum < n. So this should be the only condition breaking the loop. You don't need to check even that i < n.

Now the problem of your code is that you modify sum when it gets big enough to break the loop, making it again less than n. So if sum < n was your only condition you would have had an infinite loop. But since you have the i < n condition, the program keep adding and subtracting i*i to sum until i < n.

If n is small enough, adding and subtracting i*i doesn't change sum and when the loop breaks you get your result.

But if i can grow big enough to make sum greater than the greatest int you can have, sum overflows and becomes a meaningless value.

The solution is to eliminate the condition if(sum>=n){}.

Removing the condition will reveal that limit is like i, so you can even use i as returned value.

And keeping in mind that you don't need the condition i < n, your function becomes

int getNumberOfSquares(int n) {

    int i, sum = 0;

    for(i = 1; sum < n; ++i) {
        
        sum += i*i;
    }
    
    return i-2;
}

Returning i-2 because the i making sum > n was already 1 more than the value you wanted to return and then before sum > n is checked, thefor increments i.

Upvotes: 0

dbush
dbush

Reputation: 223689

Assuming that an integer is 32 bits on your system, i*i will overflow once it reaches a value of 65536. That causes the inaccuracies.

However it shouldn't actually reach that point, since you continue to check values of i even after the value of sum exceeds n. You should break out of the loop when you reach that point.

int getNumberOfSquares(int n){

    int sum=0;
    int limit=0;
    for (int i = 1; i < n; ++i)
    {
        if (sum + i*i >= n) {
            return limit;
        }
        sum += i*i;
        ++limit;
    }
    return limit;
}

Upvotes: 1

Related Questions