I have a too slow program

Question

I am beginner in programming and I'm learning a c++ language.

I have to create a program, that firstly load a amount of numbers and after this load numbers. I need to obtain a result that adds number one by one if they are not power of 2, else I need to subtract this number.

For example: for 3, result is = -1 - 2 + 3 = 0 (1 and 2 are powers of 2) for 4, result is = -1 - 2 + 3 - 4 = -4

It sounds that it's not problem, but the max value, that program must convert into result is 1 000 000 000. And it must give a result in 3 seconds.

I am pasting my code below. Please, help me make this with ability of converting huge numbers in short time.

#include <iostream>

using namespace std;

int main()
{
    long long amount, number, i = 0, a, b, result = 0;

    cin >> amount;

    while (i < amount) {
        cin >> number;

        if (number < 100000000) {
            a = 1;
            result = 0;
        } else if (100000000 <= number) {
            a = 100000001;
            result = 4999999791564546;
        }

        while (a <= number) {
            b = a;

            while (b % 2 == 0 && b > 1) {
                b = b / 2;
            }

            if (b == 1) {
                result = result - a;
            } else {
                result = result + a;
            }

            a++;
        }

        cout << result << endl;
        i++;
    }
}

Answer 1

All credits go to Quentin. I developed the same idea, but Quentin mentioned first, so all credits go to him.

In all this competetive programming challenges, where you see big numbers and a time limit, "brute force" or "looping over everything" will most certainly not give the desired result.

A good algorithm is always the better solution.

So looking at the task, we need to add all values except some. That means, the first step to the solution is to add all values and then to subtract the "some unwanted" values (the powers of 2). The intermediate result is a sum of all the "wanted" values.

All unwanted values (the powers of 2) need also to be added.

The final result is the intermediate result minus the sum of the powers of 2. Or, as stated in the task description in obfuscated words: "Sum of all values" - "sum of powers of 2" - "sum of powers of 2".

So, as step 1, we need to calculate the sum of all values. This is a well known algorithm. You can find everywhere. Short illustration for value 6:

123456
654321
------
777777

So, we write in one line the sequence of the values and in the next line the reversed sequence. Last line sums the single digts. And, we will easily see the pattern: n * (n+1) / 2

The sum of the powers of 2 is similar simple. In the binary number system, a power of 2 is a value with exactly one set bit:

 1 = 0001
 2 = 0010
 4 = 0100
 8 = 1000
---------
Sum: 1111

The sum is a value with all bits set. With some simple bit fiddling, we can easily find the solution.

Please see a complete working solution below. Please note: It will be extremely fast and the input value will nearly have no influence on the computing time.

#include <iostream>
#include <algorithm>

constexpr unsigned long MaxSource = 1000000000UL;

int main()
{
    // Get the Base value from the user
    std::cout << "Enter a number (1..1000000000):\n";

    unsigned long sourceNumber {0};
    std::cin >> sourceNumber;

    // Limit input value
    sourceNumber = std::clamp (sourceNumber, 1UL, MaxSource);

    // calculate the sum of all values in the range 1..sourceNumber
    const long long t1 {static_cast<long long>(sourceNumber)};
    const long long t2 {t1+1};
    const long long sum1 { (t1 * t2) >> 1 };

    // Now calculate the sum of all powers of 2
    long long sum2 {0x00000000'FFFFFFFF};
    long long bitTestMask {0x00000000'80000000};

    // find the highest set bit
    while (0 == (t1 & bitTestMask)) {
        bitTestMask = bitTestMask >> 1;
        sum2 = sum2  >> 1;
    }

    std::cout << "Result:  " << sum1 - sum2 - sum2 << "\n";

    return 0;
}

I omitted the the typical competetive programmin multiple test case stuff.

What a pity that nobody will read this . . .