How to find a better algorithm taking less Execution Time?-CodePudding

#include <iostream>
using namespace std;
     
int main() {
    int n;
    cin>>n;
    int *arr=new int [n];
    for(int k=0;n>k;k  )
    {
        cin>>*(arr k);
    }
    long long sum1=0,sum2=0,sum3=0;
    for(int k=0;n>k;k  )
    {
        sum1=sum1 *(arr k);
        if(*(arr k)%2==0)
        sum2  ;
        else 
        sum3  ;
    }
    cout<<sum1<<" ";
    cout<<sum3<<" ";
    cout<<sum2;
     
    return 0;
}

You're given a sequence of N integers, your task is to print sum of them, number of odd integers, and number of even integers respectively.

Input
The first line of input contains an integer N (1≤N≤10⁵).

The second line of input contains N integers separated by a single space (1≤Ai≤10⁵).

Output
Print the sum of them, number of odd integers, and number of even integers respectively, separated by a space.

Examples
input
5
1 2 3 4 5
output
15 3 2

Is there a better algorithm for this code? I need it to take less Execution Time.
Where can I find better algorithms for any code?

CodePudding user response：

Unless you need to re-use the N integers that you have stored in the array, there's no point in storing them. You can get the sum as well as number of odd/even integers as you input them.

Additionally, you don't need long long as the input will never get that big, unless you mean 10^5?

Further, whenever you are thinking about improving performance you should take a look at the big O which in this case is O(N) where N is the number of integers that you have. From an algorithm point of view with N input there's generally very little that you can do to improve this. Maybe if we're talking streams, you can do some statistics but otherwise this implementation is as good as it gets. In some other situations, while the worst case can't be improved, we can improve the average case, which I don't think is applicable here.

Then you should look at profiling the code. That way you have a clear understanding of where bottlenecks are. For your code, there's probably not too much that can be done reasonably.

If we're trying to squeeze every ounce of performance possible, adjusting the compiler flags can bring some performance gains. You should research these but I would not prioritize this over the above.

I would also improve how you name your variables, but this has no impact on performance.

CodePudding user response：

Actually C by default synchronizes cin/cout with C way of doing I/O - printf/scanf, which slows down I/O by quite a lot.

Switching to printf/scanf or adding something like ios::sync_with_stdio(0); at the start of main should speed this up a few times.