New ADT Implementation

[apines]

Hi all,
I need some advice in implementing a new ADT that has length of n and the following operations:
1) Init() : Initializes all n elements to 0. Can assume that this is the first one called and called only once.
2) Write(i,x): write value x to position i.
3) Read(i): Read the balue at location i.
4) MultiplyAll(y): Multiply ll elements by y, and this can be done many times to create accumulative effect. Cannot get y=0 (returns error)
5) ZeroAll: Zeroes all values in the ADT to 0.
So far so good - But here is the catch: Except the Init, all operations need to have O(1) complexity!
Any ideas?
Thank You,
Aviad

[Rashakil Fol]

Store the array alongside a 'multiplier value' that you multiply the elements of the array by when reading them (and divide by when writing...). Then have MultiplyAll simply change the multiplier value.

Also, keep a counter and increment it with every ZeroAll call. Store with each element in the array a value that tells what the counter's increment was the last time you wrote to it. If the ZeroAll counter is greater than the counter alongside your value, then treat the value as if it were zero.

[apines]

Looks perfect, thanks!

[~s.o.s~]

Storing floating point numbers would be a havoc with the above algorithm. The repeated multiplication and division is going to kill the values which you actually started out with. But still pretty good one. Also since its very much possible that the values inserted might be numbers close to the overflow limit, multiplying them with a multiplier can result in an overflow.

PS: Sam, congratulations on getting a star.