0

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

3
Contributors
3
Replies
4
Views
10 Years
Discussion Span
Last Post by ~s.o.s~
1

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.

Votes + Comments
I don't like your avatar, but still like you. - Aia :)
To counterbalance your star I'm sending you this.
Good one.. ;-)
0

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.

Votes + Comments
Counterbalance!
This comment caused my post above to get a negative rep, so now you get one, too!
This question has already been answered. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.