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.
Friday, March 27, 2009
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment