CODEWITHSUNDEEP
algorithmlogic
srip
srip

Reputation: 637

Find closest n from sum of n numbers

I am trying to solve for closest value of n when I am given a sum of first n numbers. Meaning if I have sum as 60, my n should be 10 as the sum of first 10 numbers is 55, if I include 11 the sum would be 66, exceeding my required sum.

int num=1, mysum = 0;  
int givensum=60;
while (mysum < givensum) {
    mysum += num;
    num++;
}
cout<<num-1;
return 0;

The other way I can think of solving this is by solving for quadratic equation
n(n+1) / 2 = givensum and get n from it. Is there any other way to solve this problem?

Upvotes: 2

Views: 2555

Answers (3)

aka.nice
aka.nice

Reputation: 9382

So we want to find an integer n such that (n+1)*n/2 <= y < (n+2)*(n+1)/2

Solving the quadratic equation f(x)=y, where f(x)=(x+1)*x/2 can be done with floating point arithmetic, then taking n as integer part of x.

But we don't really need floating point because we just want the integer part of the result, we can also do it with a Newton-Raphson iteration https://en.wikipedia.org/wiki/Newton%27s_method

The derivative of f(x) is f'(x)=(x+(1/2)). Not a good integer, but we can all multiply by 2, and write the loop like this: (this is Smalltalk, but that does not really matter):

Integer>>invSumFloor
    "Return the integer n such that (1 to: n) sum <= self < (1 to: n+1) sum"

    | guess delta y2 |
    y2 := self * 2.
    guess := 1 bitShift: y2 highBit + 1 // 2.
    [
        delta := ((guess + 1) * guess - y2) // (guess * 2 + 1).
        delta = 0 ]
            whileFalse: [ guess := guess - delta ].
    ^guess - 1

So we are iterating like this:

x(n+1) = x(n) - (2*f(x(n))-2*y)/(2*f'(x(n)))

But instead of taking an exact division, we use // which is the quotient rounded down to nearest integer.

Normally, we should test whether the guess is overstimated or not in the final stage.

But here, we arrange to have the initial guess be an overestimate of the result, but not too much overestimated so that the guess will allways stay overestimated. Like this we can simply subtract 1 in final stage. Above implementation uses a rough guess of first bit position as initial x value.

We can then check the implementation on first ten thousand natural integers with:

(1 to: 10000) allSatisfy: [:y | 
    | n sum |
    n := y invSumFloor.
    sum := (1 to: n) sum.
    (sum <= y and: [y < (sum + n + 1)])].

which answers true

What's nice with Smalltalk is that you can then try things like this:

80 factorial invSumFloor.

And get something like:

378337037695924775539900121166451777161332730835021256527654

You here see that Newton Raphson converges rapidly (7 iterations in above example). This is very different from the initial naive iteration.

Upvotes: 1

Saeid
Saeid

Reputation: 4265

I don't think there is a better way than solving the quadratic equation. It is pretty straightforward, 

n*(n+1)/2 = sum
n^2 + n - sum*2 = 0
assumin ax^2 + bx + c = 0
a = 1, b = 1, c = -2*sum

since we don't need the negative answer:

n = ( -b + sqrt(b^2 - 4ac) ) / 2a

This is the implementation:

#include <iostream>
#include <cmath>
using namespace std;


int main()
{
    int sum = 60;
    int a = 1;
    int b = 1;
    int c = -sum*2;

    double delta = b*b - 4*a*c;
    if ( delta >= 0 ){
        double x1 = -b + sqrt(delta);
        //double x2 = -b - sqrt(delta); // we don't need the negative answer
        x1 /= 2*a;
        //x2 /= 2*a;
        cout << x1 << endl;
    }
    else {
        cout << "no result";
    }
}

the result is a floating point number, if you want the sum of n elements to be less than or equal to the input sum you should round it down with floor function.

Consider the function f(n) = n*(n+1)/2 which yields the sum of first n integers. This function is strictly increasing. So you can use binary search to find n when the value for f(n) is given to you:

#include <iostream>
#include <cmath>
using namespace std;


int main()
{
    int sum = 61;
    int low = 1, high = sum, mid;
    while ( low < high ){
        mid = ceil ( (low+high)/2.0 );
        int s = mid*(mid+1)/2;
        if ( s > sum ){
            high = mid-1;
        } else if ( s < sum ) {
            low = mid;
        } else {
            low = mid;
            break;
        }
    }
    cout << low << endl;
}

Upvotes: 8

codemirel
codemirel

Reputation: 160

After the code breaks out of the while, mysum becomes the closest sum that is greater than your givensum. For the example you have given, the while loop gets executed because 55 is less than 60, and the mysum becomes 66 and num becomes 12 in the last execution of the loop just before it stops. After this step, because 66 is not less than 60, the while does not get executed again. Therefore, you should decrease the mysum by num-2.

cout<<num-2;

Upvotes: 0

Related Questions