CODEWITHSUNDEEP
calgorithm
daniel
daniel

Reputation: 216

Sum of i-th elements of the array

The program receives an array of integers. It is necessary on each new line to output the sum of the i-th elements of the array. For example, for such an array {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}, the answer will be like this :

55 //1+2+3+4+5+6+7+8+9+10
30 //2+4+6+8+10
18 //3+6+9
12 //4+8
15 //5+10
6  //6
7  //7
8  //8
9  //9
10 //10

Here is my code that solves this problem:

#include <string.h> 
#include <stdlib.h>
#include <stdio.h> 

int main(void) { 
    int N, i, j, S; 
    scanf("%d",&N); //length of array
    int a[N];
    for(i = 0; i < N; ++i) scanf("%d",&a[i]); 
    for(i = 1; i <= N; ++i) {
        S = 0;
        for(j = 0; j < N; ++j) 
            S += !((j+1)%i) ? a[j] : 0; 
        printf("%d\n",S);
    }
    return 0;
}

My problem is that my algorithm is not fast enough. And on big data, its speed is very low. I tried to come up with an algorithm that would recursively calculate small sums first, and then calculate other. But I failed to implement it.

Please, can you give me a more elegant option to solve this problem.

Upvotes: 1

Views: 115

Answers (2)

MBo
MBo

Reputation: 80187

Simple modification helps to avoid checking all the indices:

for(j = i - 1; j < N; j += i) 
        S += a[j];

Upvotes: 5

Some programmer dude
Some programmer dude

Reputation: 409176

A for loop doesn't have to increment the iterator variable by only one, you can add any amount to it, for example a[i - 1], as in:

for(j = 0; j < N; j += a[i - 1])

That means the innermost loop will not run as many times in the later iterations.

That also means you can simply skip the condition inside the innermost loop, and just do

S += a[j];

Note: This isn't tested, and might need some tweaking. The general principle is the important part: Do less!

Upvotes: 3

Related Questions