CODEWITHSUNDEEP
c++algorithmmath
bobthebuilder
bobthebuilder

Reputation: 41

Function: smallest positive integer

#include <iostream>

using namespace std;

int enough(int goal)
{
    
    int C { };
    int i { };
    if (goal > 1)
    {
        while (((C += i) <= goal) && ((goal - i) <= (i + 1)))
        {
            i += 1;
        }
    }
    else
    {
        i = 1;
    }
    return i;
}

int main()
{
    cout << enough(21);
    return 0;
}

So the purpose of this function is for it to return the smallest positive integer that can be summed consecutively from 1 before the cumulative sum becomes greater than the parameter "goal".

So, for example:

cout << enough(9) << endl;

will print 4 because 1+2+3+4 > 9 but 1+2+3<9

cout << enough(21) << endl;

will print 6 'cause 1+2+ . . .+6 > 21 but 1+2+ . . . 5<21

cout << enough(-7) << endl;

will print 1 because 1 > -7 and 1 is the smallest positive integer

cout << enough(1) << endl;

will print 1 because 1 = 1 and 1 is the smallest positive integer

My logic at first was using just while ((C += i) <= goal), but that went wrong, for example, for the parameter 21, where you get C = 20, which passes the test and ends up in i being augmented by 1 (resulting in the return value i = 7, which is clearly wrong).

Therefore I decided to create a test which tested both C and i, but that went wrong because the code isn't considering goal - i and i + 1 as separate tests for the while circuit, but I believe it is actually altering the value of ints goal and i, which screws everything up.

Any ideas where I went wrong?

Upvotes: 2

Views: 201

Answers (2)

Sash Sinha
Sash Sinha

Reputation: 22360

You could perhaps try to simplify your original O(N) approach by only having one condition in your while-loop, i.e., no &&:

#include <iostream>

using namespace std;

int enough(int goal)
{
    if (goal <= 0)
    {
        return 1;
    }
    int total{};
    int i{};
    while (total < goal)
    {
        total += ++i;
    }
    return i;
}

int main()
{
    cout << "enough(9): " << enough(9) << endl;
    cout << "enough(21): " << enough(21) << endl;
    cout << "enough(-7): " << enough(-7) << endl;
    cout << "enough(1): " << enough(1) << endl;
    cout << "enough(0): " << enough(0) << endl;
    return 0;
}

Output:

enough(9): 4
enough(21): 6
enough(-7): 1
enough(1): 1
enough(0): 1

Upvotes: 3

Bathsheba
Bathsheba

Reputation: 234705

Your approach is unnecessarily verbose. There is a closed-form (i.e. O(1)) solution for this.

The sum S of the arithmetic progression 1, 2, ..., n is

S = n * (n + 1) / 2

Rearranging this (completing the square), rejecting the spurious root, and rounding appropriately to fit the requirements of the question yields the result

n = std::ceil((-1 + std::sqrt(1 + 8 * S)) / 2)

This will not work for negative n, and possibly 0 too depending on the specific (and unspecified) requirements.

Or if you must use an O(N) approach, then

int enough(int goal){
    int i = 0;
    for (int total = 0; (total += ++i, total) < goal; );
    return i;
}

will do it, which returns 1 for goal <= 1.

Upvotes: 5

Related Questions