Find if subsum is zero

Algorithm:

Step 1: Declare and initialize an array ‘a’ with the given values 1, -2, -3, -4, -5, 1.

Step 2: Declare a variable ‘subsum’ and initialize it to 0.

Step 3: Using for loop, iterate the array elements.
For each element repeat the next two steps.

Step 4: Add array elements to subsum one per the iteration.

Step 5: Check if subsum is equal to zero. If true, then output “Zero subsum found”.

Step 6: Otherwise continue the loop(go to step 4) and return the function.

Dry Run:

   0        1 2        3 4 5   

1

-2

-3

-4

-5

1

Iteration 1:  Start the loop

i=0 and 0<6 -> condition true

  0       1 2        3 4 5   

1

-2

-3

-4

-5

1

a[0] = 1;   

subsum = 0 + 1; (step 4: subsum += a[i])

subsum = 1;

If 1 == 0 -> condition false. Continue the loop. (step 5: subsum==0)

i = 1; (incremented by one)

Iteration 2: 

i=1 and 1<6 -> condition true

  0       1 2        3 4 5   

1

-2

-3

-4

-5

1

a[1] = -2;

subsum = 1 + (-2); (step 4: subsum += a[i])

subsum = -1;

If -1 == 0 -> condition false. Continue the loop. (step 5: subsum==0)

i = 2; (incremented by one)

Iteration 3:

i=2 and 2<6 -> condition true

  0       1 2        3 4 5   

1

-2

-3

-4

-5

1

a[2] = -3;

subsum = -1 + (-3); (step 4: subsum += a[i])

subsum = -4;

If -4 == 0 -> condition false. Continue the loop. (step 5: subsum==0)

i = 3; (incremented by one)

Iteration 4:

i=3 and 3<6 -> condition true

  0       1 2        3 4 5   

1

-2

-3

-4

-5

1

a[3] = -4

subsum = (-4) + (-4); (step 4: subsum += a[i])

subsum = -8;

If -8 == 0 -> condition false. Continue the loop. (step 5: subsum==0)

i = 4; (incremented by one)

Iteration 5:

i=4 and 4<6 -> condition true

  0       1 2        3 4 5   

1

-2

-3

-4

-5

1

a[4] = -5;

subsum = (-8) + (-5); (step 4: subsum += a[i])

subsum = -13;

If -13 == 0 -> condition false. Continue the loop. (step 5: subsum==0)

i = 5; (incremented by one)

Iteration 6:

i=5 and 5<6 -> condition true

  0       1 2        3 4 5   

1

-2

-3

-4

-5

1

a[5] = 1;

subsum = (-13) + 1; (step 4: subsum += a[i])

subsum = -12;

If -12 == 0 -> condition false. Continue the loop. (step 5: subsum==0)

i = 6; (incremented by one)

Iteration 7:

i=6 and 6<6 -> condition false

Terminate the loop.

Implementation:

#include <iostream>

#include <conio.h>

#include <stdio.h>

using namespace std;

int main()

{

int a[] = {1,-2,-3,-4,-5,1}, subsum=0;

for(int i=0;i<6;i++)

{

subsum += a[i];

if(subsum == 0)

cout<<"Zero subsum found";

}

getch();

return 0;

}

Algorithm complexity

O(n) here, n=6 so O(6)