Friday, March 27, 2009

Array Creation

Assume the datatype is int32 for the given problem

An input array A of size n is given.
An output array B needs to be created of size k which is defined as

Arr_B= Arr_A + Arr_A[i+1] +... +Arr_A[n-k+i];

Well few Constraints is given:

1) addition of any two elements arr_A[m] and arr_A[n] is expensive.
2) Subtract operation on any two elements sat Arr_A[m] and Arr_A[n] is not supported.

Find the time complexity to create array B and the number of additions in order of n for the creation ?

Hints:

Sliding Window...
This problem seems like you create a window of size n-k and then slide it over the elements of Arr_A to to produce Arr_B.

No comments:

Post a Comment