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

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.

commented: Good one.. ;-) +19
commented: To counterbalance your star I'm sending you this. -2
commented: I don't like your avatar, but still like you. - Aia :) +1

Looks perfect, thanks!

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.

commented: This comment caused my post above to get a negative rep, so now you get one, too! -1
commented: Counterbalance! +12
Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.