Given an array numbered from 1 to N, you need to perform M operations. Each operation is described by 3 values a, b and k. Now, k is added for the range of values starting from index 'a' and ending at index 'b' in the given array. Now, After M operations, you have to calculate the average of the values in the array.
Initialize the array to '0' before starting to perform M operations.
Consider the number of elements (N) = 5
Number of operations to perform (M) = 4
When M=1,
a=1, b=2, k=100
When M=2,
a=2, b=5, k=100
When M=3,
a=3, b=4, k=100
Initially the array is 0 0 0 0 0
First operation 100 100 0 0 0
Second operation 100 200 100 100 100
Third operation 100 200 200 200 100
Total = 800, Average = 800/5 = 160
Method 1: (Brute Force)
Implementation:
Initialize the array to '0' before starting to perform M operations.
Consider the number of elements (N) = 5
Number of operations to perform (M) = 4
When M=1,
a=1, b=2, k=100
When M=2,
a=2, b=5, k=100
When M=3,
a=3, b=4, k=100
Initially the array is 0 0 0 0 0
First operation 100 100 0 0 0
Second operation 100 200 100 100 100
Third operation 100 200 200 200 100
Total = 800, Average = 800/5 = 160
Method 1: (Brute Force)
Implementation:
#include <stdio.h> #include <string.h> #include <math.h> #include <stdlib.h> /* Maximum size that an integer array can hold */ #define max 1000000 int main() { int a,b,i; /*largest data type for an integer type data */ unsigned long long int N,M,k,Arr[max],total = 0,average; /* N - Number of elements of the array M - Number of Operations to be performed in the array */ scanf("%llu %llu", &N, &M); /* Initialize the elements of the array to "0" , for "N" elements*/ for ( i = 0;i < N; i++ ) { /* Assign value "0" to A[0],A[1],A[2],....A[N-1] */ Arr [ i ] = 0; } /* For every "M" operation, get the range "a & b" and the value to increment the array - "k" */ while(M > 0) { /* Lower index - a, Upper index - b, value to be added - k */ scanf("%d %d %llu", &a, &b, &k); /* a. Loop over the range a & b, b. Increment the elements of the array within the range with value "k" */ for ( i = a - 1;i <= b - 1; i++) { Arr[ i ] = Arr[ i ] + k; } /* Decrements "M" till it becomes zero */ M--; } /* Find the sum of the elements of the array after "M" Queries. Note that "total is initialized as zero while declaring it" */ for( i = 0;i < N;i ++ ) { /* Can also be written as total+=Arr[i] */ total = total + Arr[ i ]; } /* Calculate the average = (Sum of N elements) / (Number of elements, N) */ average = total / N; /* STDOUT the computer average to the user */ printf("%llu\n", average); return 0; }